The Hangzhou Normal U Qualification Trials for ZJPSC 2021
A. Array Permutation
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Little H is so boring that he wants to generate an array of length $$$n$$$.

Little H uses the following method to generate the array.

  • Suppose the current array length is $$$m(m \lt n)$$$. Then he will randomly generate a number $$$x$$$ from $$$[1, n - m]$$$. Then he will follow the ordered permutation of $$$[1, x]$$$(such as $$$x = 3$$$, the ordered permutation is $$$[1, 2, 3]$$$) after the array.
  • If the length of the array after the append operation is completed is $$$n$$$，then finish the entire process, otherwise repeat the above steps.

Now little H want to know how many different arrays there are for a certain $$$n$$$。

Due to the limited ability of counting little H, you just need to output the answer modulo $$$10^9 + 7$$$.

Input

There are several test cases.

The first line contains a single integer $$$T(1 \leq T \leq 10^3)$$$, denoting the number of test cases. Then follow all the test cases.

For each test case, only one line which contains a single integer $$$n(1 \leq n \leq 10^6)$$$, denoting the length of the array little H wants to generate.

Output

For each test case, print a integer in one line which denoting the answer.

Example
Input
3
1
100
1000000
Output
1
988185646
617521033

B. Baom and Fibonacci
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

As we know the Fibonacci sequence is:

$$$$$$ fib(n) = \begin{cases} 1 &n=1 \ or \ n=2 \\ fib(n-1) + fib(n-2) & n \gt 2 \end{cases} $$$$$$

Baom wonder the value of function:

$$$$$$ f(n)=\sum_{i=1}^n\sum_{j=1}^n\gcd(fib(i),fib(j)) \bmod 998244353 $$$$$$

Input

One line contains a sigle integer $$$n(1 \leq n \leq 10^{10})$$$.

Output

Print a single integer $$$f(n) \bmod 998244353$$$.

Example
Input
3
Output
10

C. Circle Minimal
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

As we all know, a tree has $$$n$$$ nodes and $$$n - 1$$$ edges.

We define the length of the circle as the sum of the weights of all edges on the circle.

Now we have a graph with $$$n$$$ nodes and $$$n$$$ edges, you can move at most one edge on the graph to minimize the length of the circle on the graph.

If you choose to move an edge, there can be no self-loops(which means $$$u \rightarrow u$$$) and duplicated edges after the movement, and the graph is connected (at least one path can reach any two points on the graph).

Little H need you output the length of the minimal circle.

Input

The first line contains a single integer $$$n(3 \leq n \leq 10^5)$$$.

Each of the next $$$n$$$ lines contains three integers $$$u_i, v_i, w_i(1 \leq u_i, v_i \leq n, 1 \leq w_i \leq 10^9)$$$, representing the $$$i$$$-th edge connect $$$u_i$$$ and $$$v_i$$$ which weights is $$$w_i$$$.

Output

Print a single integer, denoting the answer.

Examples
Input
5
1 2 1
1 5 1
3 4 1
1 4 10
2 3 10
Output
3
Input
5
1 2 1
2 3 1
3 4 1
1 4 10
1 5 10
Output
3

D. Double Pleasure
time limit per test
3 s
memory limit per test
256 megabytes
input
standard input
output
standard output

Hsueh- especially likes pleasure number because these numbers make people feel happy.

A number is a pleasure number, iff it is an integer, and the greatest common factor of the product of its digits and the number itself is not $$$1$$$.

It is worth noting that:

  • The greatest common factor of $$$0$$$ and $$$x$$$ ($$$x \gt 0$$$) is $$$x$$$.
  • $$$0$$$ and $$$0$$$ have no greatest common factor.

For instance：

  • $$$33$$$ is the pleasure number, because $$$3 \times 3 = 9$$$, the greatest common factor of $$$9$$$ and $$$33$$$ is $$$3$$$.
  • $$$233$$$ is not a pleasure number because $$$2 \times 3 \times 3 = 18$$$, and the greatest common factor of $$$18$$$ and $$$233$$$ is $$$1$$$.

Hsueh- wants to know how many pleasure numbers in the range $$$[A, B]$$$.

Input

The first line contains a single integer $$$T(1 \leq T \leq 10^4)$$$, denoting the number of test case.

