hackercupai/hackercup huggingface dataset:
**Note: The only difference between this chapter and [chapter 1](https://www.facebook.com/codingcompetitions/hacker-cup/2022/round-1/problems/A1) is that here, card values are not guaranteed to be distinct and can be up to \(10^9\).**

Let's cut to the chase. You have a deck of \(N\) face-up cards, each displaying **a not necessarily unique integer between \(1\) and \(10^9\).**

*Cutting* the deck once consists of taking a stack of between \(1\) and \(N - 1\) (inclusive) cards from the top and moving it to the bottom in the same order. For example, for the deck \([5, 1, 2, 4, 3]\) ordered from top to bottom, cutting \(2\) cards from the top would yield \([2, 4, 3, 5, 1]\):

{{PHOTO_ID:792109885435616|WIDTH:700}}

Initially, the \(i\)th card from the top is \(A_i\). Is it possible to cut the deck exactly \(K\) times to reorder the deck such that the \(i\)th card from the top is \(B_i\) for all \(i\)?

# Constraints

\(1 \le T \le 205\)
\(2 \le N \le 500{,}000\)
\(0 \le K \le 10^{9}\)
\(1 \le A_i, B_i \le \mathbf{10^9}\)
**\(A\) and \(B\) are permutations of each other.**

The sum of \(N\) across all test cases is at most \(7{,}000{,}000\).

# Input Format

Input begins with an integer \(T\), the number of test cases. For each test case, there is first a line containing two space-separated integers \(N\) and \(K\). Then, there is a line containing \(N\) space-separated integers, \(A_1, ..., A_N\). Then, there is a line containing \(N\) space-separated integers, \(B_1, ..., B_N\).

# Output Format

For the \(i\)th test case, print `"Case #i: "` followed by `"YES"` if it's possible to cut the deck \(K\) times to change the deck from \(A_i\) to \(B_i\), or `"NO"` otherwise.

# Sample Explanation

In the first case, it's possible to get to the new order with \(K = 1\) cut (cutting 2 cards from the top).

In the second case, it's impossible to change \([3, 1, 4, 2]\) to \([1, 2, 3, 4]\) with any number of cuts.

In the third case, it's impossible for the deck to be in a different order after \(K = 0\) cuts.