408670: GYM103260 J Increasing or Decreasing
Description
You are given two permutations $$$A$$$ and $$$B$$$ of size $$$n$$$. Both permutations contain integers from $$$1$$$ to $$$n$$$. You want to transform $$$A$$$ to $$$B$$$ in no more than $$$n$$$ operations of the following kind:
- Choose a subsegment $$$[l;r]$$$ of $$$A$$$ and sort it in either increasing or decreasing order.
Note that you don't have to minimize the number of operations, any sequence of operations of length not more than $$$n$$$ is fine.
InputThe first line contains one integer $$$n$$$ ($$$1 \le n \le 500$$$) — the sizes of both permutations.
The second line contains the permutation $$$A_{1}, A_{2}, \ldots, A_{n}$$$.
The third line contains the permutation $$$B_{1}, B_{2}, \ldots, B_{n}$$$.
OutputOn the first line print one integer $$$m$$$ ($$$0 \le m \le n$$$) — the number of operations.
On the next $$$m$$$ lines print the descriptions of operations. Each description should be formatted as $$$l_{i}$$$ $$$r_{i}$$$ $$$t_{i}$$$ ($$$1 \le l_{i} \le r_{i} \le n$$$, $$$t_{i}$$$ is 'I' or 'D') and means sorting the subsegment $$$[l_{i};r_{i}]$$$ in (I)ncreasing or (D)ecreasing order.
If there are different solutions any one will be accepted. It is guaranteed that there is at least one solution.
ExamplesInput5 2 4 5 1 3 5 4 3 2 1Output
1 1 5 DInput
5 5 4 3 2 1 3 2 5 1 4Output
4 2 5 I 1 4 I 1 3 D 3 4 DInput
5 3 1 4 5 2 3 1 4 5 2Output
0