Under construction

Still being built. Things may change

Binary Table

Time limit2sMemory limit512 MB

Summary
Given n shuffled row values and the corner sum X, find X among the n+1 numbers and rebuild the 0/1 table, or report if it is not unique.
Level

Medium7 of 10

Topics
Math, Bit manipulation, Implementation
Solved
No attempts yet

Problem

Kipa received an nn by nn table filled with 0s and 1s as a gift from Yul. Kipa liked the gift so much that Kipa wrote, to the right of each row, the value of that row read as a binary number and converted to decimal. In the same way, Kipa wrote below each column the value of that column read as a binary number, and wrote the sum of all those values in the bottom-right corner.

Then Minti took the table. Minti told Kipa the (n+1)(n+1) numbers in the rightmost column, in shuffled order, and then burned Kipa's precious table!

Kipa worked out which of the numbers Minti gave is XX, the one in the bottom-right corner. But Kipa is too sad to continue. Can you do this for Kipa?

Input

The first line contains a positive integer nn at most 10310^3 and a positive integer XX less than 1032010^{320}.

From the second line, nn lines follow. Each contains one of the (n+1)(n+1) numbers Minti gave, excluding XX. Each number is a positive integer, the numbers are distinct, and each is less than 2n2n.

All numbers are given in decimal.

Output

If the given information determines the table uniquely, print the original nn by nn table without spaces. Otherwise, print kipa so sad :(.

Hint

For the first input, the table below can be built, and it is unique.

1015
1004
1117
71513

Examples2

  1. Example 1

    Input
    3 13
    7
    4
    5
    
    Expected output
    101
    100
    111
    
  2. Example 2

    Input
    3 9
    7
    4
    5
    
    Expected output
    kipa so sad :(