For next $$$T$$$ lines, each line contains two integer $$$A, B(1 \leq A, B \leq 10^{18})$$$, representing the range $$$[A, B]$$$.

Output

For each test case, print a single integer, denoting the answer.

Example
Input
2
1 2
3 4
Output
1
2

E. Eaom and Longzhu
time limit per test
8 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Long long ago,as the legend said,whoever collect $$$7$$$ kind of longzhu can summon a Dragon and Dragon will makes your dreams come true.

Currently, Baom is trapped in a maze out of the world. Baom is at room $$$1$$$ and the export is at room $$$n$$$. He surprisely find that there are longzhus in each room in the maze. Baom decide to escape the maze and collect enough longzhu to make a wish.

Unfortunately, he could collect excatly one longzhu each time he get into a room.

Forunately, the room is connected by some portals, Baom can transmit himself between portals which cost energies. And longzhu is so magical that can recover Baom $$$\frac{x_{ij}w}{10}$$$ energies where $$$i$$$ is the last kinds of longzhu you had collected, $$$j$$$ is the current longzhu you just collcet and $$$w$$$ is the energies you had just cost during the transmission.

Baom hope to escape the maze and collected all kinds of longzhu with minimum energies costs.Can you help him?

Note that Baom can collected the same kind of longzhu at different rooms or collect different kind of longzhu at the same room if Baom come into it again.

The number of longzhu is infinite in each room.

Input

The first line contains integers $$$n,m (1 \leq n \leq 5\cdot 10^2,1 \leq m \leq \frac{n(n-1)}{2})$$$—number of rooms and portals.

Next $$$7$$$ lines each line contains $$$7$$$ integers $$$x_{ij} (0\leq x_{ij}\leq 10)$$$–the number described above.

Next $$$m$$$ lines each line contains $$$3$$$ integers $$$u,v,w (1\leq u,v\leq n,1\leq w\leq 10^5 \; and \; w \equiv 0\bmod 10)$$$.

Output

Print a single integer —- the minimum cost of energies if exist else $$$-1$$$.

Example
Input
3 3
0 3 9 0 6 8 1
5 0 1 5 3 8 8
7 4 5 2 5 6 9
3 0 9 7 0 1 8
6 3 8 7 0 4 9
2 9 6 6 8 3 3
4 1 2 7 7 8 3
2 1 40
1 3 60
2 3 40
Output
44

F. Fill the Binary String
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a string $$$s_1s_2...s_n$$$ of length $$$n$$$ where $$$s_i \in \{'0','1','?'\}$$$ and an integer $$$k$$$, please fill out all the $$$'?'$$$ with $$$'0'$$$ or $$$'1'$$$ such that the number of indices $$$i$$$ satisfying $$$1 \leq i \lt n$$$ and $$$s_i \neq s_{i+1}$$$ equals to $$$k$$$.

That's all? Nah! To heat things up,our dear friend asks you to find the answer with the smallest possible lexicographic order if it exists.

Recall that a string $$$a_1 a_2 ...a_n$$$ of length $$$n$$$ is lexicographically smaller than another string $$$b_1 b_2 ...b_n$$$ of length $$$n$$$ if there exists an integer $$$k$$$ ($$$1 \leq k \leq n$$$) such that $$$a_i = b_i$$$ for all $$$1 \leq i \lt k$$$ and $$$a_k \lt b_k$$$ .

Input

There are multiple test cases.

The first line of the input contains an integer $$$T$$$ indicating the number of test cases.

For each test case:

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 10^5 , 0 \leq k \lt n$$$) indicating the length of the string and the required number of indices satisfying the condition.

The second line contains a string $$$s_1s_2...s_n$$$ ($$$s i \in \{'0','1','?'\}$$$).

It's guaranteed that the sum of $$$n$$$ of all test cases will not exceed $$$10^6$$$ .

Output

For each test case output one line.

If the answer exists output the lexicographically smallest one (you need to output the whole given string after filling out all the '?' and make this string the lexicographically smallest); Otherwise output "Impossible" (without quotes).

Example
Input
5
9 6
1?010??01
9 5
1?010??01
9 6
100101101
9 5
100101101
9 3
????????1
Output
100100101
Impossible
100101101
Impossible
000000101

