Trò chơi xếp hình

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 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 dày $1$ đơn vị và 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$, tức thanh thứ $i$ phủ các cột từ $P_i$ đến $P_i+L_i-1$. Thanh rơi thẳng xuống cho tới khi mép dưới của nó tiếp xúc với một cột nào đó (hoặc một thanh ngang đã nằm trên cột đó); khi đó thanh nằm yên và 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 (độ cao mép trên của thanh) khi nó tiếp xúc với một cột nào đó trên màn hình.

Dữ liệu vào

• 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 dương $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$. Mỗi thanh nằm trọn trong màn hình: $P_i+L_i-1\le N$.

Dữ liệu ra

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

Ràng buộc

• $1\le N,M\le {10}^5$.
• $1\le H_i\le {10}^9$.
• $1\le P_i,L_i\le {10}^5$, $P_i+L_i-1\le N$.

Subtasks

• Subtask 1 ($30\%$ số điểm): $1\le N,M\le 1000$, $1\le P_i,L_i\le 1000$.
• Subtask 2 ($30\%$ số điểm): $1\le N,M\le {10}^5$, $1\le P_i,L_i\le {10}^5$. Thỏa mãn $P_i+L_i\le P_j$ (với $1\le i<j\le M$).
• Subtask 3 ($40\%$ số điểm): $1\le N,M\le {10}^5$, $1\le P_i,L_i\le {10}^5$.

Ví dụ