Có một cuộc đua Segway ở thành phố Dubrovnik. Đường đua bao gồm ba phần, mỗi phần dài 100 mét - do đó, tổng chiều dài của đường đua là 300 mét. Dựa trên giới hạn của pin Segway, mỗi tay đua có một chiến lược: tốc độ mà họ đi trên 100 mét đầu tiên, tốc độ trên 100 mét tiếp theo, và tốc độ trên 100 mét cuối cùng, ngoại trừ khi được phép tăng tốc độ tối đa của Segway (được giải thích trong đoạn tiếp theo).

Đáng tiếc, các Segway rất chậm, mất từ 1 đến 50 giây cho mỗi mét. Do đó, tốc độ trong nhiệm vụ này được cho dưới dạng giây trên mỗi mét (thay vì mét trên giây).

Dọc theo đường đua có nhiều điểm tăng tốc (accelerators). Khi một tay đua đến một điểm tăng tốc, Segway của họ nhận được sức mạnh bổ sung để chạy với tốc độ tối đa là 1 giây trên mỗi mét cho ~X~ ~mod~ ~20~ mét tiếp theo, trong đó ~X~ là số lượng tay đua hoàn toàn đứng trước họ tại thời điểm họ đến điểm tăng tốc (bao gồm cả những người đã hoàn thành cuộc đua). Tay đua không thể sử dụng điểm tăng tốc khác trước khi đã sử dụng hết tất cả sức mạnh bổ sung từ điểm tăng tốc trước. Tại thời điểm đó, nếu không có điểm tăng tốc mới, tay đua tiếp tục di chuyển với tốc độ mặc định cho phần đường đua tương ứng.

Giả sử rằng một tay đua luôn sử dụng điểm tăng tốc có sẵn, ngay cả khi đó có thể không phải là chiến lược tối ưu. Một điểm tăng tốc có thể được sử dụng bởi nhiều tay đua, thậm chí cùng một lúc. Nhiệm vụ của bạn là viết một chương trình mô phỏng cuộc đua này. Giả sử tất cả các tay đua Segway bắt đầu cùng lúc, in ra thời gian hoàn thành cuộc đua cho mỗi tay đua tính bằng giây.

Input

• Dòng đầu tiên chứa một số nguyên ~N~ ~(2 \leq N \leq 20 000)~, số lượng tay đua.
• Dòng thứ ~K~ trong ~N~ dòng tiếp theo chứa ba số nguyên từ ~1~ đến ~50~: tốc độ mặc định của tay đua thứ ~K~ trên 100 mét đầu tiên, 100 mét tiếp theo, và 100 mét cuối cùng của đường đua.
• Dòng tiếp theo chứa một số nguyên ~M~ ~(0 \leq M \leq 299)~, số lượng điểm tăng tốc. Nếu ~M > 0~, dòng tiếp theo chứa một dãy số tăng dần chặt chẽ gồm ~M~ số nguyên từ ~1~ đến ~299~: các khoảng cách từ đầu đường đua đến các điểm tăng tốc tính bằng mét.

Output

Bạn nên in ~N~ dòng, trong đó dòng thứ ~K~ chứa thời gian yêu cầu cho tay đua thứ ~K~.

Chú ý

• ~15 \%~ số test thỏa mãn ~M = 1~.
• ~40 \%~ số test thỏa mãn ~N \leq 300~.

Sample Input 1

2
1 2 3
4 5 6
0

Sample Output 1

600
1500

Sample Input 2

3
5 5 5
6 2 10
10 9 2
2
100 199

Sample Output 2

1496
1799
2075

Sample Input 3

5
2 2 2
6 6 6
8 8 8
9 9 9
10 10 10
2
297 298

Sample Output 3

600
1790
2386
2676
2973

Giải thích

• Mô tả mẫu đầu tiên: Không có điểm tăng tốc và cả hai tay đua đều sử dụng tốc độ mặc định của họ.

• Mô tả mẫu thứ hai: Tay đua số 1 không sử dụng điểm tăng tốc đầu tiên (không có ai ở phía trước anh ta), nhưng sử dụng điểm tăng tốc thứ hai vì tay đua số 2 vượt qua anh ta trong thời gian đó. Tổng cộng, tay đua số 1 đi 299 mét với tốc độ 5 giây mỗi mét, và 1 mét với tốc độ 1 giây.

Tay đua số 2 sử dụng điểm tăng tốc đầu tiên (có một tay đua phía trước), nhưng không sử dụng điểm tăng tốc thứ hai. Tổng cộng, anh ta đi 100 mét với tốc độ 6 giây mỗi mét, 1 mét với tốc độ 1 giây, 99 mét với tốc độ 2 giây mỗi mét, và 100 mét với tốc độ 10 giây mỗi mét.

Tay đua số 3 sau mỗi điểm tăng tốc đi 2 mét ở tốc độ tối đa. Tổng cộng, anh ta đi 100 mét với tốc độ 10 giây mỗi mét, 2 mét với tốc độ 1 giây mỗi mét, 97 mét với tốc độ 9 giây mỗi mét, 2 mét với tốc độ 1 giây mỗi mét, và 99 mét với tốc độ 2 giây mỗi mét.

• Mô tả mẫu thứ ba: Trong số hai điểm tăng tốc gần cuối đường đua, tay đua số 1 không sử dụng bất kỳ điểm nào. Tay đua số 2 sử dụng cả hai (cho 1 mét) và sau đó đi thêm 1 mét với tốc độ mặc định của cô ấy. Tay đua số 3 sử dụng điểm tăng tốc đầu tiên (cho 2 mét) và sau đó đi thêm 1 mét với tốc độ mặc định của cô ấy. Tay đua số 4 và số 5 sử dụng sức mạnh bổ sung từ điểm tăng tốc đầu tiên cho đến hết đường đua.