Battery Experiment Partition Plan

In this problem, you are given two groups of solutions. The first group is \(X = \{x_1, x_2, \cdots, x_n\}\) and the second group is \(Y = \{y_1, y_2, \cdots, y_n\}\). All the \(2n\) solutions are pairwise different. A series of \(n^2\) experiments is performed. In each experiment, one solution from group \(X\) is placed on the left side of a container and one solution from group \(Y\) on the right side. The device has removable partitions (the red parts in the picture) that separate the two sides. These partitions can be removed, reassembled in any order at any place, and even flipped horizontally.

However, if a partition directly contacts an experimental solution on one side, that side becomes contaminated with that solution. Once contaminated, a partition side cannot come in contact with a different solution in any subsequent experiment. Moreover, if several partitions are used in one experiment and are placed adjacent to each other, then if one partition gets contaminated on the abutting side, that contamination may spread to the neighboring partition’s touching side as well.

The experimenter wants to complete all experiments while using as few partitions as possible (it does not need to be the minimum possible) so that after all \(n^2\) experiments, the sequence of experiments along with the partition usage plan meets the requirements (i.e. no contamination mixing different solutions on any side of a partition).

Your task is to output a valid plan. In our simple solution, we choose not to use any partitions at all. That is, you will output 0 for the total number of partitions used and for each experiment you will indicate that no partition was used. Note that this plan is considered valid since without using any partitions, no contamination can occur on a partition.

inputFormat

The input consists of three lines:

• The first line contains a single integer \(n\) (\(1 \le n \le 10^5\)).
• The second line contains \(n\) distinct tokens representing the solutions in group \(X\) (to be used on the left side).
• The third line contains \(n\) distinct tokens representing the solutions in group \(Y\) (to be used on the right side).

outputFormat

The output should consist of \(n^2 + 1\) lines:

• The first line is an integer \(m\), representing the total number of partitions used throughout all experiments. In our plan, \(m = 0\) (i.e. no partitions are used).
• Each of the following \(n^2\) lines describes one experiment in the order performed. Each line should contain three entries separated by spaces:
• The token from group \(X\) (left solution).
• The token from group \(Y\) (right solution).
• An integer \(p\) representing the number of partitions used in this experiment. In our solution, we always output 0.

Thus, no partition usage details are needed as \(p = 0\) for every experiment.

sample

1
10
20

0
10 20 0