У нас є сітка з \(N\) рядків і \(M\) стовпців. Квадрат (\(i,j\)) в \(i\)-му рядку зверху та \(j\)-му стовпці зліва має ціле число \((i-1) \times M + j\), яке написане на ньому.

Виконаємо на цій сітці наступну операцію.

• Для кожного квадрата (\(i,j\)) такого, що \(i+j\) є непарним, замініть ціле число в цьому квадраті на 0.

Дайте відповіді на \(Q\) запитань після операції. \(І\)-те питання звучить так:

• Знайдіть суму цілих чисел, записаних у всіх квадратах (\(p,q\)), які задовольняють усі наведені нижче умови, за модулем 998244353.
• \(A_i \le p \le B_i\).
• \(C_i \le q \le D_i\).

Обмеження

• Усі значення у вхідних даних є цілими числами.
• \(1 \le N,M \le 10^9\)
• \(1 \le Q \le 2 \times 10^5\)
• \(1 \le A_i \le B_i \le N\)
• \(1 \le C_i \le D_i \le M\)

Формат вхідних даних

Перший рядок містить цілі числа \(N,M\)

Наступний  рядок містить \(Q\)

Наступні  \(Q\) рядків містять цілі числа \(A_i, B_i, C_i, D_i\)

Числа у рядках розділяються пропуском.

Формат вихідних даних

У вихідний потік виведіть \(Q\) рядків. У \(i\)-му рядку має бути ціле число - відповідь на \(i\)-те запитання.

Примітка

До прикладу 1:

Сітку в цьому вхідному файлі показано нижче.

Цей вхід містить шість питань.

• Відповідь на перше запитання: 0+3+0+6+0+8+0+11+0=28.
• Відповідь на друге запитання: 1+0+9+0+17=27.
• Відповідь на третє запитання: 17+0+19+0=36.
• Відповідь на четверте запитання – 14.
• Відповідь на п'яте питання - 0.
• Відповідь на шосте питання 104.

Приклад вхідних даних

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

Приклад вихідних даних

28
27
36
14
0
104

Приклад вхідних даних

1000000000 1000000000
3
1000000000 1000000000 1000000000 1000000000
165997482 306594988 719483261 992306147
1 1000000000 1 1000000000

Приклад вихідних даних

716070898
240994972
536839100

Приклад вхідних даних

999999999 999999999
3
999999999 999999999 999999999 999999999
216499784 840031647 84657913 415448790
1 999999999 1 999999999

Приклад вихідних даних

712559605
648737448
540261130