Alice has a grid of size m×n, with rows numbered from 1 to m from top to bottom, and columns numbered from 1 to n from left to right. The cell at the intersection of row i (1≤i≤m) and column j (1≤j≤n) is called cell (i,j). Initially, the entire grid is white (color 0). Alice performs k coloring operations as follows:
- She selects a rectangle within the grid, occupying a set of contiguous cells, and chooses a color c (1≤c<100);
- She then overwrites all cells within the selected rectangle to color c.
**Objective:** Given the grid dimensions m and n and a sequence of k coloring operations, determine the resulting color grid that Alice obtains.
### Input
- The first line contains three integers m, n, and k (m,n,k≤100);
- The s-th line (1≤s≤k) contains five integers xs,ys,us,vs,cs, where (xs,ys) and (us,vs) are the coordinates of the top-left and bottom-right corners of the selected rectangle for the s-th coloring operation, and cs is the color to fill that rectangle.
### Output
- The i-th line (1≤i≤m) in the next m lines contains n integers ai1,ai2,…,ain describing the colors in row i of Alice's color grid.
### Constraints
- 1≤n≤106.
- 0≤|ai|<106.
### Example
Input:
3321122222331
Output:
220211011