Hey, this looks oddly familiar...

After nearly two years of captivity inside of [REDACTED]'s torture chamber, hewmatt10 has finally been set free! Promising to be a better person without rebellious thoughts, he promptly returns to the remains of his bunker from years past and discovers a piece of treasure. One that he wouldn't let succumb to the horrors of what happened last time.

This valuable relic was none other than his trusty paintbrush and palette, which while hewmatt10 recognized was covered in ash and dust, was remarked by hewmatt10 as a brand-new piece of technology.

Not wanting any of his paintings to get stolen by past basement-dweller justinzhu ever again, hewmatt10 wants to digitalize his paintings and create an app where he could draw paintings on a virtual ~N~ row by ~M~ column canvas using ~P~ different types of paintbrushes.

This canvas is indexed with the co-ordinates ~(i,j)~ where ~(0 \le i < N)~ and ~(0 \le j < M)~, Point ~(0, 0)~ represents the top-left corner of the canvas. Initially, all points on the canvas have colour ~0~, representing no colour.

Each of hewmatt10's paintbrushes has a unique pattern to it, containing 1s and 0s in a length ~l_i~ and width ~w_i~ rectangle. For example, here is a ~l_i = 2~ and ~w_i = 3~ paintbrush where point ~(0, 1)~ is a 0, and all other points ~\{~~(0, 0), (0, 2), (1, 0), (1, 1), (1, 2)~~\}~ are a 1.

1 0 1
1 1 1

When painting on the canvas at a co-ordinate ~(i,j)~ using a specific paintbrush ~p_i~ and a specific colour ~c_i~, a 1 at any point ~(a, b)~ on the paintbrush means that the co-ordinate ~(i + a, j + b)~ should be painted to ~c_i~.

For example, if hewmatt10 started with a ~5~ by ~6~ canvas as follows:

0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

Using the above paintbrush at index ~(3, 1)~ with colour ~5~ would lead to the following canvas:

0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 5 0 5 0 0
0 5 5 5 0 0

Note that the following points, ~(3+0,1+0),(3+0,1+2),(3+1,1+0),(3+1,1+1),(3+1,1+2)~ were painted.

Using the same paintbrush again at index ~(3, 2)~ with colour ~4~ would lead to the following canvas:

0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 5 4 5 4 0
0 5 4 4 4 0

Wanting to paint a total of ~Q~ times, can you help hewmatt10 create a painting app?

Input Specification

On the first line, five space-separated integers ~N~, ~M~, ~P~, and ~Q~.

For each of the ~P~ paintbrushes, there will be a line containing two space-separated integers ~l_i~ and ~w_i~, representing the length and width of the ~i~th paintbrush. The next ~l_i~ lines will contain ~w_i~ space-separated integers, either a 1 or a 0, representing the pattern of that paintbrush.

The next ~Q~ lines contain four space-separated integers ~p_i~, ~c_i~, ~i~ and ~j~, meaning to paint the canvas at the co-ordinate ~(i,j)~, using the ~p_i~-th paintbrush and colour ~c_i~.

Output Specification

~N~ lines with ~M~ space-separated integers per line, representing the final canvas.

Constraints

~2 \le N, M \le 100, P \le 100,~ and ~Q \le 100~

~1 \le l_i \le N, 1 \le w_i \le M~

~0 \le p_i < P, 1 \le c_i \le 100~

~0 \le i \le N - l_i~

~0 \le j \le M - w_i~

Sample Input

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

Sample Output

0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 5 4 5 4 0
0 5 4 4 4 0