The Hangzhou Normal U Qualification Trials for ZJPSC 2020
A. A simple problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

We have learned your team is good at counting problems. So we ask you a simple problem.

Now you have $$$0-n$$$ permutation, and you need to connect all the numbers in each permutation to make a new valid number and we define the new valid number as $$$S$$$. It is worth noting that if a certain permutation contains leading zero, the permutaion should be eliminated.

For example if $$$n = 2$$$, the set of $$$S$$$ will be $$$102, 120,201,210$$$.

Your task is to count how many $$$S$$$(without leading $$$0$$$) are divisible by $$$m$$$.

Input

There is a single case.

The first line contains two integers $$$n$$$, $$$m$$$$$$(1 \leq n \leq 15, 1 \leq m \leq 100)$$$.

Output

Print a single integer in one line: the number of how many $$$S$$$ are divisible by $$$m$$$.

Example
Input
2 3
Output
4

B. Hsueh- play balls
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ white balls and $$$m$$$ black balls in the box.

Hsueh- randomly takes out a single ball from the box every time until the box is empty.

You need to calculate the probability $$$p$$$ of the number of white balls and black balls outside the box is equal at least once in the process.

You need to output answer modulo $$$998244353$$$. Formally, let $$$M = 998244353$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x \lt M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

For instance, we consider $$$n = 1$$$ and $$$m = 3$$$, and we appointed "w" to represent the white ball and "b" to represent the black ball.

There are $$$4$$$ possible outcomes:

  • "wbbb"
  • "bwbb"
  • "bbwb"
  • "bbbw"

Obviously, two of the results are legal, so the answer should be $$$\displaystyle \frac{1}{2}$$$, and we can get $$$\displaystyle \frac{1}{2} \equiv 499122177 \pmod {998244353}$$$.

Input

There are several test cases.

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

For each test case, the first line contains two integers $$$n, m(1 \leq n, m \leq 10^6)$$$, representing $$$n$$$ white balls and $$$m$$$ black balls in box.

Output

For each test case, print a single integer in one line: the probability $$$p$$$ of the number of white balls and black balls outside the box is equal at least once in the process.

Examples
Input
2
1 1
1 3
Output
1
499122177
Input
1
20 18
Output
893166001

C. Hoogle Machine Translation
time limit per test
3 seconds
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().

Excellent! pubfso was lucky enough to get a Hoogle Machine Translation Machine.

This is the manual of the Hoogle Machine Translation Machine:

  • If you send a word to the machine, it will return the meaning of the word to you.
  • If you send two or more words to the machine, i.e. you send $$$x$$$ words to the machine, it will return $$$x$$$ explanations to you. Unfortunately, These $$$x$$$ explanations and $$$x$$$ words do not correspond one-to-one.

    For instance, if we have the correspondence between the following words and explanations:

    • one corresponds to $$$1$$$
    • two corresponds to $$$2$$$
    • three corresponds to $$$3$$$

    If we send $$$\{one, two, three\}$$$ to the Hoogle Machine Translation Machine.

    We may get the one of the following results:

    • $$$\{1, 2, 3\}$$$
    • $$$\{1, 3, 2\}$$$
    • $$$\{2, 1, 3\}$$$
    • $$$\{2, 3, 1\}$$$
    • $$$\{3, 1, 2\}$$$
    • $$$\{3, 2, 1\}$$$

Now, pubfso has $$$n$$$ different words need to translate, he wants your help.

Initially, pubfso will give you $$$n$$$ words.

You can make queries to the Hoogle Machine Translation Machine, Each query is a single line contains $$$x(1 \leq x \leq n)$$$ words which pubfso need to translate. Flush output stream after printing each query. Hoogle Machine Translation Machine will return $$$x$$$ explanations to you.

Your program is allowed to make no more than $$$25$$$ queries (not including printing the answer) to the Hoogle Machine Translation Machine.

Input

The first line contains a single integer $$$n(1 \leq n \leq 10^5)$$$ denoting the number of words which pubfso need to translate.

In the next line, contains $$$n$$$ strings $$$word_i$$$, denoting the $$$i$$$ th word which need to translate.

It is guaranteed that words and explanations are composed of letters or numbers, and the length does not exceed $$$10$$$.

