Gardens by the Bay is a large nature park in Singapore. In the park there are towers, known as supertrees. These towers are labelled to . We would like to construct a set of **zero or more** bridges. Each bridge connects a pair of distinct towers and may be traversed in **either** direction. No two bridges should connect the same pair of towers.

A path from tower to tower is a sequence of one or more towers such that:

- the first element of the sequence is ,
- the last element of the sequence is ,
- all elements of the sequence are
**distinct**, and - each two consecutive elements (towers) in the sequence are connected by a bridge.

Note that by definition there is exactly one path from a tower to itself and the number of different paths from tower to tower is the same as the number of different paths from tower to tower .

The lead architect in charge of the design wishes for the bridges to be built such that for all there are exactly different paths from tower to tower , where .

Construct a set of bridges that satisfy the architect's requirements, or determine that it is impossible.

#### Implementation details

You should implement the following procedure:

```
int construct(int[][] p)
```

- : an array representing the architect's requirements.
- If a construction is possible, this procedure should make exactly one call to
`build`

(see below) to report the construction, following which it should return . - Otherwise, the procedure should return without making any calls to
`build`

. - This procedure is called exactly once.

The procedure `build`

is defined as follows:

```
void build(int[][] b)
```

- : an array, with if there is a bridge connecting tower and tower , or otherwise.
- Note that the array must satisfy for all and for all .

#### Examples

##### Example 1

Consider the following call:

```
construct([[1, 1, 2, 2], [1, 1, 2, 2], [2, 2, 1, 2], [2, 2, 2, 1]])
```

This means that there should be exactly one path from tower to tower . For all other pairs of towers , such that , there should be exactly two paths from tower to tower . This can be achieved with bridges, connecting pairs of towers , , and .

To report this solution, the `construct`

procedure should make the following call:

```
build([[0, 1, 0, 0], [1, 0, 1, 1], [0, 1, 0, 1], [0, 1, 1, 0]])
```

It should then return .

In this case, there are multiple constructions that fit the requirements, all of which would be considered correct.

##### Example 2

Consider the following call:

```
construct([[1, 0], [0, 1]])
```

This means that there should be no way to travel between the two towers. This can only be satisfied by having no bridges.

Therefore, the `construct`

procedure should make the following call:

```
build([[0, 0], [0, 0]])
```

After which, the `construct`

procedure should return .

##### Example 3

Consider the following call:

```
construct([[1, 3], [3, 1]])
```

This means that there should be exactly paths from tower to tower . This set of requirements cannot be satisfied. As such, the `construct`

procedure should return without making any call to `build`

.

#### Constraints

- for all
- for all
- for all

#### Subtasks

- ( points) for all
- ( points) or for all
- ( points) or for all
- ( points) for all and there is at least one construction satisfying the requirements.
- ( points) for all
- ( points) No additional constraints.

#### Sample grader

The sample grader reads the input in the following format:

- line :
- line :

The output of the sample grader is in the following format:

- line : the return value of
`construct`

.

If the return value of `construct`

is , the sample grader additionally prints:

- line :

## Comments