posted 1 year ago

You work for a large company, and your job is to design sorting devices. Devices are built from:

n inputs,

n outputs,

gates which have two inputs and send to output the minimum ("min gates") or maximum ("max gates") of the two numbers given at their input,

connecting wires.

You are competing in a bid for a Bytelandian Ministry of Information contract to design the smallest possible device (in terms of the number of gates) which sorts any input. Each device will go through a rigorous test process on a number of data sets. However, through some Good Friends in High Places you have managed to acquire some additional information concerning the exact data sets (permutations) your device will be tested on. Make use of this, and of course your superior programming skills, to win the bid!

Input

First, two numbers, 2≤n≤20, 1≤k≤1000, the number of inputs and the number of different permutations for which your device will be tested. The next k lines contain permutations of the numbers 1 .. n.

Output

First, output p, the number of gates in your device (0≤p≤106). The next p lines should contain definitions of the gates used, in the form of a pair of integers, xi,yi, and exactly one of the strings "min" or "max". To be able to use the output of a gate as the input of a subsequent gate, we use the following convention. First of all, the range for inputs xi and yi is as follows: 1 ≤ xi,yi < n+p. The output of the i-th gate is assumed to be input n+i.

Finally, a sequence of exactly n integers in the range 1..n+p should follow, describing which of the "inputs" should be hard-wired to successive outputs of the device.

Scoring

If your program does not produce a sorting machine which works for every input (sorting it in ascending order), it will be deemed incorrect. Otherwise, you will score p penalty points for each test case solved.

Example

Input:

3 2

1 2 3

1 3 2

Output:

2

2 3 min

2 3 max

1 4 5

Score:

0.5

n inputs,

n outputs,

gates which have two inputs and send to output the minimum ("min gates") or maximum ("max gates") of the two numbers given at their input,

connecting wires.

You are competing in a bid for a Bytelandian Ministry of Information contract to design the smallest possible device (in terms of the number of gates) which sorts any input. Each device will go through a rigorous test process on a number of data sets. However, through some Good Friends in High Places you have managed to acquire some additional information concerning the exact data sets (permutations) your device will be tested on. Make use of this, and of course your superior programming skills, to win the bid!

Input

First, two numbers, 2≤n≤20, 1≤k≤1000, the number of inputs and the number of different permutations for which your device will be tested. The next k lines contain permutations of the numbers 1 .. n.

Output

First, output p, the number of gates in your device (0≤p≤106). The next p lines should contain definitions of the gates used, in the form of a pair of integers, xi,yi, and exactly one of the strings "min" or "max". To be able to use the output of a gate as the input of a subsequent gate, we use the following convention. First of all, the range for inputs xi and yi is as follows: 1 ≤ xi,yi < n+p. The output of the i-th gate is assumed to be input n+i.

Finally, a sequence of exactly n integers in the range 1..n+p should follow, describing which of the "inputs" should be hard-wired to successive outputs of the device.

Scoring

If your program does not produce a sorting machine which works for every input (sorting it in ascending order), it will be deemed incorrect. Otherwise, you will score p penalty points for each test case solved.

Example

Input:

3 2

1 2 3

1 3 2

Output:

2

2 3 min

2 3 max

1 4 5

Score:

0.5

Try to enjoy your work while doing it,it will Automatically convert in Hard Work...

posted 1 year ago

That's not a very helpful question. If we were to take it literally we would have to deconstruct the entire question and explain it in horrible detail. For example the word "you" at the beginning of the question: we would have to explain the context behind the word and what it actually applies to in real life. And so on.

But I suspect you already know what "you" means in that context and what it refers to. So saying that you don't understand the question is inaccurate, for obviously you do understand some parts of it. So your job here is to identify parts of the question which you don't understand and point to those parts.

But I suspect you already know what "you" means in that context and what it refers to. So saying that you don't understand the question is inaccurate, for obviously you do understand some parts of it. So your job here is to identify parts of the question which you don't understand and point to those parts.

Consider Paul's rocket mass heater. |