Người hùng Bitaro sắp thực hiện nhiệm vụ phòng thủ để bảo vệ ngôi làng khỏi quái vật. Độ khó của trận phòng thủ là một số nguyên từ \(1\) đến \(L\), được chọn khi bắt đầu nhiệm vụ. Trong trận có độ khó \(\ell\) (\(1 \le \ell \le L\)), lượng máu của mỗi quái vật gấp \(\ell\) lần lượng máu của nó ở độ khó \(1\).

Trận phòng thủ kéo dài \(T\) giây, trong đó có \(N\) quái vật xuất hiện. Các quái vật được đánh số từ \(1\) đến \(N\). Thời điểm \(t\) (\(0 \le t \le T\)) là thời điểm sau khi trận bắt đầu \(t\) giây. Quái vật \(i\) xuất hiện tại thời điểm \(S_i\) (\(0 \le S_i<T\)), có sức mạnh \(P_i\) và có lượng máu bằng \(\ell\times H_i\) khi độ khó là \(\ell\).

Trong trận, Bitaro có thể thực hiện hành động sau tùy ý nhiều lần:

• Chọn một quái vật hiện đang xuất hiện và dành \(1\) giây để tấn công nó. Lượng máu của quái vật giảm đi \(1\). Khi máu giảm về \(0\), quái vật bị đánh bại và không thể bị tấn công thêm.

Khi thời điểm \(T\) đến, trận phòng thủ kết thúc. Gọi \(h_i\) là lượng máu của quái vật \(i\) ngay sau thời điểm \(T\). Điểm phạt của trận được tính bằng

Bitaro hoàn thành nhiệm vụ khi và chỉ khi điểm phạt không vượt quá ngưỡng \(m\) do nhiệm vụ quy định.

Hoàn thành nhiệm vụ ở độ khó càng cao thì phần thưởng càng lớn, nên Bitaro muốn biết độ khó lớn nhất mà mình có thể hoàn thành. Tuy nhiên, ngưỡng \(m\) chưa được thông báo trước. Vì vậy, Bitaro xét \(Q\) ngưỡng có thể có là \(M_1,M_2,\ldots,M_Q\).

Cho thông tin về trận phòng thủ và các ngưỡng, với mỗi ngưỡng hãy xác định có thể hoàn thành nhiệm vụ hay không và, nếu có, tìm độ khó lớn nhất mà Bitaro có thể hoàn thành.

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên \(N,L,T\).
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(S_i,H_i,P_i\).
• Dòng tiếp theo chứa số nguyên \(Q\).
• Trong \(Q\) dòng tiếp theo, dòng thứ \(j\) chứa số nguyên \(M_j\).

Các số trên cùng một dòng được ngăn cách bởi dấu cách.

Dữ liệu ra

In \(Q\) dòng. Dòng thứ \(j\) chứa độ khó lớn nhất mà Bitaro có thể hoàn thành nhiệm vụ khi \(m=M_j\). Nếu không thể hoàn thành ở bất kỳ độ khó nào, in 0.

Ràng buộc

• \(1 \le N \le 6000\).
• \(1 \le L \le 10000000\).
• \(1 \le T \le 10^{18}\).
• \(0 \le S_i<T\) với mọi \(1 \le i \le N\).
• \(1 \le H_i\) và \(1 \le P_i\) với mọi \(1 \le i \le N\).
• \(H_1P_1+H_2P_2+\cdots+H_NP_N \le 10^{11}\).
• \(1 \le Q \le 1000000\).
• \(0 \le M_j \le 10^{18}\) với mọi \(1 \le j \le Q\).
• \(M_1<M_2<\cdots<M_Q\).
• Tất cả các giá trị trong dữ liệu vào đều là số nguyên.

Chấm điểm

1. \(1\) điểm: \(N \le 30\), \(Q=1\), \(M_1=0\), \(L=1\).
2. \(3\) điểm: \(N \le 30\), \(Q=1\), \(M_1=0\).
3. \(10\) điểm: \(N \le 30\), \(Q \le 3\).
4. \(10\) điểm: \(Q \le 3\).
5. \(35\) điểm: \(N \le 30\).
6. \(8\) điểm: \(N \le 400\).
7. \(20\) điểm: \(N \le 1800\).
8. \(13\) điểm: Không có ràng buộc bổ sung.

Ví dụ

2 2 10
0 9 2
8 5 1
3
0
20
40

0
1
2

3 1 100000000000
60000000000 30000000000 1
30000000000 45000000000 1
10000000000 10000000000 1
1
0

0

3 10000000 100000000
60000000 4 1
30000000 6 1
0 2 1
1
0

7000000

5 20 100
0 3 1
20 2 2
40 1 3
60 4 4
80 2 5
11
0
50
100
150
200
250
300
350
400
450
500

6
8
10
12
13
15
16
18
19
20
20

15 10000000 1000000000000
160278118759 43084 33592
442653603914 19490 23090
824219815410 50858 89563
502303340628 56629 45080
495062829942 87342 28821
234536700105 45384 34328
396080693809 78081 50812
734374391045 40873 92012
122606844331 25451 30426
204076581972 58431 13989
495156368673 54276 41670
812963939390 27614 50228
405067019838 96324 18477
464546304875 67562 45956
528559327980 41759 15546
10
216000000000000
1728000000000000
5832000000000000
13824000000000000
27000000000000000
46656000000000000
74088000000000000
110592000000000000
157464000000000000
216000000000000000

995176
1135557
1431775
1824183
2359362
3059523
3942014
5106209
6594716
8448125

Giới hạn

Giới hạn thời gian là \(2\) giây; giới hạn bộ nhớ là \(1024\) MB.

Nguồn

Đề bài của Ủy ban Olympic Tin học Nhật Bản, JOI 2024/2025, vòng tuyển chọn mùa xuân, ngày thi thứ ba. Đề gốc và bản dịch tiếng Việt được cung cấp theo giấy phép CC BY-SA 4.0.