B - Near Assignment 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 600 点

問題文

長さ N の整数列 A=(A_1,A_2,\cdots,A_N),B=(B_1,B_2,\cdots,B_N) 及び整数 K が与えられます．

あなたは次の操作を 0 回以上行うことができます．

  • 整数 i,j (1 \leq i,j \leq N) を選ぶ． ただしここで |i-j| \leq K を満たす必要がある． そして A_i の値を A_j に変更する．

A を B に一致させることが可能かどうか判定してください．

1 つの入力につきテストケースは T 個あります．

制約

  • 1 \leq T \leq 125000
  • 1 \leq K < N \leq 250000
  • 1 \leq A_i,B_i \leq N
  • ひとつの入力の中のテストケースすべてにわたる N の総和は 250000 以下である
  • 入力される値はすべて整数

入力

入力は標準入力から以下の形式で与えられる。

T
case_1
case_2
\vdots
case_T

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

N K
A_1 A_2 \cdots A_N
B_1 B_2 \cdots B_N

出力

各テストケースに対し，A を B に一致させることが可能なら Yes，不可能なら No と出力せよ．

入力例 1

4
3 1
1 1 2
1 2 2
5 4
2 4 5 1 3
2 1 3 2 2
13 1
3 1 3 3 5 3 3 4 2 2 2 5 1
5 3 3 3 4 2 2 2 2 5 5 1 3
20 14
10 6 6 19 13 16 15 15 2 10 2 16 9 12 2 6 13 5 5 9
5 9 6 2 10 19 16 15 13 12 10 2 9 6 5 16 19 12 15 13

出力例 1

Yes
Yes
No
Yes

1 つめのテストケースについて考えます． i=2,j=3 を選んで操作すると，A_2 の値が A_3=2 に変更され，A=(1,2,2) になります．

Score : 600 points

Problem Statement

You are given integer sequences of length N: A=(A_1,A_2,\cdots,A_N) and B=(B_1,B_2,\cdots,B_N), and an integer K.

You can perform the following operation zero or more times.

  • Choose integers i and j (1 \leq i,j \leq N). Here, |i-j| \leq K must hold. Then, change the value of A_i to A_j.

Determine whether it is possible to make A identical to B.

There are T test cases for each input.

Constraints

  • 1 \leq T \leq 125000
  • 1 \leq K < N \leq 250000
  • 1 \leq A_i,B_i \leq N
  • The sum of N across all test cases in each input is at most 250000.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

T
case_1
case_2
\vdots
case_T

Each test case is given in the following format:

N K
A_1 A_2 \cdots A_N
B_1 B_2 \cdots B_N

Output

For each test case, print Yes if it is possible to make A identical to B, and No otherwise.

Sample Input 1

4
3 1
1 1 2
1 2 2
5 4
2 4 5 1 3
2 1 3 2 2
13 1
3 1 3 3 5 3 3 4 2 2 2 5 1
5 3 3 3 4 2 2 2 2 5 5 1 3
20 14
10 6 6 19 13 16 15 15 2 10 2 16 9 12 2 6 13 5 5 9
5 9 6 2 10 19 16 15 13 12 10 2 9 6 5 16 19 12 15 13

Sample Output 1

Yes
Yes
No
Yes

Consider the first test case. If we operate with i=2 and j=3, the value of A_2 will be changed to A_3=2, resulting in A=(1,2,2).