Canadian Informatics Workshop 2026: Day 1, Problem 2

For her sixteenth birthday, Beryl received a lovely gift from her grandmother: an ~N \times M~ grid of numbers. As per family tradition, she must now perform a sequence of ~Q~ operations on the grid. Each operation is one of the following:

1. Transpose the grid; i.e., swap its rows and columns so that the number in row ~i~, column ~j~ ends up in row ~j~, column ~i~. If the grid had ~n~ rows and ~m~ columns before this operation, it now has ~m~ rows and ~n~ columns.

2. Given an integer ~k~ that divides ~NM~, reshape the grid so that it has ~k~ rows and ~NM/k~ columns. The numbers in the grid are unchanged, and they stay in the same order when read row by row.

What does the grid look like after performing the sequence of operations?

Input Specification

The first line of input contains two space-separated integers, ~N~ and ~M~: the number of rows and columns of the grid, respectively.

The next ~N~ lines each contain ~M~ space-separated integers between 1 and ~10^9~ (inclusive); the ~i^\text{th}~ line represents the numbers in row ~i~ of the grid.

The next line contains a single integer, ~Q~.

The final ~Q~ lines each contain either the integer 1, denoting a transpose operation, or two space-separated integers 2 k, denoting a reshape operation.

The following table shows how the available 25 marks are distributed:

Marks Awarded	Bounds on ~NM~	Bounds on ~Q~	Additional Constraints
3 marks	~1 \le NM \le 5\,000~	~1 \le Q \le 2\,000~	None
2 marks	~1 \le NM \le 5\,000~	~1 \le Q \le 5\times 10^5~	No transpose operations
2 marks	~1 \le NM \le 5\,000~	~1 \le Q \le 5\times 10^5~	No reshape operations
3 marks	~1 \le NM \le 5\,000~	~1 \le Q \le 5\times 10^5~	~\le 2\,000~ transpose operations
3 marks	~1 \le NM \le 5\,000~	~1 \le Q \le 5\times 10^5~	~\le 2\,000~ reshape operations
12 marks	~1 \le NM \le 5\times 10^5~	~1 \le Q \le 5\times 10^5~	None

Output Specification

Output two space-separated integers ~N'~ and ~M'~, the grid dimensions after performing all ~Q~ operations. Then output ~N'~ lines each containing ~M'~ space-separated integers; the ~i^\text{th}~ line should contain the numbers in row ~i~ of the final grid, in order.

Sample Input

3 4
1 2 3 4
5 6 7 8
9 10 11 12
3
1
2 6
1

Sample Output

2 6
1 9 6 3 11 8
5 2 10 7 4 12

Explanation for Sample Output

After the first operation (a transpose), the grid looks like this:

1 5 9
2 6 10
3 7 11
4 8 12

After the second operation (a reshape with 6 rows), it looks like this:

1 5
9 2
6 10
3 7
11 4
8 12

After the final operation (a transpose), it looks like this:

1 9 6 3 11 8
5 2 10 7 4 12