Interaction

When your program ask the meaning of words, i.e. you need to ask $$$x(x \gt 0)$$$ words, print string:

"? $$$x$$$ $$$word_1$$$ $$$word_2$$$ $$$word_3$$$ $$$\cdots$$$ $$$word_x$$$"(without quotes).

What you need to focus on is, the query "? 0" is invalid, and the jury will return Wrong Answer to you.

If your query is legal, the Hoogle Machine Translation Machine will return Same number of explanations as words to you. As follows:

$$$explanation_1$$$ $$$explanation_2$$$ $$$explanation_3$$$ $$$\cdots$$$ $$$explanation_x$$$

If we answer with $$$-1$$$ instead of a valid answer, that means you exceeded the number of queries or made an invalid query.

Exit immediately after receiving $$$-1$$$ and you will see wrong answer verdict. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.

When you got the explanation of all the words, you need to print them in order. i.e. print the string:

"! $$$word_1$$$ $$$word_2$$$ $$$word_3$$$ $$$\cdots$$$ $$$word_n$$$"(without quotes).

After printing a query or printing the answer, do not forget to output end of line and flush the output. Otherwise, you will get idleness limit exceeded. To do this, use:

  • fflush(stdout) or cout.flush() in C++;
  • System.out.flush() in Java;
  • flush(output) in Pascal;
  • stdout.flush() in Python;
  • See the documentation for other languages.
Example
Input
3
one two three

1

2

3
Output
? 1 one

? 1 two

? 1 three

! 1 2 3

D. Dup4 and pebble pile
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Dup4 has a large number of pebbles. He numbered them $$$a$$$ through $$$b$$$.

Initially, each pebble forms a pile of its own.

But Dup4 hates so many piles. So he can do the following operation to merge the two piles.

Every time, He chooses two pebbles $$$x$$$ and $$$y$$$. If $$$x$$$ and $$$y$$$ have a common prime factor $$$t$$$, and $$$t$$$ greater or equal than $$$p$$$. He can merge the pile of pebbles where $$$x$$$ is and the pile of pebbles where $$$y$$$ is. The premise is that $$$x$$$ and $$$y$$$ belong to two different piles.

He will repeat the above operations until he can no longer merge.

Finally, Dup4 wants to know how many pebble piles will end up.

For instance, if we consider $$$a = 10, b = 20, p = 3$$$, the final result will be:

$$$$$$ [10, 12, 15, 18, 20], [11], [13], [14], [16], [17], [19] $$$$$$

There are $$$7$$$ piles.

Input

The first line contains three integers $$$a, b, p(1 \leq a \leq b \leq 10^5, 2 \leq p \leq b)$$$.

Output

Print a single integer in one line: the number of pile in the end.

Example
Input
10 20 3
Output
7

E. The King Of Sum Xor
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

If you have solved CrossFire #6XX (Div.998244353) D, you will have the potential to become the king of sum xor.

Today Dup4 meets a problem and he asks you for help. He wants to know whether there exists an array $$$n$$$ non-negative integers $$$a_1, a_2, \cdots ,a_n$$$(the array can be empty) that follow these rules.

  • $$$\displaystyle a_1+a_2+\cdots +a_n = S$$$
  • $$$\displaystyle a_1 \oplus a_2 \oplus \cdots \oplus a_n = X$$$(Here $$$\oplus$$$ denotes bitwise xor operation)

However, Dup4 thinks the problem is so easy. He thinks he needs to change something.

  1. He constructs all arrays that satisfying the requirements.
  2. He defines the maximum value of the $$$i$$$-th array as $$$M_i$$$.
  3. He finds the minimum $$$M_i$$$ of the all arrays as $$$MIN$$$.
  4. He defines a set $$$V$$$ to be composed of arrays which satisfying the condition of $$$M_i = MIN$$$.

Finally, He wants to know the minimum $$$n$$$(the length of the array) of the $$$V$$$.

Input

There are several test cases.

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

For each test case, the first line contains two integers $$$s$$$, $$$x$$$ $$$(0 \leq s, x \le 2^{60} - 1)$$$.

Output

For each test case, print $$$-1$$$ if there doesn't exist an array with the mentioned property else print your answer.

