Сіз — монстрлар әскерімен шайқасатын жатырсыз. Алдыңызда \(N\) монстр бар, олардың әрқайсысының \(h_i\) денсаулық ұпайы бар.

Бір шайқаста сіз \(K\) соққыдан артық жасай алмайсыз. Әр соққы белгілі бір монстрға оның денсаулығын жартысын (төменге дөңгелектеп) азайтады. Бір монстр бірнеше рет шабуылдануы мүмкін.

Шайқастан кейін сіз оянасыз, және бәрі қайтадан басталады. Алайда, әр келесі шайқаста бір монстр мутацияға ұшырайды, және оның денсаулығы өзгереді.

Сіз уақыт цикліне тұрып қалдыңыз: барлығы \(Q + 1\) шайқасқа қатысасыз — бірінші шайқаста сізге бастапқы мәндер \(h_1, h_2, \dots, h_N\) беріледі, ал әр келесі шайқаста тек бір монстрдың денсаулығы өзгереді.

Сіздің міндетіңіз — әрбір \(Q + 1\) шайқас үшін \(K\) соққы жасағанда тірі қалған монстрлардың максималды денсаулығының минималды мүмкін мәнін анықтау.

Енгізу

Бірінші жолда \(N\), \(K\) және \(Q\) үш бүтін санды бос орынмен бөлініп берілген (\(1 \le N \le 2 \cdot 10^5\); \(1 \le K \le 10^9\); \(1 \le Q \le 5 \cdot 10^4\)) — монстрлардың саны, соққылар саны және қайталанатын шайқастар саны, сәйкесінше.

Екінші жолда \(N\) бүтін сан \(h_i\) (\(1 \le h_i \le 10^6\)) — бастапқы денсаулық ұпайлары бос орынмен бөлініп берілген.

Келесі \(Q\) жолда екі бүтін сан \(p_j\) және \(d_j\) (\(1 \le p_j \le N\); \(1 \le d_j \le 10^6\)) берілген — денсаулығы өзгерген монстрдың нөмірі және оның жаңа денсаулық мәні, сәйкесінше.

Шығару

Бір жолда \(Q + 1\) бүтін санды шығарыңыз — \(K\) соққыдан кейін монстрлар арасында максималды денсаулықтың минималды мүмкін мәні бастапқы және әрбір \(Q\) өзгерісінен кейін.

Бағалау жүйесі

Мысалдар

Енгізу 1

4 3 2
7 5 4 10
2 1
4 6

Жауап 1

5 4 3

Ескертпелер

Барлық үш шайқасты қарастырайық:

Бірінші шайқас: \([7, 5, 4, 10]\), \(K = 3\).

Оптималды жоспар:

• \(10\)-ға соққы \(\rightarrow 5\)

• \(7\)-ге соққы \(\rightarrow 3\)

• \(5\)-ке соққы \(\rightarrow 2\)

Барлық соққыдан кейін массив: \([3, 2, 4, 5]\), максимум \(5\)-ке тең.

Екінші шайқас: \([7, \mathbf{1}, 4, 10]\)

Оптималды жоспар:

• \(10\)-ға соққы \(\rightarrow 5 \rightarrow 2\)

• \(7\)-ге соққы \(\rightarrow 3\)

Қалғандар: \([3, 1, 4, 2]\), максимум \(4\)-ке тең.

Үшінші шайқас: \([7, 1, 4, \mathbf{6}]\)

Оптималды жоспар:

• \(7\)-ге соққы \(\rightarrow 3\)

• \(4\)-ке соққы \(\rightarrow 2\)

• \(6\)-ға соққы \(\rightarrow 3\)

Енді массив: \([3, 1, 2, 3]\), максимум \(3\)-ке тең.

Жауап: 5 4 3