K. Matrix Operations
time limit per test
15 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Given an $$$n \times n$$$ matrix where each element $$$a_{i,j}$$$ $$$(1 \le i, j \le n)$$$ in the matrix is $$$0$$$ initailly, you are asked to successively perform $$$n$$$ groups of operations on the matrix.

For each group of operations, you are given six parameters $$$x$$$, $$$y$$$, $$$z_1$$$, $$$z_2$$$, $$$z_3$$$ and $$$z_4$$$ and need to do the following operations in order:

  1. Find the maximum element among $$$a_{i,j}$$$ $$$(1 \le i \lt x, 1 \le j \lt y)$$$, denoted by $$$w_1$$$;
  2. Find the maximum element among $$$a_{i,j}$$$ $$$(1 \le i \lt x, y \le j \le n)$$$, denoted by $$$w_2$$$;
  3. Find the maximum element among $$$a_{i,j}$$$ $$$(x \le i \le n, 1 \le j \lt y)$$$, denoted by $$$w_3$$$;
  4. Find the maximum element among $$$a_{i,j}$$$ $$$(x \le i \le n, y \le j \le n)$$$, denoted by $$$w_4$$$;
  5. Increase each element $$$a_{i,j}$$$ $$$(1 \le i \lt x, 1 \le j \lt y)$$$ by $$$z_1$$$;
  6. Increase each element $$$a_{i,j}$$$ $$$(1 \le i \lt x, y \le j \le n)$$$ by $$$z_2$$$;
  7. Increase each element $$$a_{i,j}$$$ $$$(x \le i \le n, 1 \le j \lt y)$$$ by $$$z_3$$$;
  8. Increase each element $$$a_{i,j}$$$ $$$(x \le i \le n, y \le j \le n)$$$ by $$$z_4$$$.

After performing each group of operations, you need to output the values of $$$w_1$$$, $$$w_2$$$, $$$w_3$$$ and $$$w_4$$$.

Input

The first line contains an integer $$$n$$$ $$$(2 \le n \le 10^5)$$$, indicating the number of rows as well as columns in the matrix as well as the number of groups of operations.

Then follow $$$n$$$ lines, each of which contains contains six integers $$$x$$$, $$$y$$$ $$$(1 \lt x, y \le n)$$$, $$$z_1$$$, $$$z_2$$$, $$$z_3$$$ and $$$z_4$$$ $$$(1\le z_1, z_2, z_3, z_4\le 10^9)$$$, indicating the parameters of a group of operations as described above.

Output

For each operation, output a line containing four integers, indicating the values of $$$w_1$$$, $$$w_2$$$, $$$w_3$$$ and $$$w_4$$$.

Example
Input
3
3 3 1 2 3 4
2 3 1 2 3 4
3 2 1 2 3 4
Output
0 0 0 0
1 2 3 4
4 6 6 8