Need for sum thing
Нехай є трикутна таблиця з N рядків. Перший рядок таблиці складається з одного елементу, другий рядк — з трьох, третій — з п'яти і т.д. i-тий рядок складається з 2i-1 елементів. Середні елементи усіх рядків утворюють один стовпець. Таким чином, таблиця являє собою рівнобедрений прямокутний трикутник. У верхньому елементі таблиці знаходиться прямий кутл, а у нижньому рядку — гіпотенуза.
Кожен елемент таблиці — деяка цифра від '0' до '9'.
Потрібно відповісти на Q запитів суми усіх елементів деякої трикутної області заданої таблиці. Кожен запит має вид:
r_i, c_i, k_i
Область i-того запиту являє собою рівносторонній прямокутний трикутник з k_i рядків з вершиною у (r_i, c_i):
Перший рядок складається з елементу (r_i, c_i). Другий рядок — з трьох елементів: (r_i+1, c_i), (r_i+1, c_i+1), (r_i+1, c_i+2), третій з п'яти і т.д.
Потрібно знайти суму усіх елементів трикутника з запиту.
Оскільки запитів багато, вони генерються програмно:
A_1 = 1
A_i = (1234567·A_{i-1} + 7654321) mod 1000000007, при 2 ≤ i ≤ Q
r_i = A_i mod N + 1
c_i = A_i mod (2r_{i }- 1) + 1
k_i = A_i mod (n - r_{i }+ 1) + 1
Вхідні дані
У першому рядку N і Q — кількість рядків заданого трикутника та кількість запитів. Далі у N рядках йде опис таблиці. У i-тому з них рівно 2i-1 цифр — елементи таблиці (між цифрами немає пропусків).
Вихідні дані
Оскільки запитів багато, виведіть одне число — суму усіх відповідей на запити.
Обмеження
1 ≤ N ≤ 10^3
0 ≤ Q ≤ 5·10^6
^{ }Пояснення
Заданий трикутник:
Перший запит: , сума 24.
Другий запит: 8, сума 8.
Третій запит: 6, сума 6.
Четвертий запит: 1, сума 1.
П'ятий запит: 3, сума 3.