Подвижная матрица

Вам задана бинарная матрица MM, состоящая из nn строк и mm столбцов. Обработайте qq запросов двух видов:

  • r i k – циклически сдвинуть ii-ю строку матрицы на kk элементов вправо.
  • с j k – циклически сдвинуть jj-й столбец матрицы на kk элементов вниз.

Выведите матрицу MM после применения всех запросов.

Входные данные

В первой строке записаны числа nn и mm – число строк и столбцов в матрице соответственно (1n,m; nm2105)(1 \le n, m;\ n \cdot m \le 2 \cdot 10^5).

В каждой из следующих nn строк записано по mm чисел – очередная строка матрицы.

В следующей строке записано число qq – количество запросов (1q21051 \le q \le 2 \cdot 10^5).

Следующие qq строк содержат запросы в формате из условия задачи (1km1 \le k \le m при запросе типа r, иначе 1kn1 \le k \le n).

Выходные данные

Выведите матрицу MM после применения всех запросов в таком же формате, в котором она дана во входных данных.

Подзадачи

баллынеобх. подзадачиограничения
1

15

-

n,m50;q1000n, m \le 50; q \le 1000

2

23

-

Только запросы типа c

3

62

1, 2

Нет доп. ограничений

STDINSTDOUT
3 3
101
001
111
2
r 2 2
c 3 1
101
011
110