Example
Input
2
9 3
19 1
Output
6
19

F. Hsueh- Love Matrix
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Hsueh- constructed a matrix of $$$n$$$ rows and $$$m$$$ columns, the label starts from $$$1$$$. He makes the element in the $$$i$$$-th row and $$$j$$$-th column $$$a_{i, j}$$$ equal to $$$i$$$ times $$$j$$$. i.e. $$$a_{i, j} = i \cdot j$$$. You need to find the $$$k$$$-th largest element.

Unfortunately, Hsueh- only has ten fingers, so he can't count numbers with more than ten digits. Therefore, if the answer is strictly greater than $$$9,999,999,999$$$, just output "Oops"(without quotes).

For instance, we consider $$$n = 2$$$ and $$$m = 3$$$, The matrix elements are as follows:

$$$$$$ \left[ \begin{array}{ccc} 1&2&3\\ 2&4&6 \end{array} \right] $$$$$$

  • $$$k = 1$$$, the answer is $$$6$$$.
  • $$$k = 2$$$, the answer is $$$4$$$.
  • $$$k = 3$$$, the answer is $$$3$$$.
  • $$$k = 4$$$, the answer is $$$2$$$.
  • $$$k = 5$$$, the answer is $$$2$$$.
  • $$$k = 6$$$, the answer is $$$1$$$.
Input

There are several test cases.

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

For each test case, The first line contains three integers $$$n, m(1 \leq n, m \leq 10^9)$$$ and $$$k(1 \leq k \leq n \cdot m)$$$, representing you need to find the $$$k$$$-th largest element in $$$n$$$ rows and $$$m$$$ columns matrix.

Output

For each test case, output in one line "Oops"(without quotes) if the answer strictly greater than $$$9,999,999,999$$$, or print a single integer in one line: the $$$k$$$-th largest element of the matrix.

Examples
Input
5
1 1 1
2 3 6
3 3 2
1 10 10
100 100 100
Output
1
1
6
1
8722
Input
1
1000000000 1000000000 1
Output
Oops

G. LTS owns large quantities of apples
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The difference between this problem and Hsueh- owns large quantities of apples is more than the data range, please read the statement carefully.

There are $$$n$$$ apples in ltslts's bag, and $$$m$$$ kids around the man. Let's numbered these children $$$1$$$ to $$$m$$$.

ltslts take all of the apples and gave to the first child.

  • The first child got $$$n$$$ apples from ltslts. Next, he ate an apple and the remaining apples could just be divided into $$$x$$$ piles. He took a single pile and gave the remaining ($$$x - 1$$$) piles to the second child.
  • The second child got $$$\displaystyle \frac{(n - 1)(x - 1)}{x}$$$ apples from the first child. Next, he ate an apple and the remaining apples could just be divided into $$$x$$$ piles. He took a single pile and gave the remaining ($$$x - 1$$$) piles to the third child.
  • $$$\cdots$$$
  • The $$$i$$$-th child got some apples from the ($$$i - 1$$$)-th child. Next, he ate an apple and the remaining apples could just be divided into $$$x$$$ piles. He took a single pile and gave the remaining ($$$x - 1$$$) piles to the ($$$i + 1$$$)-th child.
  • $$$\cdots$$$
  • The last child got some apples from the Penultimate child, Next, he ate an apple and the remaining apples could just be divided into $$$x$$$ piles. He took a single pile and go away.

It should be noted that the number of apples in a pile taken by last child must be a positive integer.

Until the last child go away, Hsueh- wants to know what is a valid $$$n$$$ that meets all requirements.

For instance, we consider $$$m = 2$$$ and $$$x = 3$$$, a valid answer is $$$n = 7$$$.

  • The first child got $$$7$$$ apples. Next, he ate an apple and the remaining $$$6$$$ apples could just be divided into $$$3$$$ piles and $$$2$$$ apples per pile. He took a single pile and gave the remaining $$$2$$$ piles to the second child.
  • The second child got $$$4$$$ apples. Next, he ate an apple and the remaining $$$3$$$ apples could just be divided into $$$3$$$ piles and $$$1$$$ apple per pile. He took a single pile and go away.
Input

