בטקס הפתיחה של IOI 2018 צועדים $N$ מתחרים בטור לאורך ישר המספרים. כל המתחרים פונים לכיוון החיובי של הישר. בזמן $0$, המתחרה ה־$i$ ($1 \le i \le N$, בספירה מראש הטור) עומד בקואורדינטה $-i$. בנוסף, נושאת הדגל IOI-chan עומדת בקואורדינטה $0$.

לכל מתחרה יש ערך הנקרא איטיות. איטיותו של המתחרה ה־$i$ היא $D_i$. המתחרים פועלים לפי הכלל הבא:

• אם המרחק בין המתחרה ה־$i$ לבין האדם שמיד לפניו (מתחרה או IOI-chan) הוא לפחות $D_i+1$, המתחרה ה־$i$ עובר למיקום במרחק $1$ מאותו אדם. אחרת, המתחרה ה־$i$ אינו זז.

IOI-chan נעה מרחק $1$ בכיוון החיובי של הישר בכל יחידת זמן. כל מתחרה זז באופן מיידי בכל פעם שהתנאי שתואר לעיל מתקיים.

אתם כתבים המסקרים את טקס הפתיחה. הייתם אמורים לצלם תמונות, אבל ישנתם שינה עמוקה לאורך כל הטקס. לא נותרה ברירה — החלטתם לרמות באמצעות צילום האולם וציור האנשים על גבי התמונות.

כדי שלא יגלו שרימיתם, או כדי להעריך את הזמן הדרוש לציור, ברצונכם לדעת את $Q$ הערכים הבאים:

• מספר האנשים העומדים בקואורדינטות שבין $L_j$ ל־$R_j$, כולל הקצוות, בזמן $T_j$ ($1 \le j \le Q$).

משימה

נתונות האיטיות של כל מתחרה והנתונים של $Q$ השאלות. כתבו תוכנית המחשבת לכל שאלה את מספר האנשים המקיימים את התנאי.

קלט

קראו את הנתונים הבאים מהקלט הסטנדרטי.

• השורה הראשונה מכילה שני מספרים שלמים $N$ ו־$Q$, המופרדים ברווח. פירושם שיש $N$ מתחרים (ללא IOI-chan) ו־$Q$ שאלות.
• השורה ה־$i$ ($1 \le i \le N$) מבין $N$ השורות הבאות מכילה מספר שלם $D_i$. פירושו שאיטיותו של המתחרה ה־$i$ מראש הטור היא $D_i$.
• השורה ה־$j$ ($1 \le j \le Q$) מבין $Q$ השורות הבאות מכילה שלושה מספרים שלמים $T_j$, $L_j$ ו־$R_j$, המופרדים ברווחים. ערכים אלה מייצגים את השאלה ה־$j$.

פלט

הדפיסו $Q$ שורות לפלט הסטנדרטי. השורה ה־$j$ ($1 \le j \le Q$) צריכה להכיל את התשובה לשאלה ה־$j$.

מגבלות

כל נתוני הקלט מקיימים את התנאים הבאים.

• $1 \le N \le 500\,000$.
• $1 \le Q \le 500\,000$.
• $1 \le D_i \le 1\,000\,000\,000$ ($1 \le i \le N$).
• $1 \le T_j \le 1\,000\,000\,000$ ($1 \le j \le Q$).
• $1 \le L_j \le R_j \le 1\,000\,000\,000$ ($1 \le j \le Q$).

תתי־משימות

יש 3 תתי־משימות. הניקוד והמגבלות הנוספות של כל תת־משימה הם כדלקמן:

תת־משימה 1 [7 נקודות]

• $D_i=1$ ($1 \le i \le N$).

תת־משימה 2 [12 נקודות]

• $N \le 1\,000$.
• $Q \le 1\,000$.
• $T_j \le 1\,000$ ($1 \le j \le Q$).
• $1 \le L_j \le R_j \le 1\,000$ ($1 \le j \le Q$).

תת־משימה 3 [81 נקודות]

אין מגבלות נוספות.

