وصف المسألة

يعيش بيتارو حول بحيرة دائرية كبيرة. طول محيط البحيرة هو $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$.