G. Guess Strings
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem. You have to use a flush operation right after printing each line. For example, in C++ you should use the function fflush(stdout), in Java — System.out.flush(), in Pascal — flush(output) and in Python — sys.stdout.flush().

One day, Kwords was very boring, so he constructed a string. This string consists of two types of lowercase letters. And the length of this string is between $$$2$$$ and $$$100$$$.

At the same time, Hsueh- is also boring. So Kwords wants Hsueh- to guess what the string constructed by Kwords is.

Hsueh- can ask kwords for information about the string by inquiry.

In each inquiry, Hsueh- can ask whether a string $$$S$$$ is a substring of string $$$T$$$ which constructed by Kwords is。

In order to respect Hsueh-, Kwords only allows him to ask questions up to $$$200$$$ times.

Interaction

For each output, you must follow the following format.

  • ASK $$$T$$$：The meaning of this format is to ask whether the string $$$T$$$ is a substring of the string S which constructed by Kwords, if it is, the jury will return $$$1$$$, otherwise it will return $$$0$$$.
  • ANSWER $$$T$$$：Make sure your answer is $$$T$$$.
Example
Input

1

0

1

1

0

0

0

0
Output
ASK a

ASK c

ASK b

ASK ab

ASK aba

ASK abb

ASK aab

ASK bab

ANSWER ab

H. Hsueh- And Treasure
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Hsueh- Dreaming one night, dreaming that he was in a vast ocean.

In a faraway place, there is an island. It is said that there are some precious treasures on it. There are treasures left by the King of Sailing Kwords to give to the world.

So Hsueh- wants to find the treasure left by Kwords。

We assume that the sea is a two-dimensional plane, Hsueh- is currently at $$$(0,0)$$$, and the location of the treasure is at $$$(x,y)$$$.

Next, due to the influence of the cosmic background radiation wave, Hsueh- can only take exactly $$$i$$$ steps at the $$$i$$$-th moment, and each step can only walk one square in four directions, up, down, left, and right. The initial moment is $$$0$$$.

Hsueh- is too anxious to find the last treasure, so he asks you, can you help him plan the shortest route to the destination $$$(x,y)$$$. And please output this route.

Note that there may be multiple routes, and you can output any route.

Input

The first line contains a single integer $$$T(1 \leq T \leq 10)$$$, denoting the number of test cases.

For next $$$T$$$ lines, each line contains two integers $$$x, y(|x|, |y| \leq 10^9)$$$, representing the location of the treasure.

Output

For each test case,the output format must meet the following requirements.

The first line you need to print "Case #i:"(without quotation marks), representing the current number of test cases.

The second line you need to print a single integer $$$t$$$, which indicates the final moment at which it can reach $$$(x_i, y_i)$$$.

Next $$$t$$$ lines, each line contains two integers separated by a space, denoting the location of the $$$j$$$-th moment.

Example
Input
2
1 0
2 2
Output
Case #1:
1
1 0
Case #2:
3
1 0
1 2
2 2

I. Iaom and Chicken feet
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Baom likes chicken very much.

One day ,while he was thinking a problem on tree he found it looks like chicken's feet.

He fall into thinking,how much chicken feet are there on the tree.

The "chicken feet" is a subgraph of given tree which shapes like the picture above

Baom wonder the number of "chicken feet" all over the tree.Two "feet"s are consider the same iff the set of edges of "chicken feet"s are the same.

Input

The first line contains one integer $$$n (1\le n \le 5 \cdot 10^5)$$$ —The number of nodes each of next $$$n-1$$$ line contains a description of an edge: two integers $$$u$$$ and $$$v(1\le u,v \le n,u \ne v)$$$ The given edges form a tree.

Output

Print a single integer — the number of "chicken feet" modulo $$$998244353$$$.

Example
Input
7
1 2
2 3
2 4
5 4
6 4
7 4
Output
1

J. Jew Sorting
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Hello, guys, I am the King of boredom.

I have a array of length $$$2^k(0 \leq k \leq 20)$$$. You can delete the first half or the second half of each operation.

So, you need to tell me the minimum number of operations required can make this sequence non-decreasing.

Input

The first line contains a single integer $$$k(0 \leq k \leq 20)$$$, denoting the length of the array is $$$2^k$$$.

The second line contains $$$2^k$$$ integers, the $$$i$$$-th integer is $$$a_i(1 \leq a_i \leq 10^9)$$$ representing the array.

