Hoa ban

Đến với Điện Biên lần này các bạn không có cơ hội được ngắm nhìn những bông hoa Ban tuyệt đẹp bởi vì chúng chỉ nở vào mùa xuân. Tuy nhiên, các bạn có thể ngắm nhìn hàng cây gồm $n$ cây hoa Ban trồng bên đường được đánh số từ cây $1$ đến cây $n$ từ chân đèo đến đỉnh đèo Pha Đin.

Khi lấy từ vườn ươm mang đi trồng mỗi cây đều có chiều cao là một số nguyên dương $B$. Để chăm sóc cho hàng cây hoa Ban này tính đến nay người ta đã sử dụng hết $Q$ bao phân bón tổng hợp. Các bao phân bón được sử dụng lần lượt từ bao phân bón thứ $1$ đến bao phân bón thứ $Q$, bón hết bao này rồi mới tới bao khác.

Biết rằng trong bao phân bón thứ $i$ ($1\le i\le Q$) có $p_i$ viên phân bón. Khi sử dụng nó, người ta phải thực hiện $p_i$ lần bón phân cho cây, mỗi lần chỉ bón một viên và thực hiện như sau:

• Chọn cây có chiều cao nhỏ nhất trong các cây từ cây $1$ đến cây $r_i$. Nếu có nhiều cây có cùng chiều cao nhỏ nhất thì chọn cây có số thứ tự nhỏ nhất trong số chúng.
• Bón một viên cho cây được chọn, khi đó chiều cao của cây được bón phân sẽ tăng thêm $1$ đơn vị.

Yêu cầu: Hãy cho biết chiều cao của $n$ cây hoa Ban hiện tại.

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên dương $n,Q,B$ ($n,Q\le {10}^5$, $B\le {10}^9$).
• Dòng thứ $i$ trong $Q$ dòng tiếp theo mỗi dòng chứa hai số nguyên dương $r_i$ và $p_i$ ($r_i\le n$; $p_i\le {10}^9$).

Dữ liệu ra

In ra $n$ số nguyên là chiều cao hiện tại của các cây hoa Ban từ cây thứ $1$ đến cây thứ $n$, mỗi số cách nhau bởi một dấu cách trống.

Ràng buộc

• $1\le n,Q\le {10}^5$.
• $1\le B\le {10}^9$.
• $1\le r_i\le n$, $1\le p_i\le {10}^9$.

Subtasks

Điểm được tính theo từng test.

• Subtask 1 ($25\%$ số test): $n,Q\le 2000$; $p_i=1$ với $1\le i\le Q$.
• Subtask 2 ($25\%$ số test): $p_i=1$ với $1\le i\le Q$.
• Subtask 3 ($25\%$ số test): $n,Q\le 2000$.
• Subtask 4 ($25\%$ số test): $2000<n,Q\le {10}^5$.

Ví dụ