The first line contains two integers $$$m(1 \leq m \leq 15)$$$ and $$$x(2 \leq x \leq 15)$$$, denoting the number of children and the number of piles in operation of each child.

Output

For each test case, print a single integer in one line: valid $$$n$$$ that meets all requirements.

We can show that an answer less than or equal to $$$10^{18}$$$ always exists. Therefore you should to print a valid $$$n$$$ less than or equal to $$$10^{18}$$$. If there are multiple answers, print any.

Example
Input
2 3
Output
7

H. Hsueh- and keyboard
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Hsueh- has a keyboard.

There is a string which has $$$x$$$ characters in the textarea.

At present, Hsueh- wants to see a string of length exactly $$$n$$$ in the textarea.

You can use the following operations to meet Hsueh-'s requirements.

  • Strike the keyboard once, enter a character.
  • Strike the keyboard twice(Ctrl + A), select all characters in the textarea.
  • Strike the keyboard twice(Ctrl + C), copy the selected character to the clipboard.
  • Strike the keyboard twice(Ctrl + V), paste the characters which in the clipboard(Do not empty the clipboard).
  • Strike the keyboard once(Backspace), delete character at the end of the textarea or delete the selected character if some characters are selected.

Hsueh- wants to know the minimum number of strokes required to see a string of length exactly $$$n$$$ in the textarea.

What is different from your traditional perception is, if you press Ctrl + A to select all characters and then enter a character or paste some characters, the selected characters will not be deleted. In other words, if you select all characters in the textarea and then enter a character or paste some characters, it will not replace the selected characters but append the characters you enter or paste at the end.

Input

The first line contains two integers $$$x, n(0 \leq x \leq 10^6, 1 \leq n \leq 10^6)$$$, denoting the length of the string which originally appeared in the textarea and the length of the string which Hsueh- wants to see.

Output

Print a single integer in one line: the minimum number of strokes required to see a string of length exactly $$$n$$$ in the textarea.

Examples
Input
1 4
Output
3
Input
100 199
Output
7

I. LTS and rectangular area union
time limit per test
4.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In another parallel world, ltslts is a fantastic engineer, he build $$$n$$$ rectangular rooms, numbered from $$$1$$$ to $$$n$$$. From a bird's-eye view, the rooms are arranged on a 2-dimensional plane, with axis-aligned. The southern wall of each room has y-coordinate 0.

The $$$i$$$-th rectangular room has southwest corner $$$(L_i, 0)$$$ and the northeast corner $$$(R_i, H_i)$$$. Since houses often have shared regions (such as a common living/dining area), these rooms may overlap with one another. Due to these houses are built on the mountain, the height of these houses is decreasing.

Specifically, let $$$P_i$$$ be the area of the union of rooms $$$1 \cdots i$$$. Note that the area of the overlap only needs to be calculated once, and that the union might not form a single connected polygon.

Although ltslts is a fantastic engineer, his mathematical ability is very poor. Please help compute the product $$$(P_1 \times P_2 \times P_3 \times \cdots \times P_n)$$$. As this product may be very large, you need compute its value module $$$998244353$$$.

Formally, let $$$M = 998244353$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x \lt M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

It you don't know what is rectangular area union, you just need to remember, the area of the overlap only needs to be calculated once.

For instance, let's consider $$$(L_i, R_i, H_i)$$$ to representing a rectangular, if we have two rectangulars $$$(1, 3, 5)$$$ and $$$(2, 4, 5)$$$, the rectangular area union is $$$15$$$, because the area $$$(2, 3, 5)$$$ is overlap area, just need to calculate once.

Input

The first line contains a single integer $$$n(1 \leq n \leq 10^6)$$$, denoting the number of rooms.

In the next $$$n$$$ lines, each line contains three integers $$$L_i, R_i, H_i(1 \leq L_i, R_i, H_i \leq 10^9),$$$ representing the $$$i$$$-th rectangular.

It is guaranteed that $$$H_1 \geq H_2 \geq \cdots \geq H_n$$$ and $$$L_i \lt R_i$$$.

Output

Print a single integer in one line: the product $$$(P_1 \times P_2 \times P_3 \times \cdots \times P_n)$$$ module $$$998244353$$$.

Example
Input
2
1 4 5
2 3 5
Output
225

