- محدودیت زمان: ۲ ثانیه
- محدودیت حافظه: ۵۱۲ مگابایت
آی مجری که به فکر بچهها است، میخواهد برای فامیل دور(که فردا بیشتر با او آشنا میشوید) تولد بگیرد. او با دیدن در به وجد میآید. آی مجری برای تولد او یک فضا طراحی کرده است که در آن \(n\) در پشت سر هم قرار دارند. در ورای در \(i\)م، \(a_i\) در دیده میشود. برای روز تولد فامیل، آي مجری \(m\) برنامه دارد. در هر برنامه او به فامیل سه عدد \(l\) و \(r\) و \(k\) میدهد که به این معنی است که فامیل میتواند از در \(l\)م شروع کرده و آنرا باز کند و سپس به \(k\) در جلوتر رفته و آن را باز کند و همینطور ادامه دهد تا به در \(r\)م برسد. مقدار خوشحالی فامیل در هر برنامه برابر تعداد در هاییست که در ورای در های بازشده میبیند. آی مجری میخواهد تولد به یاد ماندنیای برای فامیل تدارک ببیند. برای همین شما باید به او کمک کنید تا بداند در هر برنامه چقدر فامیل خوشحال میشود.
ورودی
در سطر اول ورودی دو عدد طبیعی \(n\) و \(m\) آمدهاست، که نشاندهندهی تعداد در های اولیه و تعداد برنامههای روز تولد است.
در سطر دوم \(n\) عدد میآید که عدد \(i\)م نشاندهندهی \(a_i\) است.
در \(m\) سطر بعدی در هر سطر سه عدد \(l\) و \(r\) و \(k\) میآید که نمایانگر یک برنامه هستند. تضمین میشود که \(r - l\) بر \(k\) بخشپذیر است. \[1 \le a_i \le 10^9\]
\[1 \le l \le r \le n \le 100\ 000\]
\[1 \le k \le n \le 100\ 000\]
\[1 \le m \le 300\ 000\]
خروجی
خروجی شامل \(m\) عدد است که عدد \(i\)م نمایانگر مقدار خوشحالی فامیل دور در برنامهی\(i\)م است.
مثال
ورودی نمونه
5 5
1 2 3 4 5
1 5 1
1 5 2
1 4 3
1 5 4
1 1 5
خروجی نمونه
15
9
5
6
1