รายละเอียดโจทย์

บีทาโร่อาศัยอยู่รอบทะเลสาบขนาดใหญ่ที่เป็นรูปวงกลม ความยาวรอบทะเลสาบคือ $L$ และที่จุดหนึ่งรอบทะเลสาบมีบ้านของบีทาโร่ตั้งอยู่ จุดที่ไปถึงเมื่อเคลื่อนที่จากบ้านของบีทาโร่ไปตามเส้นรอบวงของทะเลสาบในทิศทางตามเข็มนาฬิกาเป็นระยะทาง $x$ ($0 \le x < L$) จะเรียกว่าจุด $x$ ปัจจุบันกำลังมีการวางแผนจัดการแข่งขันมาราธอนที่จะจัดขึ้นรอบทะเลสาบ

บีทาโร่ได้ยินมาว่าการแข่งขันมาราธอนมีกำหนดการจะจัดขึ้นดังต่อไปนี้:

• มีการเตรียมป้ายหมายเลขตั้งแต่ $0$ ถึง $L - 1$ ไว้หมายเลขละ $1$ แผ่น ผู้เข้าร่วมการแข่งขันมาราธอนแต่ละคนจะสวมป้ายหมายเลขแผ่นใดแผ่นหนึ่ง จุดเริ่มต้นของผู้เข้าร่วมที่สวมป้ายหมายเลข $l$ ($0 \le l \le L - 1$) คือจุด $l$
• หลังจากการแข่งขันมาราธอนเริ่มต้นขึ้น เป็นเวลา $T$ วินาที ผู้เข้าร่วมจะเคลื่อนที่ไปรอบทะเลสาบในทิศทางตามเข็มนาฬิกาด้วยความเร็วของแต่ละคน เวลาที่ผ่านไป $t$ วินาที ($0 \le t \le T$) นับตั้งแต่เริ่มการแข่งขันมาราธอนจะเรียกว่าเวลา $t$

บีทาโร่มีรายชื่อผู้เข้าร่วมการแข่งขันมาราธอน ปัจจุบันมีผู้เข้าร่วม $N$ คนระบุอยู่ในรายชื่อผู้เข้าร่วม โดยผู้เข้าร่วมคนที่ $i$ ($1 \le i \le N$) มีกำหนดจะสวมป้ายหมายเลข $A_i$ และเคลื่อนที่ไปรอบทะเลสาบในทิศทางตามเข็มนาฬิกาด้วยความเร็ว $S_i$ ต่อ $1$ วินาที

จากรายชื่อผู้เข้าร่วม บีทาโร่ได้หาจำนวนครั้งของการชนกันที่เกิดขึ้นระหว่างการแข่งขันมาราธอน ในที่นี้ การชนกันหมายถึงการที่ผู้เข้าร่วมที่ต่างกัน $2$ คนอยู่ที่จุดเดียวกัน กล่าวอย่างเคร่งครัดคือ เขาได้หาจำนวนชุดสามสิ่งอันดับ $(p, q, t)$ ที่ประกอบด้วยจำนวนเต็ม $p, q$ ซึ่งสอดคล้องกับ $0 \le p < q \le L - 1$ และจำนวนจริง $t$ ซึ่งสอดคล้องกับ $0 \le t \le T$ ที่สอดคล้องกับเงื่อนไขต่อไปนี้:

• มีผู้เข้าร่วมที่สวมป้ายหมายเลข $p$
• มีผู้เข้าร่วมที่สวมป้ายหมายเลข $q$
• ผู้เข้าร่วมที่สวมป้ายหมายเลข $p$ และผู้เข้าร่วมที่สวมป้ายหมายเลข $q$ อยู่ที่จุดเดียวกันในเวลา $t$

ทว่า หลังจากนั้นได้มีการเปลี่ยนแปลงรายชื่อผู้เข้าร่วมจำนวน $Q$ ครั้ง การเปลี่ยนแปลงครั้งที่ $j$ ($1 \le j \le Q$) แทนด้วยจำนวนเต็ม $2$ จำนวนคือ $X_j, Y_j$ และมีรายละเอียดดังต่อไปนี้:

• ปัจจุบัน หากมีคนที่สวมป้ายหมายเลข $X_j$ และเคลื่อนที่รอบทะเลสาบตามเข็มนาฬิกาด้วยความเร็ว $Y_j$ ต่อ $1$ วินาทีระบุอยู่ในรายชื่อผู้เข้าร่วม ให้ลบคนนั้นออกจากรายชื่อผู้เข้าร่วม มิฉะนั้น ให้เพิ่มคนที่สวมป้ายหมายเลข $X_j$ และเคลื่อนที่รอบทะเลสาบตามเข็มนาฬิกาด้วยความเร็ว $Y_j$ ต่อ $1$ วินาทีเข้าไปในรายชื่อผู้เข้าร่วมใหม่

