J. Jaimito's blocks
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Jaimito is a manufacturer of educational children's games. His latest game contains a certain number of wooden blocks that can be placed on a board forming $$$T$$$ towers of blocks. Each tower is in a specific position on the board, designated by a different integer between $$$1$$$ and $$$T$$$ inclusive. These positions can be empty, meaning that some of the towers may not contain blocks.

The blocks in a tower are stacked one on top of the other, so that each block in that tower has exactly one block underneath and exactly one block on top, except for the bottom block which has the board underneath, and the top block which has nothing on top.

Each block has a certain weight that is a positive integer. As part of the game rules, the stability rule must always be respected: it is not allowed for a block to be placed on top of another block with strictly smaller weight. In other words, the blocks of each tower, when viewed from the board upwards, are ordered in a non-increasing manner by weight. A configuration of blocks that respects the stability rule is called stable. The following figure shows two stable configurations for a game with $$$T=3$$$ towers.

A permitted move in the game consists of taking the top block from a non-empty tower and placing it on top of another (possibly empty) tower, always respecting the stability rule.

Jaimito needs your help to determine, given two stable configurations, an initial and a final one, whether it is possible to reach the final configuration from the initial configuration through zero or more permitted moves.

Input

The first line contains an integer $$$T$$$ ($$$1 \leq T \leq 2 \cdot 10^5$$$) indicating the number of towers.

Each of the following $$$2T$$$ lines describes a tower. The first $$$T$$$ lines describe the towers of the initial configuration, in order from tower $$$1$$$ to tower $$$T$$$, while the remaining $$$T$$$ lines describe the towers of the final configuration, in the same order.

The line describing each tower contains an integer $$$K \ge 0$$$ followed by $$$K$$$ integers $$${X_1}, {X_2}, \ldots, {X_K}$$$ ($$$1 \leq X_i \leq 10^9$$$), indicating that the tower contains $$$K$$$ blocks and that $$$X_i$$$ is the weight of the $$$i$$$-th block of the tower, counting from the board upwards.

It is guaranteed that the initial and final configurations are stable, and that neither has more than $$$2 \cdot 10^5$$$ blocks.

Output

A line with the uppercase letter "S" if it is possible to reach the final configuration from the initial configuration through zero or more permitted moves, or the uppercase letter "N" otherwise.

Examples
Input
4
2 3 2
1 4
2 3 1
1 4
0
2 2 1
2 3 3
2 4 4
Output
S
Input
3
2 6 5
2 6 3
1 8
1 6
0
3 8 6 5
Output
N
Input
1
0
0
Output
S
Note

In the first example, we can make the following sequence of permitted moves to reach from the initial configuration to the final configuration:

The moves are:

  • Move the block with weight $$$4$$$ from the second tower to the fourth.
  • Move the block with weight $$$2$$$ from the first tower to the second.
  • Move the block with weight $$$1$$$ from the third tower to the second.
  • Move the block with weight $$$3$$$ from the first tower to the third.

In the statement, there is an image that shows the initial configuration and the final configuration corresponding to the second example.