E. Efficient Packing
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Eva is preparing for an important space mission. Before launch, she needs to fit $$$n$$$ crates into the cargo container of a spacecraft. The container is an axis-aligned box with opposite corners $$$(0,0,0)$$$ and $$$(W,H,D)$$$. The $$$i$$$-th crate is a rectangular box with side lengths $$$w_i$$$, $$$h_i$$$, and $$$d_i$$$.

Each crate may be placed in any orientation in which its edges are parallel to the coordinate axes. All crates must lie inside the container, and their interiors must not overlap. They may touch each other and the walls of the container. A crate may be suspended in mid-air.

Find any valid crate arrangement with integer corner coordinates, or determine that none exists.

Input

The first line of input contains three integers $$$W$$$, $$$H$$$, and $$$D$$$, denoting the dimensions of the container ($$$1 \le W, H, D \le 10^9$$$).

The second line contains an integer $$$n$$$, denoting the number of crates ($$$1 \le n \le 4$$$).

The $$$i$$$-th of the following $$$n$$$ lines contains three integers $$$w_i$$$, $$$h_i$$$, and $$$d_i$$$, denoting the side lengths of the $$$i$$$-th crate ($$$1 \le w_i, h_i, d_i \le 10^9$$$).

Output

Print "NO" if no valid arrangement exists in which every crate has integer corner coordinates.

Otherwise, print "YES", followed by $$$n$$$ groups of six integers $$$x_1$$$, $$$y_1$$$, $$$z_1$$$, $$$x_2$$$, $$$y_2$$$, $$$z_2$$$. The $$$i$$$-th group gives the opposite corners $$$(x_1, y_1, z_1)$$$ and $$$(x_2, y_2, z_2)$$$ of the $$$i$$$-th crate ($$$0 \le x_1 \lt x_2 \le W$$$; $$$0 \le y_1 \lt y_2 \le H$$$; $$$0 \le z_1 \lt z_2 \le D$$$). The side lengths $$$x_2 - x_1$$$, $$$y_2 - y_1$$$, and $$$z_2 - z_1$$$ must equal $$$w_i$$$, $$$h_i$$$, and $$$d_i$$$ in some order.

If there are multiple answers, print any of them.

Examples
Input
7 7 7
3
1 1 1
1 1 1
1 1 1
Output
YES
1 1 1 2 2 2
3 3 3 4 4 4
5 5 5 6 6 6
Input
5 5 1
4
1 2 3
2 3 1
3 1 2
1 2 3
Output
YES
0 2 0 2 5 1
3 0 0 5 3 1
2 3 0 5 5 1
0 0 0 3 2 1
Input
9 10 11
2
6 6 6
6 6 6
Output
NO
Input
10 10 10
4
3 7 10
10 3 7
7 10 3
7 7 7
Output
YES
7 0 0 10 7 10
0 0 7 7 10 10
0 7 0 10 10 7
0 0 0 7 7 7