ทั้งนี้ รับประกันว่า ณ เวลาที่การเปลี่ยนแปลงใดๆ สิ้นสุดลง จะมีผู้เข้าร่วมระบุอยู่ในรายชื่อผู้เข้าร่วมตั้งแต่ $2$ คนขึ้นไป และป้ายหมายเลขที่ผู้เข้าร่วมสวมใส่จะแตกต่างกันทั้งหมด

บีทาโร่ต้องการทราบจำนวนครั้งของการชนกันที่เกิดขึ้นระหว่างการแข่งขันมาราธอนของผู้เข้าร่วม ณ เวลาที่การเปลี่ยนแปลงแต่ละครั้งสิ้นสุดลง จากขอบเขตข้อมูลของโจทย์ สามารถพิสูจน์ได้ว่าจำนวนครั้งของการชนกันที่เกิดขึ้นระหว่างการแข่งขันมาราธอนมีค่าจำกัด

เมื่อกำหนดข้อมูลเกี่ยวกับการแข่งขันมาราธอนและการเปลี่ยนแปลงรายชื่อผู้เข้าร่วม จงเขียนโปรแกรมเพื่อหาเศษเหลือจากการหารจำนวนครั้งของการชนกันที่เกิดขึ้นระหว่างการแข่งขันมาราธอนของผู้เข้าร่วม ณ เวลาที่การเปลี่ยนแปลงแต่ละครั้งสิ้นสุดลงด้วย $1000000007$

ขอบเขตข้อมูล

• $2 \le N$
• $N \le L \le 10^9$
• $1 \le T \le 10^9$
• $0 \le A_i \le L - 1$ ($1 \le i \le N$)
• $A_i \ne A_j$ ($1 \le i < j \le N$)
• $1 \le S_i \le 10^9$ ($1 \le i \le N$)
• $1 \le Q$
• $N + Q \le 100000$
• $0 \le X_j \le L - 1$ ($1 \le j \le Q$)
• $1 \le Y_j \le 10^9$ ($1 \le j \le Q$)
• ณ เวลาที่การเปลี่ยนแปลงใดๆ สิ้นสุดลง จะมีผู้เข้าร่วมตั้งแต่ $2$ คนขึ้นไป
• ณ เวลาที่การเปลี่ยนแปลงใดๆ สิ้นสุดลง จุดเริ่มต้นของผู้เข้าร่วมจะแตกต่างกันทั้งหมด
• ค่าที่รับเข้ามาทั้งหมดเป็นจำนวนเต็ม

โจทย์ย่อย

1. ($10$ คะแนน) $T = 1$, $S_i \le 2$ ($1 \le i \le N$), $Y_j \le 2$ ($1 \le j \le Q$)
2. ($8$ คะแนน) $N \le 2000$, $Q = 1$
3. ($11$ คะแนน) $N \le 2000$, $Q \le 2000$
4. ($27$ คะแนน) $Q = 1$
5. ($34$ คะแนน) $N + Q \le 78000$
6. ($10$ คะแนน) ไม่มีเงื่อนไขเพิ่มเติม

ข้อมูลนำเข้า

ข้อมูลนำเข้าจะกำหนดให้ในรูปแบบต่อไปนี้: $$\begin{aligned} &N \quad L \quad T \\ &A_1 \quad A_2 \quad \dots \quad A_N \\ &S_1 \quad S_2 \quad \dots \quad S_N \\ &Q \\ &X_1 \quad Y_1 \\ &X_2 \quad Y_2 \\ &\vdots \\ &X_Q \quad Y_Q \end{aligned}$$

ข้อมูลส่งออก

แสดงผล $Q$ บรรทัด ในบรรทัดที่ $j$ ($1 \le j \le Q$) ให้แสดงเศษเหลือจากการหารจำนวนครั้งของการชนกันที่เกิดขึ้นระหว่างการแข่งขันมาราธอนของผู้เข้าร่วม ณ เวลาที่การเปลี่ยนแปลงครั้งที่ $j$ สิ้นสุดลงด้วย $1000000007$

ตัวอย่าง

ตัวอย่าง 1

ข้อมูลนำเข้า

3 7 2
1 6 3
4 1 6
1
4 2

