Yamochka is a big fan of puzzles, so recently she bought herself a new jigsaw puzzle. The assembled puzzle is a rectangular grid of K rows and L columns, consisting of K · L equal-sized squares, called puzzle pieces. Each side of a piece can have a socket of a certain type, or a tab of a certain type, or be smooth if that side lies on the boundary of the puzzle. If two pieces in the assembled puzzle are adjacent by a side, then on that side one piece must have a tab and the other a socket, and they must be of the same type.

Unfortunately, Yamochka turned out to be not very experienced at assembling puzzles, so she bought a beginner set: in this set, all tab types are distinct, and all socket types are distinct as well. More formally: each connection type corresponds to exactly one tab and one socket, or to nothing.

After opening the box with the puzzle and trying to fit some pieces together, Yamochka realized that puzzles are not really her thing, so the task of assembling this puzzle falls entirely on you.

The first line contains an integer N (1 ≤ N ≤ 10⁵) — the number of puzzle pieces.

The next N lines contain four integers l_i, u_i, r_i, d_i (−10⁶ ≤ l_i, u_i, r_i, d_i ≤ 10⁶) — the descriptions of the left, top, right, and bottom sides of the i-th puzzle piece, respectively. If t is one of these numbers, then:

• if t > 0, then this side has a tab of type |t|;
• if t < 0, then this side has a socket of type |t|;
• if t = 0, then this side is smooth and must lie on the outer boundary of the puzzle.

Of course, any piece can be rotated clockwise by any angle that is a multiple of 90^∘.

In the first line, output two numbers K, L (1 ≤ K, L ≤ N; K × L = N).

In the next K lines, output L integers — the indices of the pieces in input order that should be placed in those positions in the assembled puzzle.

Each piece must appear in the output exactly once. The rotations of the pieces do not need to be specified in the output. The answer is considered correct if there exists a set of rotations such that all adjacent sides are compatible and all smooth sides lie on the boundary.

It is guaranteed that an answer always exists. If there are multiple valid answers, output any of them.