Integral Pyramid

Interview

Time limit2sMemory limit512 MB

Summary
Given n and x, decide whether positive integers can fill the bottom row of Pascal-style sums so the single top cell equals x, and print a valid pyramid.
Level

Medium6 of 10

Topics
Combinatorics, Math, Greedy, Backtracking
Solved
No attempts yet

Problem

Pascal's triangle is a marvel of the combinatorial world, and what's more you can easily build one for yourself at home.

The lowest row has n numbers. The next row is staggered and has n − 1 numbers, where the ith is the sum of the ith and the i + 1th on the previous row.

You can choose any positive integers for the lowest row, but the single cell on the top row needs to be equal to a given x. Is this possible?

Input

  • The only line contains the number of rows, n (1 ≤ n ≤ 20), and the value needed at the top, x (1 ≤ x ≤ 109).

Output

If a pyramid can be constructed, output all of the numbers on each row, starting from the top. Every number must be greater than or equal to 1.

Otherwise, output impossible.

Examples3

  1. Example 1

    Input
    3 15
    Expected output
    15
8 7
3 5 2

  2. Example 2

    Input
    6 789
    Expected output
    789
394 395
209 185 210
117 92 93 117
70 47 45 48 69
45 25 22 23 25 44

  3. Example 3

    Input
    20 1
    Expected output
    impossible