في حفل افتتاح 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$. تصبح المسافة بين IOI-chan والمتسابق الأول $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$. تصبح المسافة بين IOI-chan والمتسابق الأول $3$، فينتقل المتسابق الأول إلى الإحداثي $3$. يقف المتسابقون الأول والثاني والثالث عند الإحداثيات $3$ و$-2$ و$-3$ على الترتيب. ولأن IOI-chan والمتسابق الأول موجودان في المجال $[2,4]$، نطبع 2 للسؤال الرابع.
• عند الزمن $5$، تنتقل IOI-chan إلى الإحداثي $5$. لا يتحرك أي متسابق؛ فيقف المتسابقون الأول والثاني والثالث عند الإحداثيات $3$ و$-2$ و$-3$ على الترتيب. ولأن المتسابق الأول وحده في المجال $[2,4]$، نطبع 1 للسؤال الخامس.
• عند الزمن $6$، تنتقل IOI-chan إلى الإحداثي $6$. تصبح المسافة بين IOI-chan والمتسابق الأول $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