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\), …, \(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\), …, \(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\), …, \(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 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.

Dữ liệu nhập:

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

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

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

Dữ liệu xuất:

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

Ví dụ

Input

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

Output

3  
4  
4