ข้อมูลส่งออก

7

คำอธิบาย

มีผู้เข้าร่วม $4$ คน ณ เวลาที่การเปลี่ยนแปลงครั้งที่ $1$ สิ้นสุดลง ข้อมูลเกี่ยวกับผู้เข้าร่วมแต่ละคนเป็นดังนี้:

1. สวมป้ายหมายเลข $1$ และเริ่มต้นจากจุด $1$ เคลื่อนที่ตามเข็มนาฬิกาด้วยความเร็ว $4$ ต่อ $1$ วินาที
2. สวมป้ายหมายเลข $6$ และเริ่มต้นจากจุด $6$ เคลื่อนที่ตามเข็มนาฬิกาด้วยความเร็ว $1$ ต่อ $1$ วินาที
3. สวมป้ายหมายเลข $3$ และเริ่มต้นจากจุด $3$ เคลื่อนที่ตามเข็มนาฬิกาด้วยความเร็ว $6$ ต่อ $1$ วินาที
4. สวมป้ายหมายเลข $4$ และเริ่มต้นจากจุด $4$ เคลื่อนที่ตามเข็มนาฬิกาด้วยความเร็ว $2$ ต่อ $1$ วินาที

สำหรับผู้เข้าร่วม ณ เวลาที่การเปลี่ยนแปลงครั้งที่ $1$ สิ้นสุดลง การชนกันระหว่างการแข่งขันมาราธอนจะเกิดขึ้น $7$ ครั้งดังต่อไปนี้:

1. ที่เวลา $1 \div 4$ ผู้เข้าร่วมที่สวมป้ายหมายเลข $3$ และผู้เข้าร่วมที่สวมป้ายหมายเลข $4$ อยู่ที่จุดเดียวกันคือจุด $9 \div 2$
2. ที่เวลา $3 \div 5$ ผู้เข้าร่วมที่สวมป้ายหมายเลข $3$ และผู้เข้าร่วมที่สวมป้ายหมายเลข $6$ อยู่ที่จุดเดียวกันคือจุด $33 \div 5$
3. ที่เวลา $3 \div 2$ ผู้เข้าร่วมที่สวมป้ายหมายเลข $1$ และผู้เข้าร่วมที่สวมป้ายหมายเลข $4$ อยู่ที่จุดเดียวกันคือจุด $0$
4. ที่เวลา $5 \div 3$ ผู้เข้าร่วมที่สวมป้ายหมายเลข $1$ และผู้เข้าร่วมที่สวมป้ายหมายเลข $6$ อยู่ที่จุดเดียวกันคือจุด $2 \div 3$
5. ที่เวลา $2$ ผู้เข้าร่วมที่สวมป้ายหมายเลข $3$ และผู้เข้าร่วมที่สวมป้ายหมายเลข $4$ อยู่ที่จุดเดียวกันคือจุด $1$
6. ที่เวลา $2$ ผู้เข้าร่วมที่สวมป้ายหมายเลข $3$ และผู้เข้าร่วมที่สวมป้ายหมายเลข $6$ อยู่ที่จุดเดียวกันคือจุด $1$
7. ที่เวลา $2$ ผู้เข้าร่วมที่สวมป้ายหมายเลข $4$ และผู้เข้าร่วมที่สวมป้ายหมายเลข $6$ อยู่ที่จุดเดียวกันคือจุด $1$

ตัวอย่างข้อมูลนำเข้านี้สอดคล้องกับเงื่อนไขของโจทย์ย่อยที่ $2, 3, 4, 5, 6$

ตัวอย่าง 2

ข้อมูลนำเข้า

3 6 1
1 3 4
1 1 1
2
0 2
1 1

ข้อมูลส่งออก

1
0

คำอธิบาย

มีผู้เข้าร่วม $4$ คน ณ เวลาที่การเปลี่ยนแปลงครั้งที่ $1$ สิ้นสุดลง ข้อมูลเกี่ยวกับผู้เข้าร่วมแต่ละคนเป็นดังนี้:

1. สวมป้ายหมายเลข $1$ และเริ่มต้นจากจุด $1$ เคลื่อนที่ตามเข็มนาฬิกาด้วยความเร็ว $1$ ต่อ $1$ วินาที
2. สวมป้ายหมายเลข $3$ และเริ่มต้นจากจุด $3$ เคลื่อนที่ตามเข็มนาฬิกาด้วยความเร็ว $1$ ต่อ $1$ วินาที
3. สวมป้ายหมายเลข $4$ และเริ่มต้นจากจุด $4$ เคลื่อนที่ตามเข็มนาฬิกาด้วยความเร็ว $1$ ต่อ $1$ วินาที
4. สวมป้ายหมายเลข $0$ และเริ่มต้นจากจุด $0$ เคลื่อนที่ตามเข็มนาฬิกาด้วยความเร็ว $2$ ต่อ $1$ วินาที

