Rùa 🐢 đi làm thêm tại một cánh đồng có \(N\) hàng và \(M\) cột, có số hàng được đánh số từ \(1→N\) từ trên xuống dưới và có số cột được đánh số từ \(1→M\) từ trái sang phải. Nhiệm vụ của Rùa là gieo hạt vào những ô trong cánh đồng này.

Rùa 🐢 có một chiến thuật gieo hạt như sau: mỗi lần gieo thứ \(i\), đầu tiên chọn hai ô \((a_i, b_i)\) là ô bắt đầu và ô \((c_i, d_i)\) là ô kết thúc và cậu chọn thêm một số \(x_i\) là số hạt thóc sẽ gieo trong mỗi ô. Cậu sẽ rải theo đường ziczac, đầu tiên từ \((a_i, b_i)\) lần lượt rải từng ô và đi sang phải đến khi đụng ô cuối cùng trong hàng, cậu đi xuống một hàng và lần lượt rải sang trái cho đến khi đụng ô đầu tiên của hàng bên dưới, cậu lại xuống một hàng và rải sang phải,... cho đến khi cậu rải xong ô cuối cùng là \((c_i, d_i)\).

*Ví dụ thứ tự rải cho $N=5, M=4$ và $a_i=2, b_i=2, c_i=4, d_i=3$*

Trong khi gieo hạt, Rùa quên ghi chép lại số liệu nên hiện tại không biết số hạt mỗi ô trên cánh đồng. Cho thông tin những lần gieo hạt của Rùa, hãy giúp Rùa đếm số hạt thóc mỗi ô trong cánh đồng cuối cùng có được.

Input

• Dòng đầu tiên chứa hai số nguyên lần lượt là \(N\) và \(M\) \((1 \leq N, M \leq 10^3)\)
• Dòng tiếp theo chứa một số nguyên \(Q\), là số lần Rùa gieo thóc \((1 \leq Q \leq 2*10^5)\)
• \(Q\) dòng tiếp theo chứa năm số nguyên dương, dòng thứ \(i\) chứa lần lượt là \(a_i, b_i, c_i, d_i, x_i\) \((1 \leq a_i \leq c_i \leq N)\), \((1 \leq b_i, d_i \leq M)\), \((1 \leq x_i \leq 10^9)\). Với \((a_i, b_i)\) là ô bắt đầu và \((c_i, d_i)\) là ô kết thúc.

Dữ liệu đầu vào đảm bảo nếu \(a_i = c_i\) thì \(b_i \leq d_i\)

Output

• In ra \(N\) dòng, dòng thứ \(i\) in ra \(M\) số nguyên. Với dòng \(i\), số thứ \(j\) là số thóc ở ô tương ứng trên cánh đồng.

Example

Test 1

Input

3 4
3
1 1 2 2 1
3 3 3 4 2
2 3 3 3 3

Output

1 1 1 1
0 1 4 4
0 0 5 5

Note