Description

Note: This is just the translation of "10664 - easy 8 Puzzles" in English. Please submit your code to "10664 - easy 8 Puzzles".

Given a 3×3 board with 9 tiles and every tile has one number from 0 to 8. 

We can swap ‘0’ with its four adjacent (left, right, above, and below) tiles. For example:

step 1 : swap 0 with ‘5’

step 2 : swap 0 with ‘6’

The objective is to place the numbers on tiles to match the following configuration.

(Noting important in this paragraph, something like Rody is too busy and needs your help to solve this problem.) 

Input

Given T (1<=T<=30) in the first line, saying that there will be T test cases.

From 2nd line to (T+1)-th line, each line contains 9 distinct integers from 0 to 8, representing an 8-puzzle game. Nice integers will be filled to the 3×3 board in a row-major manner. For example, 1 2 3 4 0 5 7 8 6 will become the configuration as shown in the following figure.

Output

For each 8-puzzle game, if it can be solved in 14 steps, print out "You can solve it within x steps.", x is the minimum number of steps to solve this puzzle. Otherwise, print out "You'd better skip this game.

Sample Input  Download

Sample Output  Download

Discuss

Description

Mr. Kuo is an adventurer. One day, he finds a sequences of operations and an empty set S.

Each operation is one of the following two types,

1. Insert x：insert x into S. Duplicate element is legal.
2. Query x k：Among the elements of S that are greater or equal to x, what is the k-th smallest value？

Mr. Kuo is curious about the answer to each operation 2, so he asks for your help.

Hint：You can refer to C++ upper_bound function. 

Input

The input consists of multiple lines.

Each line is given in one of the following two format：

1. Insert x
2. Query x k

There will be at most 100000 operations in the sequences.

1 ≤ x ≤ 10⁹

1 ≤ k ≤ 5

Output

For each operation of type 2, print the k-th smallest value among the elements of S that are greater than or equal to x.

If there are less than k elements of S that are greater than or equal to x, then print "-1".

Remember to print '\n' at the end of each line.

Sample Input  Download

Sample Output  Download

Discuss

Description

There are \(N\) stones, numbered \(1,2,...,N\).

There is a frog who is initially on Stone \(x\). He will repeat the following action some number of times to reach Stone \(N\):

• If the frog is currently on Stone \(i\), jump to Stone \(i + d\) or Stone \(i - d\) where \(d\) is a divisor of \(i\).

Here, an integer \(b\) is said to be a divisor of \(a\) if there exist an integer \(c\) such that \(a = b \times c\).

For each starting stone \(1 \leq x \leq N\), find the minimum number of jumps to reach Stone \(N\).

Input

The only line contains an integer \(N\).

\(N\)

Constraints

• \(1 \le N\le 10^6\)

Output

Please output \(N\) integers in a line, each followed by a space.

Sample Input  Download

Sample Output  Download

Discuss

Description

You might need to use long long int to avoid overflow.

Elephants love to eat KuoTA (鍋貼), so Elfnt decided to open a restaurant called "八方來財", serving delicious KuoTA to satisfy their cravings.

After solving the queueing problem, Elfnt now hopes to close the restaurant as early as possible to get some rest. He already knows the dining time of all $n$ elephants today. Please calculate how long the restaurant needs to stay open, from opening to closing.

There are $k$ seats in the restaurant. As long as there is an available seat, the elephant at the front of the queue will immediately be seated and start dining. Once the $i$-th elephant is seated, they will occupy the seat for $x_i$ units of time, after which they will leave the restaurant, freeing up the seat. (At the very beginning, the first $k$ elephants will be seated immediately.)

Input

The first line contains two integers $n$ and $k$, representing the number of elephant and the number of seats.

The second line contains $n$ integers $x_1, x_2, ..., x_n$, where $x_i$ is the amount of time the $i$-th elephant will take to dine.

Constraints

• $1 \leq n, k \leq 2 \times 10^5$
• $1 \leq x_j \leq 10^9$

Subtask

1. (Testcases 1-3) $1 \leq n, k \leq 1000$
2. (Testcases 4-6) No additional constraints.

Output

Output how long the restaurant needs to stay open. (NO space and '\n' at the end)

Sample Input  Download

Sample Output  Download

Discuss