J. Hsueh- owns large quantities of apples
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The difference between this problem and LTS owns large quantities of apples is more than the data range, please read the statement carefully.

There are $$$n$$$ apples in Hsueh-'s bag, and $$$m$$$ kids around the man. Let's label these children $$$1$$$ to $$$m$$$.

Hsueh- take all of the apples and gave to the first child.

  • The first child got $$$n$$$ apples from Hsueh-. Next, he ate an apple and the remaining apples could just be divided into $$$x$$$ piles. He took the $$$x - 1$$$ piles and gave the remaining pile to the second child.
  • The second child got $$$\displaystyle \frac{(n - 1)}{x}$$$ apples from the first child. Next, he ate an apple and the remaining apples could just be divided into $$$x$$$ piles. He took the $$$x - 1$$$ piles and gave the remaining pile to the third child.
  • $$$\cdots$$$
  • The $$$i$$$-th child got some apples from the ($$$i - 1$$$)-th child. Next, he ate an apple and the remaining apples could just be divided into $$$x$$$ piles. He took the $$$x - 1$$$ piles and gave the remaining pile to the ($$$i + 1$$$)-th child.
  • $$$\cdots$$$
  • The last child got some apples from the Penultimate child, Next, he ate an apple and the remaining apples could just be divided into $$$x$$$ piles. He took $$$x - 1$$$ piles and go away.

It should be noted that the number of apples in a pile left by last child must be a positive integer.

Until the last child go away, Hsueh- wants to know what is the minimum $$$n$$$ that meets all requirements.

Since $$$n$$$ can be very large, output $$$n$$$ modulo $$$998244353$$$. Formally, let $$$M = 998244353$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x \lt M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

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, the first line contains two integers $$$m(1 \leq m \leq 10^9)$$$ and $$$x(2 \leq x \leq 10^9)$$$, denoting the number of children and the number of piles in operation of each child.

Output

For each test case, print a single integer in one line: minimum of $$$n$$$ modulo $$$998244353$$$ that meets all requirements.

Example
Input
1
1000000000 1000000000
Output
720560972

K. LTS buy wine
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

On a sunny afternoon, ltslts' friends came to visit him. So he decided to buy some wine.

All the wine in the store are known to be on the same shelf, these wine are numbered $$$1$$$ through $$$n$$$ from left to right.

ltslts' friends is very wealthy, so ltslts will buy all the wine. But his drinking capacity is limited, so he only buys a bottle of wine every day.

As we all konw, the longer the wine, the more valuable it is.

In the first, the $$$i$$$-th bottle of wine has a value $$$v_i$$$. On the $$$t$$$-th day, ltslts will buy a bottle of wine on the far left or right side of the shelf, and get the value $$$v_i \cdot t$$$.

Obviously, all the wine will be bought by ltslts on the $$$n$$$-th day, and he wants to know what the maximum value he could get.

For instance, we consider $$$n = 5$$$, and the value of wine are $$$\{1, 3, 1, 5, 2\}$$$.

  • On the first day, we buy the wine on the far left and got $$$1$$$ value point, the remaining wine are $$$\{3, 1, 5, 2\}$$$.
  • On the second day, we buy the wine on the far right and got $$$4$$$ value point, the remaining wine are $$$\{3, 1, 5\}$$$.
  • On the third day, we buy the wine on the far left and got $$$9$$$ value point, the remaining wine are $$$\{1, 5\}$$$.
  • On the fourth day, we buy the wine on the far left and got $$$4$$$ value point, the remaining wine are $$$\{5\}$$$.
  • On the final day, we got $$$25$$$ value point, and we got a total of $$$43$$$ value point.
Input

The first line contains a single integer $$$n(1 \leq n \leq 2000)$$$, denoting the number of wine.

In the next $$$n$$$ lines, each line contains a single integer $$$v_i(1 \leq v_i \leq 10^9)$$$ denoting the value of the $$$i$$$-th wine.

Output

Print a single integer in one line: the maximum value ltslts could get.

Example
Input
5
1
3
1
5
2
Output
43

L. Line problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

We have learned your team is good at geometry problems. So we ask you a simple problem.

Now you have two segments in a $$$2$$$-dimensional plane, you should tell us the length of the intersection of two line segments.

