Bon rất thích trò chơi điện tử đặc biệt là trò chơi xếp hình. Hôm nay Bon 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.

Yêu cầu: Xác định độ 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~).

Output

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

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