eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Need for sum thing

Need for sum thing

Ліміт часу 2 секунди
Ліміт використання пам'яті 256 MiB

Нехай є трикутна таблиця з 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 iQ

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 цифр — елементи таблиці (між цифрами немає пропусків).

Вихідні дані

Оскільки запитів багато, виведіть одне число — суму усіх відповідей на запити.

Обмеження

1N10^3

0Q5·10^6

^{ }Пояснення

Заданий трикутник:

Перший запит: , сума 24.

Другий запит: 8, сума 8.

Третій запит: 6, сума 6.

Четвертий запит: 1, сума 1.

П'ятий запит: 3, сума 3.

Приклад

Вхідні дані #1
3 5
1
234
56789
Вихідні дані #1
42