What you need to pay attention to is, if these two line segments intersect at one point, we consider their intersecting length to be $$$0$$$.

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.

The first line contains four integers $$$x_1$$$, $$$y_1$$$, $$$x_2$$$, $$$y_2$$$$$$(-10^{9} \leq x_1, y_1, x_2, y_2 \leq 10^{9})$$$, representing the two points of the first line segment.

The second line contains four integers $$$x_3$$$, $$$y_3$$$, $$$x_4$$$, $$$y_4$$$$$$(-10^{9} \leq x_3, y_3, x_4, y_4 \leq 10^{9})$$$, representing the two points of the second line segment.

Output

For each test case, print the length of the intersection of two line line segments.

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

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^{-9}$$$.

Example
Input
2
0 0 3 3
1 1 2 2
0 0 1 1
1 1 2 2
Output
1.41421356237309514547
0.00000000000000000000

M. Rikka with Random Graph
time limit per test
2.5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Hello everyone! I am your old friend Rikka. Welcome to Hangzhou Normal U. This is an interesting problem, which is problem about the Graph. I promise you all that this should be easiest problem for most people.

A random graph, or a random directed graph, is a graph which edges generated by randomly.

In this problem, we constructed a directed graph by randomly, you need to design a special data structure to support the following operations:

  • $$$u \; v$$$, query weather point $$$u$$$ can reach point $$$v$$$ through some edges.

If you are Candidate Master or Master or Grandmaster or Legendary Grandmaster or high level title in Programming competition, you will find that this problem is very easy to solve. Even this problem can be solved on any category of graph. Don't even care of this graph is randomly generated.

So in order to reflect your programming ability, you need to answer these queries online.

To decrease the size of the input, Rikka provides an directed graph via a random number generator with given random seeds , denoted by two integers $$$k_1$$$ and $$$k_2$$$, Supposing the number of vertices and edges in the graph are $$$n$$$ and $$$m$$$ respectively, the following code in C++ tells you how to generate the graph and store the $$$i$$$-th directed edge between the vertex $$$u[i]$$$ and $$$v[i]$$$ in corresponding arrays. You can use the code directly in your submissions.

Input

The first line contains $$$5$$$ integers, $$$n(2 \leq n \leq 10^5)$$$, $$$m(1 \leq m \leq \min(10^5, n \cdot (n - 1)))$$$, $$$q(1 \leq q \leq 10^5)$$$, $$$k_1, k_2(1 \leq k_1, k_2 \leq 10^9)$$$. Denoting the number of points, the number of edges, the number of queries, and the random seeds.

It is guaranteed that $$$k_1$$$ and $$$k_2$$$ are chosen randomly except for the sample.

Since the graph is randomly generated, it may contains self-loop or multiple edges.

In the next $$$q$$$ lines, each line contains two integers $$$u$$$ and $$$v(1 \leq u, v \leq n, u \neq v)$$$, representing query weather point $$$u$$$ can reach $$$v$$$ through some edges.

What you need to pay attention to is, you need to answer these queries online, so these queries will not be given to you at the beginning.

Output

For each queries, you need output "Yes"(without quotes) if $$$u$$$ can reach $$$v$$$ through some edges, or output "No"(without quotes).

Interaction

Initially, you will get the $$$n, m, q, k_1, k_2$$$ and the first queries.

You need to answer the $$$i$$$-th queries correctly before the $$$(i + 1)$$$-th queries will be given to you.

If your answer is legal, Jury will return the next querires to you or terminate the program if the answer is last answer.

If Jury return $$$-1$$$ instead of a next queries, that means you made an invalid answer.

Exit immediately after receiving $$$-1$$$ and you will see wrong answer verdict. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.

After printing a answer, do not forget to output end of line and flush the output. Otherwise, you will get idleness limit exceeded. To do this, use:

  • fflush(stdout) or cout.flush() in C++;
  • System.out.flush() in Java;
  • flush(output) in Pascal;
  • stdout.flush() in Python;
  • See the documentation for other languages.
Examples
Input
10 90 3 123456789 987654321
1 2
2 1
10 9
Output
No
No
Yes
Input
2 1 1 123456789 987654321
1 2
Output
No