Daddy pig gave four missions for George to complete.

Mission 1

Given $N$ dinosaurs, find the number of dinosaurs that stand out.
(A dinosaur is considered stand out if it is taller than the dinosaurs on the left and the right)
Notice that the leftmost and rightmost dinosaur can never stand out, how sad :(

Mission 2

Given $N$ dinosaurs, finish the below operations in order:
Given $A$ pairs of $(x_i,y_i)$, swap the position of the $x_i$-th and $y_i$-th dinosaur.
Given $B$ pairs of $(x_j,y_j)$, reverse the order of the dinosaurs from the $x_j$-th to the $y_j$-th dinosaur inclusively.

Mission 3

Given $N$ dinosaurs, Daddy pig will ask George $C$ questions:
How many dinosaurs are taller than the $c_i$-th one?

Mission 4

Given $N$ dinosaurs, Daddy pig will ask George to perform $D$ operations:
Put the dinosaurs taller than $d_i$ into the basket, and take the dinosaurs shorter than $\lfloor d_i/2\rfloor$ out of the basket.

Please help him to complete the mission, or else George will cry and the dinosaurs will eat you.

Input

The first line contains an integer $T$, which indicates the type of mission.
If $T = 1$:
The second line contains an integer $N$.
The third line contains the heights of the $N$ dinosaurs, where the $i$-th dinosaur has height $h_i$.
If $T = 2$:
The second line contains integers $N$, $A$ and $B$.
The third line contains the heights of the $N$ dinosaurs, where the $i$-th dinosaur has height $h_i$.
The next $A$ lines contain pairs of integers, where the $i$-th line contains $(x_i, y_i)$.
The next $B$ lines contain pairs of integers, where the $j$-th line contains $(x_j, y_j)$.
If $T = 3$:
The second line contains an integer $N$ and $C$.
The third line contains the heights of the $N$ dinosaurs, where the $i$-th dinosaur has height $h_i$.
The next $C$ lines contain queries of Daddy Pig, where the $i$-th line contains $c_i$.
If $T = 4$:
The second line contains integers $N$ and $D$.
The third line contains the heights of the $N$ dinosaurs, where the $i$-th dinosaur has height $h_i$.
The next $D$ lines contain operations given by Daddy pig, where the $i$-th line contains $d_i$.

Output

If $T = 1$:
Output the number of dinosaurs that stand out.
If $T = 2$:
Output the heights of dinosaurs in order after the operations.
If $T = 3$:
Output the answers of each questions separated by line.
If $T = 4$:
Output the dinosaurs in the basket on the first line and the dinosaurs not in the basket on the second line.

Constraints

For all cases,
$1 \le T \le 4$
$1 \le N \le 10^3$
$1 \le A, B, C, D \le 10^4$
$1 \le x_i, x_j, y_i, y_j \le N$
$1 \le h_i, d_i \le 10^9$
Subtask 1 (25%): $T = 1$
Subtask 2 (25%): $T = 2$
Subtask 3 (25%): $T = 3$
Subtask 4 (25%): $T = 4$