תיאור הבעיה

ביטארו גר סביב אגם עגול וגדול. היקף האגם הוא $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$.