Bon rất thích trò chơi điện tử đặc biệt là trò chơi xếp hình. Nhân ngày sinh nhật, Bon đòi cậu HA mua cho Bon một máy chơi điện tử, vì rất quý cháu nên HA mua cho Bon máy điện tử xếp hình để cậu bé chơi giải trí.

Có máy điện tử, cứ đến bữa ăn là Bon mang ra chơi để có thể ăn cơm dễ dàng hơn. Hôm nay Bon thấy thấy trên màn hình đã có sẵn ~N~ thanh thẳng đứng xếp sát nhau đánh chỉ số từ ~1~ đến ~N~, các thanh có độ cao là ~H_1, H_2, \dots, H_N~.

Phía trên của màn hình xuất hiện lần lượt ~M~ thanh nằm ngang, mỗi thanh có độ dài lần lượt là ~L_1, L_2, \dots, L_M~. Các thanh xuất hiện được xác định tọa độ của mép bên trái thanh đó là vị trí ~P_1, P_2, \dots, P_M~. Khi một thanh rơi xuống và mép dưới thanh tiếp xúc với một cột nào đó thì mới xuất hiện thanh tiếp theo trên màn hình.

Bạn hãy giúp Bon xác định xem độ cao của mỗi thanh ngang khi nó tiếp xúc với một cột nào đó trên màn hình.

Input

• Dòng ~1~ chứa hai số ~N~ và ~M~ ~(1 \le N, M \le 10^5)~

• Dòng ~2~ chứa ~N~ số nguyên không âm ~H_1, H_2, \dots, H_N~ ~(1 \le H_i \le 10^9)~

• ~M~ dòng tiếp theo mỗi dòng chứa ~2~ số ~P_i~ và ~L_i~ ~(1 \le P_i, L_i \le 10^5)~ - là vị trí xuất hiện và chiều dài của thanh thứ ~i~.

Output

• ~M~ dòng, mỗi dòng ~i~ là độ cao của thanh ngang thứ ~i~ khi rơi xuống.

Scoring

Sample Input 1

13 3
3 2 1 1 4 2 1 2 1 1 1 2 3
2 2
8 6
3 1

Sample Output 1

3
4
4

Notes

• Thanh ngang thứ nhất phủ các vị trí ~2~ và ~3~, có mép trên ở độ cao ~3~.

• Thanh ngang thứ hai phủ các vị trí từ ~8~ đến ~13~, có mép trên ở độ cao ~4~.

• Thanh ngang thứ ba nằm trên thanh ngang thứ nhất tại vị trí ~3~, có mép trên ở độ cao ~4~.