D. Binary tree
time limit per test
1 second
memory limit per test
128 megabytes
input
standard input
output
standard output

Maxim Vitalievich has a binary tree consisting of $$$n$$$ vertices. All vertices are numbered from $$$1$$$ to $$$n$$$. Each vertex of the tree contains some integer, and all numbers are different. He decided to turn it into a binary search tree using two kinds of operations:

  • swap $$$x$$$ — swap values at vertex $$$x$$$ and parent vertex $$$p$$$.
  • rotate $$$x$$$ — rotate (either left or right) vertex $$$x$$$ and parent vertex $$$p$$$.

The figure above shows an example of the "swap" operation and the "rotate" operation. Note that operations cannot be applied to the root of the tree because it has no parent vertex.

Help Maksim Vitalyevich turn the original binary tree into a binary search tree in the minimum number of "swap" operations. Recall that a binary tree is a binary search tree if and only if all values in the left subtree are strictly less than the value at the vertex, and all values in the right subtree are strictly greater than.

Input

The first line contains an integer $$$n$$$ — the number of vertices in the binary tree.

The next $$$n$$$ lines contain three integers $$$a_i$$$, $$$x_i$$$, $$$y_i$$$ ($$$0 \le x_i, y_i \le n$$$) — the value at the $$$i$$$-th vertex, the numbers of the left and right vertices, respectively. If $$$x_i = 0$$$, then the $$$i$$$-th vertex has no left child vertex. If $$$y_i = 0$$$, then the $$$i$$$-th vertex has no right child vertex.

It is guaranteed that the description of the vertices in the input corresponds to the correct description of the binary tree and that all values of $$$a_i$$$ are unique.

$$$$$$ 1 \le n \le 5\,000 $$$$$$ $$$$$$ 1 \le a_i \le 10^{9} $$$$$$

Output

In the first line print the number $$$m$$$ — the total number of operations.

In the next $$$m$$$ lines print a description of the operations. The description of the $$$i$$$-th operation must be output in one of the following formats:

  • swap $$$x_i$$$, where $$$x_i$$$ — vertex number.
  • rotate $$$x_i$$$, where $$$x_i$$$ — vertex number.

If there are multiple answers, print any one. The total number of transactions must not exceed $$$300\,000$$$.

Examples
Input
2
1 2 0
2 0 0
Output
1
swap 2
Input
3
1 2 3
3 0 0
2 0 0
Output
3
swap 2
rotate 3
swap 1