Codeforces functionality may be limited from June 18, 19:00 (UTC) to June 19, 3:00 AM (UTC) due to technical maintenance. Polygon will work as usual.
×

Codeforces Round 868 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

brute force

math

sortings

*900

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Sort with Step

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputLet's define a permutation of length $$$n$$$ as an array $$$p$$$ of length $$$n$$$, which contains every number from $$$1$$$ to $$$n$$$ exactly once.

You are given a permutation $$$p_1, p_2, \dots, p_n$$$ and a number $$$k$$$. You need to sort this permutation in the ascending order. In order to do it, you can repeat the following operation any number of times (possibly, zero):

- pick two elements of the permutation $$$p_i$$$ and $$$p_j$$$ such that $$$|i - j| = k$$$, and swap them.

Unfortunately, some permutations can't be sorted with some fixed numbers $$$k$$$. For example, it's impossible to sort $$$[2, 4, 3, 1]$$$ with $$$k = 2$$$.

That's why, before starting the sorting, you can make at most one preliminary exchange:

- choose any pair $$$p_i$$$ and $$$p_j$$$ and swap them.

Your task is to:

- check whether is it possible to sort the permutation without any preliminary exchanges,
- if it's not, check, whether is it possible to sort the permutation using exactly one preliminary exchange.

For example, if $$$k = 2$$$ and permutation is $$$[2, 4, 3, 1]$$$, then you can make a preliminary exchange of $$$p_1$$$ and $$$p_4$$$, which will produce permutation $$$[1, 4, 3, 2]$$$, which is possible to sort with given $$$k$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$1 \le k \le n - 1$$$) — length of the permutation, and a distance between elements that can be swapped.

The second line of each test case contains $$$n$$$ integers $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$) — elements of the permutation $$$p$$$.

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

- 0, if it is possible to sort the permutation without preliminary exchange;
- 1, if it is possible to sort the permutation with one preliminary exchange, but not possible without preliminary exchange;
- -1, if it is not possible to sort the permutation with at most one preliminary exchange.

Example

Input

64 13 1 2 44 23 4 1 24 23 1 4 210 34 5 9 1 8 6 10 2 3 710 34 6 9 1 8 5 10 2 3 710 34 6 9 1 8 5 10 3 2 7

Output

0 0 1 0 1 -1

Note

In the first test case, there is no need in preliminary exchange, as it is possible to swap $$$(p_1, p_2)$$$ and then $$$(p_2, p_3)$$$.

In the second test case, there is no need in preliminary exchange, as it is possible to swap $$$(p_1, p_3)$$$ and then $$$(p_2, p_4)$$$.

In the third test case, you need to apply preliminary exchange to $$$(p_2, p_3)$$$. After that the permutation becomes $$$[3, 4, 1, 2]$$$ and can be sorted with $$$k = 2$$$.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/19/2024 08:10:47 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|