1134 : ลำดับ (sequence)
Problem type : Batch
Time limit : 0.3 second(s)
Memory limit : 32 megabyte(s)
ให้ A, B, C, D, E, F, G, H เป็นจำนวนเต็มใดๆ เราจะนิยามลำดับ a1, a2, a3, … ดังนี้

a1 = A, a2 = B, a3 = C, a4 = D

และ ak = Eak-1 + Fak-2 + Gak-3 + Hak-4 สำหรับทุกจำนวนเต็ม k ≥ 5

งานของคุณ
จงเขียนโปรแกรมเพื่อตอบคำถามทั้งหมด Q คำถามว่า สำหรับแต่ละค่า N เศษจากการหาร aN ด้วย 2553 มีค่าเท่าไร

ข้อมูลนำเข้า
บรรทัดแรกระบุจำนวนเต็ม A, B, C, D, E, F, G และ H ซึ่งแต่ละจำนวนจะมีค่าอยู่ในช่วงตั้งแต่ 0 ถึง 1,000

บรรทัดที่ 2 ระบุจำนวนเต็ม Q (2 ≤ Q ≤ 200,000) แทนจำนวนคำถามทั้งหมด

อีก Q บรรทัดต่อมา ในบรรทัดที่ i+2 (1 ≤ i ≤ Q) จะระบุจำนวนเต็ม N (1 ≤ N ≤ 1,000,000,000,000,000,000) แสดงถึงคำถามที่ i

ข้อมูลส่งออก
มีทั้งหมด Q บรรทัด โดยในบรรทัดที่ i (1 ≤ i ≤ Q) แสดงคำตอบของคำถามที่ i

การให้คะแนน
20% ของข้อมูลทดสอบ จะมี N ≤ 1,000,000 ในทุกคำถาม
50% ของข้อมูลทดสอบ จะมี G = H = 0
60% ของข้อมูลทดสอบ จะมี Q ≤ 2,000

ที่มา
การแข่งขัน IOI Thailand League เดือนตุลาคม 2553
โจทย์โดย: สุธี เรืองวิเศษ
ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
1 2 3 4 2 3 0 0
7
1
2
3
4
5
6
7
1
2
3
4
17
46
143
5 2 1 8 4 9 3 6
8
10
20
15
1
5
4
12
15
1127
2306
443
5
77
8
1598
443

ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้

กำลังออนไลน์: 24 ผู้เยี่ยมชมและ 0 สมาชิก (5 บอท)