สำหรับผู้เข้าร่วม ณ เวลาที่การเปลี่ยนแปลงครั้งที่ $1$ สิ้นสุดลง การชนกันระหว่างการแข่งขันมาราธอนจะเกิดขึ้น $1$ ครั้งดังต่อไปนี้:

1. ที่เวลา $1$ ผู้เข้าร่วมที่สวมป้ายหมายเลข $0$ และผู้เข้าร่วมที่สวมป้ายหมายเลข $1$ อยู่ที่จุดเดียวกันคือจุด $2$

มีผู้เข้าร่วม $3$ คน ณ เวลาที่การเปลี่ยนแปลงครั้งที่ $2$ สิ้นสุดลง ข้อมูลเกี่ยวกับผู้เข้าร่วมแต่ละคนเป็นดังนี้:

1. สวมป้ายหมายเลข $3$ และเริ่มต้นจากจุด $3$ เคลื่อนที่ตามเข็มนาฬิกาด้วยความเร็ว $1$ ต่อ $1$ วินาที
2. สวมป้ายหมายเลข $4$ และเริ่มต้นจากจุด $4$ เคลื่อนที่ตามเข็มนาฬิกาด้วยความเร็ว $1$ ต่อ $1$ วินาที
3. สวมป้ายหมายเลข $0$ และเริ่มต้นจากจุด $0$ เคลื่อนที่ตามเข็มนาฬิกาด้วยความเร็ว $2$ ต่อ $1$ วินาที

สำหรับผู้เข้าร่วม ณ เวลาที่การเปลี่ยนแปลงครั้งที่ $2$ สิ้นสุดลง การชนกันระหว่างการแข่งขันมาราธอนจะเกิดขึ้น $0$ ครั้ง

ตัวอย่างข้อมูลนำเข้านี้สอดคล้องกับเงื่อนไขของโจทย์ย่อยที่ $1, 3, 5, 6$

ตัวอย่าง 3

ข้อมูลนำเข้า

2 100000 993754689
58683 3478
28489 48682814
1
28482 39599461

ข้อมูลส่งออก

9265409

คำอธิบาย

มีผู้เข้าร่วม $3$ คน ณ เวลาที่การเปลี่ยนแปลงครั้งที่ $1$ สิ้นสุดลง ข้อมูลเกี่ยวกับผู้เข้าร่วมแต่ละคนเป็นดังนี้:

1. สวมป้ายหมายเลข $58683$ และเริ่มต้นจากจุด $58683$ เคลื่อนที่ตามเข็มนาฬิกาด้วยความเร็ว $28489$ ต่อ $1$ วินาที
2. สวมป้ายหมายเลข $3478$ และเริ่มต้นจากจุด $3478$ เคลื่อนที่ตามเข็มนาฬิกาด้วยความเร็ว $48682814$ ต่อ $1$ วินาที
3. สวมป้ายหมายเลข $28482$ และเริ่มต้นจากจุด $28482$ เคลื่อนที่ตามเข็มนาฬิกาด้วยความเร็ว $39599461$ ต่อ $1$ วินาที

สำหรับผู้เข้าร่วม ณ เวลาที่การเปลี่ยนแปลงครั้งที่ $1$ สิ้นสุดลง การชนกันระหว่างการแข่งขันมาราธอนจะเกิดขึ้น $967009272178$ ครั้ง ดังนั้น เศษเหลือจากการหารจำนวนครั้งของการชนกันที่เกิดขึ้นระหว่างการแข่งขันมาราธอนด้วย $1000000007$ คือ $9265409$

ตัวอย่างข้อมูลนำเข้านี้สอดคล้องกับเงื่อนไขของโจทย์ย่อยที่ $2, 3, 4, 5, 6$

ตัวอย่าง 4

ข้อมูลนำเข้า

7 100 100
34 12 46 23 57 63 99
12 34 23 12 34 12 23
5
67 34
99 23
33 34
99 12
23 12

ข้อมูลส่งออก

330
264
341
440
341

คำอธิบาย

ตัวอย่างข้อมูลนำเข้านี้สอดคล้องกับเงื่อนไขของโจทย์ย่อยที่ $3, 5, 6$