B - Chmax and Chmin Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 800 点

問題文

正整数 N と，長さ N の整数列 X=(X_1,X_2,\dots ,X_N) と Y=(Y_1,Y_2,\dots ,Y_N) が与えられます.

さらに，長さ N の整数列 A=(A_1,A_2,\dots ,A_N) と B=(B_1,B_2,\dots ,B_N) が与えられます.

以下のいずれかの操作をあわせて 0 回以上 2N 回以下の好きな回数行うことで A を B に一致させることができるかどうかを判定し，できる場合にはそのような手順をひとつ出力してください.

  • chmax : 1\le l\le r\le N なる整数 l,r を選ぶ. i=l,l+1,\dots ,r について A_i を \max(A_i,X_{r-l+1}) で置き換える.

  • chmin : 1\le l\le r\le N なる整数 l,r を選ぶ. i=l,l+1,\dots ,r について A_i を \min(A_i,Y_{r-l+1}) で置き換える.

T 個のテストケースが与えられるので，それぞれについて解いてください.

制約

  • 1 \le T \le 10^5
  • 1 \le N \le 400
  • 1 \le X_i,Y_i,A_i,B_i\le N
  • 全てのテストケースにわたる N^3 の総和は 400^3 以下
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる. ここで \mathrm{test}_i は i 番目のテストケースを意味する.

T
\mathrm{test}_1
\mathrm{test}_2
\vdots
\mathrm{test}_T

各テストケースは以下の形式で与えられる.

N
X_1 X_2 \dots X_N
Y_1 Y_2 \dots Y_N
A_1 A_2 \dots A_N
B_1 B_2 \dots B_N

出力

T 個のテストケースについて順に，次のように出力せよ.

A を B に一致させることができない場合には -1 を出力せよ.

できる場合には，操作を行う回数を K\ (0\le K\le 2N) として，次の形式で出力せよ.

K
\mathrm{op}_1 l_1 r_1
\mathrm{op}_2 l_2 r_2
\vdots
\mathrm{op}_K l_K r_K

ここで \mathrm{op}_i,l_i,r_i は i 回目の操作を表す. \mathrm{op}_i は chmax または chmin で，i 回目の操作の種類を表す. l_i,r_i はそれぞれ i 回目の操作で選んだ l,r とせよ.

入力例 1

2
3
1 3 1
3 1 3
1 2 3
3 1 1
2
1 1
2 2
1 2
2 1

出力例 1

2
chmax 1 2
chmin 2 3
-1

1 つ目のテストケースについて説明します. A=(1,2,3),B=(3,1,1) です. 次の 2 回の操作を順に行います.

  • chmax 1 2 : A_1,A_2 をそれぞれ \max(A_1,X_2)=3,\max(A_2,X_2)=3 で置き換えます. A=(3,3,3) となります.
  • chmin 2 3 : A_2,A_3 をそれぞれ \min(A_2,Y_2)=1,\min(A_3,Y_2)=1 で置き換えます. A=(3,1,1) となります.

その結果，A を B に一致させることができます. 別の出力として，次のようなものも正答となります.

4
chmax 1 3
chmax 1 2
chmin 1 1
chmin 2 3

操作回数が最小である必要がないことに注意してください.

2 つ目のテストケースについて，どのような 0 回以上 2N 回以下の操作列も A を B に一致させることができないことが示せます.

Score : 800 points

Problem Statement

You are given a positive integer N, and length-N integer sequences, X=(X_1,X_2,\dots ,X_N) and Y=(Y_1,Y_2,\dots ,Y_N).

Additionally, you are given length-N integer sequences, A=(A_1,A_2,\dots ,A_N) and B=(B_1,B_2,\dots ,B_N).

Determine whether it is possible to make A match B by performing the following operations any number of times between 0 and 2N (inclusive) in total, and if it is possible, output one such procedure.

  • chmax: Choose integers l and r such that 1\le l\le r\le N. For i=l,l+1,\dots ,r, replace A_i with \max(A_i,X_{r-l+1}).

  • chmin: Choose integers l and r such that 1\le l\le r\le N. For i=l,l+1,\dots ,r, replace A_i with \min(A_i,Y_{r-l+1}).

You are given T test cases; solve each of them.

Constraints

  • 1 \le T \le 10^5
  • 1 \le N \le 400
  • 1 \le X_i,Y_i,A_i,B_i\le N
  • The sum of N^3 over all test cases is at most 400^3.
  • All input values are integers.

Input

The input is given from Standard Input in the following format. Here, \mathrm{test}_i denotes the i-th test case.

T
\mathrm{test}_1
\mathrm{test}_2
\vdots
\mathrm{test}_T

Each test case is given in the following format:

N
X_1 X_2 \dots X_N
Y_1 Y_2 \dots Y_N
A_1 A_2 \dots A_N
B_1 B_2 \dots B_N

Output

For each of the T test cases, in order, output as follows.

If it is impossible to make A match B, output -1.

If it is possible, letting K\ (0\le K\le 2N) be the number of operations performed, output in the following format:

K
\mathrm{op}_1 l_1 r_1
\mathrm{op}_2 l_2 r_2
\vdots
\mathrm{op}_K l_K r_K

Here, \mathrm{op}_i, l_i, and r_i represent the i-th operation. \mathrm{op}_i is chmax or chmin, representing the type of the i-th operation. l_i and r_i are the l and r chosen in the i-th operation, respectively.

Sample Input 1

2
3
1 3 1
3 1 3
1 2 3
3 1 1
2
1 1
2 2
1 2
2 1

Sample Output 1

2
chmax 1 2
chmin 2 3
-1

We explain the first test case. We have A=(1,2,3) and B=(3,1,1). Perform the following two operations in order.

  • chmax 1 2 : Replace A_1,A_2 with \max(A_1,X_2)=3,\max(A_2,X_2)=3, respectively. Now A=(3,3,3).

  • chmin 2 3 : Replace A_2,A_3 with \min(A_2,Y_2)=1,\min(A_3,Y_2)=1, respectively. Now A=(3,1,1).

As a result, A matches B. The following output is also accepted.

4
chmax 1 3
chmax 1 2
chmin 1 1
chmin 2 3

Note that the number of operations does not need to be minimized.

For the second test case, it can be shown that no sequence of operations of length between 0 and 2N (inclusive) makes A match B.