Telejump

Time limit1sMemory limit128 MB

Summary
Given a type-1 jumps, b type-2 jumps, and c type-3 jumps with n = a+b+c+1, output a route visiting planets 0 through n-1 exactly once using every ticket exactly once.
Level

Medium6 of 10

Topics
Greedy, Implementation, Math
Solved
No attempts yet

Problem

Hongjun and friends plan to visit nn planets numbered 00 through n−1n-1. They teleport with the Telejump system co-developed by Sasung and Boogle, starting at planet 00 and ending anywhere.

Three ticket types are available.

  • Type 1: move from xx to x+1x+1 or x−1x-1 when inside the range
  • Type 2: move from xx to x+2x+2 or x−2x-2 when inside the range
  • Type 3: move from xx to x+3x+3 or x−3x-3 when inside the range

They hold aa type-1 tickets, bb type-2 tickets, and cc type-3 tickets, with a+b+c+1=na+b+c+1=n. Each count is at least 33, so n≥10n \ge 10.

Output a visit order that uses every planet exactly once and every ticket exactly once.

Input

The first line contains TT (1≤T≤201 \le T \le 20), the number of test cases.

Each test case is one line with three integers aa, bb, and cc (3≤a,b,c≤50003 \le a,b,c \le 5000). For that case, n=a+b+c+1n=a+b+c+1.

Output

For each test case, print one line with nn planet numbers separated by spaces. The route must start at planet 00.

If multiple routes are valid, print any of them. Every input is guaranteed to be solvable.

Hint

Use length-3 jumps to cover large gaps, then spend the remaining type-1 and type-2 tickets on unvisited planets. When a=b=ca=b=c, a repeating three-ticket pattern visits the whole line in order.

Examples3

  1. Example 1

    Input
    2
    3 3 3
    3 4 3
    
    Expected output
    0 3 1 2 5 4 6 9 7 8
    0 3 1 2 5 4 6 9 7 8 10
    
  2. Example 2

    Input
    1
    3 3 3
    
    Expected output
    0 3 1 2 5 4 6 9 7 8
    
  3. Example 3

    Input
    1
    3 4 3
    
    Expected output
    0 3 1 2 5 4 6 9 7 8 10