Output

Print a single integer, denoting the answer.

Examples
Input
2
1 3 2 1
Output
1
Input
2
1 2 3 4
Output
0

K. K-Clearing II
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of $$$n$$$ integers.

While there is at least one element equal to $$$k$$$ in the array, then you should make all the positive elements in the array minus one. In other words, $$$a_i=a_i-1(1\leq i\leq n;a_i \gt 0)$$$.

Please calculate the sum of the number of elements equal to $$$0$$$ after clear all elements equal to $$$k$$$ in all subarray containing $$$m$$$ consecutive elements in the array $$$a$$$.

Input

The first line contains three integers $$$n,m(1\leq m\leq n\leq 10^6)$$$, $$$k(1\leq k\leq 10^9)$$$ — the length of $$$a$$$, the length of the subarray and the number we need to clear.

The second line contains $$$n$$$ integers $$$ a_1,a_2,...,a_n(1\leq a_i\leq 10^9)$$$.

Output

Output an integer representing the answer.

Examples
Input
5 3 1
1 2 3 4 5
Output
3
Input
6 3 1
1 1 4 5 1 4
Output
5
Note

In the second sample, there are $$$4$$$ subarrays in $$$a$$$ with length $$$m$$$:

1.$$$[1,1,4]$$$, and $$$[0,0,3]$$$ after clear the $$$k$$$

2.$$$[1,4,5]$$$, and $$$[0,3,4]$$$ after clear the $$$k$$$

3.$$$[4,5,1]$$$, and $$$[3,4,0]$$$ after clear the $$$k$$$

3.$$$[5,1,4]$$$, and $$$[4,0,3]$$$ after clear the $$$k$$$

So the sum of the number of elements equal to $$$0$$$ is $$$5$$$.

L. Little H And Reboot
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

One day, HZNU Online Judge server was unable to log in, resulting in Hsueh- unable to upload problems on the server.

After hard judgment, Hsueh- guessed that this was because the server was down.

Poor Hsueh- just go to the machine room and restart the server.

After a long period of time, Hsueh- finally found the computer room and found the location of the server, but he had never seen this super non-quantum low-speed potato server from Pangalactic Universe Invincible Co., Ltd., and didn't know how to restart it. .

Recalling that when I bought this server before, a master came to install it, and I never shut it down once.

This left him helpless. He could only call the master, but the master also forgot how to operate.

Finally, the master told him that the manual had been thrown in a certain position in the warehouse and told him the coordinates. Now Hsueh- can finally find a way to restart the server!

When Hsueh- walked into the warehouse, he found that due to the random stacking before, the whole warehouse was very chaotic. Even if he knew the coordinates, he needed to go over some boxes.

Because the boxes are randomly placed, they will not overlap.

For instance, the warehouse might look like the picture below. It can be considered that the warehouse is infinitely large, and Hsueh- is infinitely small, which can be regarded as a point.

Since the box was moved around all day, plus a lot of roads, he finally didn't want to climb over, so he decided to bypass the box. At the same time, he hopes to take the shortest path.

However, he wants you to tell him the shortest path length, so that he can decide whether to restart the server or replace it with a Pangalactic Universe Invincible Infinite Co., Ltd. Super Advanced Unspeakable Fairy Server.

Input

The first line contains a single integer $$$n(0 \leq n \leq 200)$$$, denoting the number of boxes in the warehouse.

Next $$$n$$$ lines, each line $$$8$$$ integers, $$$x_{i_0},y_{i_0},x_{i_1},y_{i_1},x_{i_2},y_{i_2},x_{i_3}, y_{i_3}$$$, arranged in a counterclockwise direction, representing a rectangular box.

The $$$n + 2$$$ line contains $$$4$$$ integers $$$x_0, y_0, x_1, y_1$$$, respectively representing the coordinates of Hsueh- and the coordinates of the manual.

The absolute value of all integers does not exceed $$$10000$$$.

Test data to ensure that the vertices of two boxes will not overlap, and at the same time ensure that the vertices of one box will not appear on the edge of the other box.

Output

Print a single float number, denoting your answer.

Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-4}$$$.

Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-4}$$$.

Example
Input
2
2 2 3 1 6 4 5 5
6 3 6 0 9 0 9 3
2 6 10 0
Output
10.79669127533633954386