This page is still under construction.

Parts of this page are still being built. What you see may change.

On a Distant Amazon

Time limit2sMemory limit256 MB

Summary
Given n women, construct a mother-daughter forest where exactly a women have at least one daughter and exactly b are someone's daughter, or report impossible.
Level

Medium6 of 10

Topics
Graph, Greedy, Tree, Implementation
Solved
No attempts yet

Problem

Programmer Gosha likes to read fairy tales to his children at bedtime. One day the tale he decided to read began like this:

"In a distant village in the valley of the Amazon River lives a tribe in which there is not a single man. Four women live in this village: three mothers and three daughters."

Gosha's children found this passage suspicious, and he had to quickly explain how four people could include three mothers and three daughters at the same time.

Assuming that the tale may later describe other villages, Gosha wants to learn how to quickly construct an example of a tribe with exactly n women in which a of the women are the mother of someone in the tribe and b of the women are the daughter of someone in the tribe.

Help him quickly come up with an example of such a tribe for given n, a, and b.

Input

The first line contains an integer T (1 ≤ T ≤ 104), the number of test cases. Each of the next T lines contains three positive integers: n, a, and b. (1 ≤ n, a, b ≤ 105)

The sum of all values of n in the input does not exceed 105.

Output

For each of the T test cases, output "IMPOSSIBLE" if the required tribe does not exist. If the tribe exists, output a description of the tribe in n lines. Number all members of the tribe from 1 to n. In the i-th line, output first the number k, the number of daughters of the i-th woman, followed by k numbers, the indices of her daughters. Each woman can have at most one mother.

If there are several valid answers, output any of them. Naturally, a mother is always older than her daughter, so the tribe must allow a way to assign ages to all the women such that this rule holds.

Examples1

  1. Example 1

    Input
    3
    3 1 2
    3 2 1
    5 2 4
    
    Expected output
    2 2 3
    0
    0
    IMPOSSIBLE
    0
    2 1 3
    2 4 5
    0
    0