Swap by Sum
View as PDFYou are given two integer arrays ~a~ and ~b~, each consisting of ~n~ elements, and an integer ~k~.
You are allowed to transform array ~a~ using the following operation any number of times:
- Choose an index ~i~ (~1 \le i < n~) such that ~a_i + a_{i + 1} = k~, and swap the two elements ~a_i~ and ~a_{i+1}~.
Given arrays ~a~ and ~b~, determine whether it is possible to transform array ~a~ into array ~b~.
Input
The first line contains an integer ~t~ (~1 \le t \le 10^4~) — the number of test cases. The description of each test case is as follows:
The first line contains two integers ~n~, ~k~ (~1 \le n \le 2 \cdot 10^5~; ~|k| \le 10^9~).
The second line contains ~n~ integers ~a_1, a_2, \ldots, a_n~ (~|a_i| \le 10^9~).
The third line contains ~n~ integers ~b_1, b_2, \ldots, b_n~ (~|b_i| \le 10^9~).
It is guaranteed that the sum of ~n~ over all test cases does not exceed ~2 \cdot 10^5~.
Output
For each test case, print YES if it is possible to transform array ~A~ into array ~B~, or NO otherwise.
Scoring
The total score for this problem is ~1000~.
Sample Input 1
5
5 5
1 4 1 2 3
4 1 1 3 2
3 -5
-1 -2 -4
-4 -2 -1
1 1000000000
-1000000000
1000000000
4 0
-1 1 -1 1
1 -1 1 -1
6 7
1 6 6 1 2 5
6 1 1 6 5 2
Sample Output 1
YES
NO
NO
YES
YES
Notes
In the first test case, ~k = 5~ and ~a = [1, 4, 1, 2, 3]~. We can perform the following operations to transform array ~a~ into ~b = [4, 1, 1, 3, 2]~:
Swap the first pair of elements: ~[\underline{1}, \underline{4}, 1, 2, 3] \Longrightarrow [4, 1, 1, 2, 3]~;
Swap the last pair of elements: ~[4, 1, 1, \underline{2}, \underline{3}] \Longrightarrow [4, 1, 1, 3, 2]~.
In the second test case, ~k = 5~, ~a = [-1, -2, -4]~ and ~b = [-4, -2, -1]~. Since there is no adjacent pair of elements whose sum is ~5~, no transformation can be performed at all. Thus, the answer is NO.
Comments
This comment is hidden due to too much negative feedback. Show it anyway.
tôi bị lừa :)
:))) khuyen cao ko xem binh luạn
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
$$tôi \ bị \ {\huge lừaaaaaaa}$$