דוגמאות

קלט 1

3 6
2
5
3
1 2 4
2 2 4
3 2 4
4 2 4
5 2 4
6 2 4

פלט 1

0
1
1
2
1
2

הסבר

בדוגמה זו המתחרים ו־IOI-chan נעים באופן הבא.

בהמשך, הקטע $[L,R]$ מציין את קבוצת הנקודות על ישר המספרים שהקואורדינטות שלהן בין $L$ ל־$R$, כולל הקצוות.

• בזמן $0$, IOI-chan עומדת בקואורדינטה $0$. המתחרים הראשון, השני והשלישי עומדים בקואורדינטות $-1$, $-2$ ו־$-3$, בהתאמה.
• בזמן $1$, IOI-chan נעה לקואורדינטה $1$. אף מתחרה אינו זז; המתחרים הראשון, השני והשלישי עומדים בקואורדינטות $-1$, $-2$ ו־$-3$, בהתאמה. מכיוון שאין אנשים בקטע $[2,4]$, יש להדפיס 0 כתשובה לשאלה הראשונה.
• בזמן $2$, IOI-chan נעה לקואורדינטה $2$. המרחק בינה לבין המתחרה הראשון הוא כעת $3$, ולכן המתחרה הראשון עובר לקואורדינטה $1$. המתחרים הראשון, השני והשלישי עומדים בקואורדינטות $1$, $-2$ ו־$-3$, בהתאמה. מכיוון שרק IOI-chan נמצאת בקטע $[2,4]$, יש להדפיס 1 כתשובה לשאלה השנייה.
• בזמן $3$, IOI-chan נעה לקואורדינטה $3$. אף מתחרה אינו זז; המתחרים הראשון, השני והשלישי עומדים בקואורדינטות $1$, $-2$ ו־$-3$, בהתאמה. מכיוון שרק IOI-chan נמצאת בקטע $[2,4]$, יש להדפיס 1 כתשובה לשאלה השלישית.
• בזמן $4$, IOI-chan נעה לקואורדינטה $4$. המרחק בינה לבין המתחרה הראשון הוא כעת $3$, ולכן המתחרה הראשון עובר לקואורדינטה $3$. המתחרים הראשון, השני והשלישי עומדים בקואורדינטות $3$, $-2$ ו־$-3$, בהתאמה. מכיוון ש־IOI-chan והמתחרה הראשון נמצאים בקטע $[2,4]$, יש להדפיס 2 כתשובה לשאלה הרביעית.
• בזמן $5$, IOI-chan נעה לקואורדינטה $5$. אף מתחרה אינו זז; המתחרים הראשון, השני והשלישי עומדים בקואורדינטות $3$, $-2$ ו־$-3$, בהתאמה. מכיוון שרק המתחרה הראשון נמצא בקטע $[2,4]$, יש להדפיס 1 כתשובה לשאלה החמישית.
• בזמן $6$, IOI-chan נעה לקואורדינטה $6$. המרחק בינה לבין המתחרה הראשון הוא כעת $3$, ולכן המתחרה הראשון עובר לקואורדינטה $5$. כעת המרחק בין המתחרה הראשון לשני הוא $7$, ולכן המתחרה השני עובר לקואורדינטה $4$. בנוסף, המרחק בין המתחרה השני לשלישי הוא כעת $7$, ולכן המתחרה השלישי עובר לקואורדינטה $3$. המתחרים הראשון, השני והשלישי עומדים בקואורדינטות $5$, $4$ ו־$3$, בהתאמה. מכיוון שהמתחרים השני והשלישי נמצאים בקטע $[2,4]$, יש להדפיס 2 כתשובה לשאלה השישית.

קלט 2

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

פלט 2

2
0

הסבר

דוגמת קלט זו מקיימת את המגבלות של תת־משימה 1.

קלט 3

6 6
11
36
28
80
98
66
36 29 33
190 171 210
18 20 100
1000 900 1100
92 87 99
200 100 300

פלט 3

1
6
0
5
2
7