IOI '14 - Taipei, Taiwan

Place tiles on the floor

We have a ~2^n~ by ~2^n~ floor with ~4^n~ unit squares. Each square can be identified by its ~x~ and ~y~ coordinates (both from ~0~ to ~2^n-1~). We want to cover this floor with four types of ~2~ by ~2~ L-shaped tiles, as shown in the following figure. The tiles cannot overlap, and they can only be placed on the grid boundary. In addition, there is exactly a square that we cannot cover with tiles. Please find a way to cover the entire floor with tiles.

Example

In the following example we have ~n = 3~ and ~64~ squares. The blue square at ~(1, 6)~ cannot be covered by any tile. This figure shows a possible way to cover the floor. To identify a tile we will use the ~x~ and ~y~ coordinates. For example, the green tile in the figure can be identified by ~(6, 2)~, ~(7, 2)~, and ~(7, 3)~.

Statement

Write a program to cover the floor with tiles.

Input Specification

The input consists of one line with ~3~ integers ~n~, ~x~, and ~y~. ~n~ indicates that the size of the floor is ~2^n~ by ~2^n~. ~x~ and ~y~ are the coordinates of the square that cannot be covered with tiles.

Output Specification

The output should consist of a list of tile positions. Each line of the output should contain six space-separated integers ~x_1~, ~y_1~, ~x_2~, ~y_2~, ~x_3~, and ~y_3~ to describe the position of one tile. For example, if we want to place the green tile as the first tile, we can output the integers ~6~, ~2~, ~7~, ~2~, ~7~, and ~3~. The three squares of a tile can appear in any order, so we can also set them as ~7~, ~2~, ~7~, ~3~, ~6~, and ~2~. The tiles can also appear in any order.

Sample Input 1

1 0 0

Sample Output 1

0 1 1 0 1 1

Sample Input 2

1 1 0

Sample Output 2

0 0 0 1 1 1

Constraints

Subtask 1 [5%]

~n = 1~

Subtask 2 [15%]

~1 \le n \le 2~

Subtask 3 [20%]

~1 \le n \le 8~

~x = y = 0~

Subtask 4 [60%]

~1 \le n \le 8~