Trong tựa game God of war ra mắt vào tháng 11 năm 2022, Kratos - vị thần chiến tranh, có nhiệm vụ tiêu diệt ~N~ con rồng cổ đại. Các con rồng này được dân gian truyền miệng rằng, nếu chỉ dùng vũ khí gây sát thương lên chúng, chúng sẽ không bao giờ chết. Bởi vì các con rồng này được bảo vệ bởi ~M~ cột trụ do Odin dựng lên. Mỗi cột trụ chỉ bảo vệ một con rồng. Và một con rồng chỉ bị tiêu diệt khi không còn cột trụ nào bảo vệ con rồng đó.

~M~ cột trụ được xếp thành một hàng ngang và lần lượt được đánh số từ ~1~ đến ~M~. Mỗi cột trụ có HP (máu) là ~h_i~, khi một cột bị nhận ~x~ sát thương, HP của cột trụ tương ứng sẽ giảm đi ~x~ đơn vị. Nếu HP của cột trụ ~\leq 0~, cột trụ sẽ bị phá hủy.

Kratos thi triển ~Q~ lần tuyệt chiêu Spartan Rage. Tuyệt chiêu có dạng ~(l, r, x)~: Kratos gây ~x~ đơn vị sát thương lên các cột trụ có số thứ tự từ ~l~ đến ~r~ chưa bị phá hủy.

Với mỗi con rồng, bạn hãy xác định sau sự kiện thứ mấy, nó sẽ bị tiêu diệt.

Input

• Dòng đầu tiên chứa số nguyên ~N, M, Q~ ~(1 \leq N, M, Q \leq 10^5)~ - lần lượt là số con rồng, số cột trụ, số lần thi triển tuyệt chiêu của Kratos.
• ~M~ dòng tiếp theo, mỗi dòng chứ hai số nguyên ~h_i~ và ~p_i~ ~(1 \leq h_i \leq 10^9, 1 \leq p_i \leq N)~ - lần lượt là HP của cột trụ thứ ~i~ và con rồng mà nó bảo vệ.
• ~Q~ dòng tiếp theo, mỗi dòng gồm ba số nguyên ~l_i, r_i, x_i~ ~(1 \leq l_i \leq r_i \leq M, 1 \leq x_i \leq 10^9)~ - mô tả lần thi triển tuyệt chiêu thứ ~i~ của Kratos.

Output

• Gồm ~N~ dòng, dòng thứ ~i~ ghi một số nguyên ~d_i~ ~(1 \leq d_i \leq Q)~ cho biết sau ~d_i~ lần thi triển tuyệt chiêu thì con rồng thứ ~i~ bị tiêu diệt. Nếu con rồng không bị tiêu diệt, in ra Failed.

Scoring

• Subtask 1 (~25\%~): ~N, M, Q \leq 5000~;
• Subtask 2 (~25\%~): ~l_i = r_i~;
• Subtask 3 (~50\%~): ràng buộc gốc.

Sample Input

2 5 4
10 1
2 2
5 2
7 1
1 1
1 2 1
2 4 1
3 5 4
1 5 3

Sample Output

Failed
3