Có một hầm ngục gồm \(N+1\) tầng và \(M\) người chơi bên trong. Các tầng được đánh số từ \(1\) đến \(N+1\) theo thứ tự từ gần cửa vào nhất. Những người chơi được đánh số từ \(1\) đến \(M\).

Để đi từ tầng \(i\) sang tầng \(i+1\) (\(1 \le i \le N\)), người chơi phải tiêu hao \(A_i\) đơn vị năng lượng. Hầm ngục chỉ cho phép đi một chiều: chỉ có thể di chuyển từ tầng \(i\) sang tầng \(i+1\).

Trên mỗi tầng từ \(1\) đến \(N\) có một suối hồi phục. Tại suối ở tầng \(i\), người chơi có thể trả \(B_i\) đồng xu để hồi phục \(1\) đơn vị năng lượng. Có thể sử dụng suối nhiều lần miễn là có đủ xu. Tuy nhiên, mỗi người chơi có một giới hạn năng lượng riêng, và năng lượng không được vượt quá giới hạn đó kể cả khi sử dụng suối hồi phục.

Người chơi thứ \(j\) (\(1 \le j \le M\)) hiện ở tầng \(S_j\), có năng lượng hiện tại bằng \(0\) và giới hạn năng lượng là \(U_j\). Người này muốn tới tầng \(T_j\) mà năng lượng không bao giờ nhỏ hơn \(0\) trên đường đi.

Cho thông tin về hầm ngục và những người chơi, với mỗi người hãy xác định có thể tới tầng đích hay không. Nếu có thể, hãy tìm số đồng xu ít nhất cần dùng.

Dữ liệu vào

Dữ liệu được cho từ đầu vào chuẩn:

N M
A_1 A_2 ... A_N
B_1 B_2 ... B_N
S_1 T_1 U_1
...
S_M T_M U_M

Tất cả các giá trị đầu vào đều là số nguyên.

Dữ liệu ra

In ra \(M\) dòng. Dòng thứ \(j\) (\(1 \le j \le M\)) chứa số đồng xu ít nhất mà người chơi thứ \(j\) cần để tới tầng \(T_j\). Nếu người đó không thể tới tầng \(T_j\), in ra \(-1\).

Ràng buộc

• \(1 \le N \le 200\,000\).
• \(1 \le M \le 200\,000\).
• \(1 \le A_i \le 200\,000\) với mọi \(1 \le i \le N\).
• \(1 \le B_i \le 200\,000\) với mọi \(1 \le i \le N\).
• \(1 \le S_j < T_j \le N+1\) với mọi \(1 \le j \le M\).
• \(1 \le U_j \le 100\,000\,000\) với mọi \(1 \le j \le M\).

Phân nhóm

• Nhóm 1 (11 điểm): \(N \le 3000\), \(M \le 3000\).
• Nhóm 2 (14 điểm): \(U_1=U_2=\cdots=U_M\).
• Nhóm 3 (31 điểm): \(T_j=N+1\) với mọi \(1 \le j \le M\).
• Nhóm 4 (44 điểm): Không có ràng buộc bổ sung.

Ví dụ

5 4
3 4 1 1 4
2 5 1 2 1
1 6 3
1 6 4
3 5 1
2 5 9

-1
29
3
22

10 10
1 8 9 8 1 5 7 10 6 6
10 10 2 8 10 3 9 8 3 7
2 11 28
5 11 28
7 11 28
1 11 18
3 11 18
8 11 18
4 11 11
6 11 11
10 11 11
9 11 5

208
112
179
248
158
116
234
162
42
-1

20 20
2 3 2 11 4 6 9 15 17 14 8 17 3 12 20 4 19 8 4 5
19 3 18 2 13 7 5 19 10 1 12 8 1 15 20 1 13 2 18 6
12 15 67
7 15 18
16 17 14
9 21 97
1 19 43
3 18 31
16 20 70
7 20 28
1 16 61
3 5 69
9 10 15
2 13 134
11 19 23
16 20 14
5 21 16
15 20 11
7 11 54
7 16 16
13 17 10
3 15 135

151
591
4
284
339
517
35
581
254
58
-1
178
519
-1
-1
-1
219
-1
-1
214

Nguồn

JOI 2020/2021, vòng chung kết quốc gia, ngày 14/02/2021. Đề gốc của Ủy ban Olympic Tin học Nhật Bản: tiếng Anh, tiếng Nhật. Bản dịch theo giấy phép CC BY-SA 4.0.