Nanobugs

Time limit1sMemory limit1024 MB

Summary

Given n bugs that are each a spy or an agent, output equal-size chamber checks that prove the spy count is a rather than b, or print -1 if that is impossible.

Level: Medium6 of 10
Topics: Math, Implementation
Solved: No attempts yet

Problem

In this problem, for a collection of bugs where each bug is either a spy or an agent, you have to show the true number of spy bugs without disclosing any spy or agent.

Nanobugs are intelligent robots that obey the orders of their masters. They are usually busy spying, eavesdropping, or monitoring other nanobugs. All nanobugs look exactly the same.

Bartosz and Vivek are engineers at two corporations, Eastern Cartel and Southern Trading Company. They are examining the meeting room in the Eastern Cartel office, where representatives of both corporations will discuss a new contract. Together they have caught $n$ nanobugs. Each bug is either a security agent of Eastern Cartel or a spy of Southern Trading Company.

Anders is a security expert from SpyTek. His job today is to help Bartosz and Vivek determine how many spies and agents are among the caught nanobugs. For each bug, Anders knows whether it is a spy or an agent, but nobody else knows that.

Anders sees exactly $a$ spies among the bugs. Bartosz and Vivek have only learned through standard procedures that there are either $a$ or $b$ spies. The numbers $a$ and $b$ differ by exactly one. They have no other information about the bugs.

Nanobugs are expensive intelligent machines that value their incognito. Anders knows who the master of each bug is. But if the affiliation of a nanobug, meaning which company it works for, becomes known to the engineers or to other nanobugs, that nanobug's further functioning and its very existence are threatened.

As a security expert, Anders has a balance checker. It is a small box with two chambers and an indicator light. Anders places some nanobugs in each chamber and presses a button. For each corporation, the checker verifies that the number of its nanobugs is the same in both chambers. If this holds for both corporations, the light is green. Otherwise it is red.

Anders runs a series of checks. He starts by placing all nanobugs in a row in an order of his choice. In each check, he puts some nanobugs in the first chamber and some in the second, presses the button, shows the result to the engineers, and then returns all nanobugs to their places, restoring the original order. Throughout the series, the nanobugs are numbered from $1$ to $n$ by their places in the row.

Help Anders prove to the engineers that there are exactly $a$ spies among the $n$ nanobugs, without disclosing any nanobug's affiliation. If this is not possible, determine that it is impossible.

Input

The first line contains three integers $n$ , $a$ , and $b$ ( $20 \le n \le 50$ , $1 \le a, b \le 4$ , $|a - b| = 1$ ). Here $n$ is the total number of nanobugs. Bartosz and Vivek know that there are either $a$ or $b$ spies among them, and Anders has to prove that the exact number of spies is $a$ .

Output

On the first line, print one integer $m$ ( $0 \le m \le 1000$ ), the number of checks, or $-1$ if it is impossible to satisfy all conditions. If the answer is positive, print $m$ lines, one for each check.

Each check line has three parts. The first part lists the bugs placed in the first chamber: their count, followed by their numbers in any order. Then comes a character showing the result, '=' (ASCII 61) for a positive result (green light) or '^' (ASCII 94) for a negative result (red light). After that, the bugs placed in the second chamber are listed in the same format as the first chamber. Everything is printed on one line, and consecutive numbers or characters are separated by one or more spaces.

No bug can be mentioned twice in one check.

Hint

In the sample, the engineers know that among the 22 caught nanobugs there are either one or two spies. In fact there are exactly two, and Anders must prove it. The answer uses four checks.

The first check shows that the first six bugs contain as many spies as the next six bugs. The same holds for agents, because both chambers have the same size. After the second check, the bugs numbered 13, 14, 15, 16, and 21 contain as many spies as the bugs numbered 17, 18, 19, 22, and 20. The third check shows that the number of spies among bugs 13, 14, and 17 differs from the number among bugs 6, 8, and 9. The fourth check gives no information, because a check with unequal chamber sizes always gives a negative result.

If there were exactly one spy, at least one of the checks would give a different result, so the number of spies must be two.

Examples1

Example 1

Input

22 2 1

Expected output

4
6 1 2 3 4 5 6 = 6 7 8 9 10 11 12
5 13 14 15 16 21 = 5 17 18 19 22 20
3 13 14 17 ^ 3 6 8 9
1 1 ^ 2 2 3