Khu vườn có thể mô tả như một mảng một chiều: \(H = h_1, h_2, \ldots, h_n\) trong đó \(h_i\) là chiều cao ở vị trí \(i\). Có một con ếch sống trong khu vườn kỳ diệu đó. Mỗi buổi sáng, ếch đều tập nhảy trong vườn. Sáng thứ \(i\), ếch sẽ xuất phát tại \(x_i\), nhảy \(k_i\) bước theo quy tắc nhảy sau:

• Nếu đang quay mặt về bên phải, nó sẽ nhảy đến vị trí gần nó nhất về bên phải, sao cho độ cao ở đó lớn hơn hoặc bằng độ cao ở hiện tại. Nếu vị trí như thế không tồn tại, nó sẽ nhảy quay đầu, tức là nhảy tại chỗ và quay đầu lại (vẫn tính 1 bước nhảy)
• Nếu nó đang quay mặt về bên trái, nó sẽ nhảy đến vị trí gần nó nhất về bên trái, sao cho độ cao ở đó nhỏ hơn hoặc bằng độ cao ở hiện tại. Nếu vị trí như thế không tồn tại, nó sẽ nhảy quay đầu, tức là nhảy tại chỗ và quay đầu lại (vẫn tính 1 bước nhảy)

Biết rằng mỗi sáng ếch đều bắt đầu ở tư thế quay sang phải. Hãy cho biết vị trí mà ếch kết thúc buổi tập

Input

• Dòng đầu tiên chứa \(n,m\) là số vị trí và số ngày
• Dòng tiếp theo chứa dãy \(H\)
• \(m\) dòng tiếp theo, dòng thứ \(i\) chứa \(x_i, k_i\)

Output

• In ra \(m\) dòng là vị trí kết thúc của ếch trong \(m\) ngày đó

Scoring

• \(1 \leq n,m \leq 10^5\), \(1 \leq k_i, h_i \leq 10^9\)
• Subtask \(1\) (\(20\%\) số điểm): \(m, k_i \leq 5000\)
• Subtask \(2\) (\(20\%\) số điểm): dãy \(H\) tăng nghiêm ngặt

Example

5 2
1 2 3 4 5
1 4
1 9 

5
1