The 20th Hangzhou City University Programming Contest
A. Zawei The Rock
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Zawei likes Bocchi The Rock very much, so today he wants you to output the string "Jesus Bocchi".

Input

No input.

Output

The output contains a line with "Jesus Bocchi" (without quote).

Example
Input
(no input)
Output
Jesus Bocchi

B. Emoji Master BSQ
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

As everyone knows, BSQ is an emoji master.

Now BSQ has given you the conversion rules of $$$n$$$ words. Please convert what BSQ said according to the rules.

Input

The first line contains two integer $$$n, m$$$ $$$(1 \le n, m \le 100)$$$.

Then $$$n$$$ lines follow, the $$$i$$$-th of them contains two strings $$$s_i$$$ and $$$t_i$$$ $$$(1 \le |s_i|, |t_i| \le 10)$$$ — This means that the word $$$s_i$$$ needs to be converted into the word $$$t_i$$$, it is guaranteed all $$$s_i$$$ and $$$t_i$$$ are distinct.

The next line contains $$$m$$$ words $$$p_1, p_2, ... , p_m$$$ $$$(1 \le |p_i| \le 10)$$$, separate with a space. — This is what BSQ said. It is guaranteed that for each integer $$$i$$$ $$$(1 \le i \le m)$$$, there exist an integer $$$j$$$ $$$(1 \le j \le n)$$$ satisfies $$$p_i = s_j$$$.

It is guaranteed that all words contain only lowercase English letters.

Output

Output one line contains $$$m$$$ words $$$q_1, q_2, ... , q_m$$$, separate with a space. — This represents the result after conversion.

Example
Input
3 4
wo i
qiu ball
ni you
wo qiu qiu ni
Output
i ball ball you

C. Genshin Master
time limit per test
1 second
memory limit per test
128 megabytes
input
standard input
output
standard output

Yoimiya is playing a rhythm game. There are $$$6$$$ tracks in this game. For any second, if there is a block on a track, the player can gain $$$1$$$ point by pressing the button of that track.

As you can see in the picture, Yoimiya has only one hand to play the game, which means she can press at most $$$5$$$ tracks simultaneously.

Yoimiya playing the rhythm game

Now give you the time intervals of each track that exists a block. Please help Yoimiya calculate the maximum score she can achieve.

Notice that for any time interval, she does NOT have to press it continuously, which is different from the actual game. This means all blocks appear for exactly one second. Interval $$$[l, r]$$$ means there are $$$r - l + 1$$$ blocks on a track from the $$$l$$$-th second to $$$r$$$-th second.

Input

The input consists of $$$6$$$ lines, each line representing a track.

Each line starts with a single integer $$$n$$$ $$$(1 \le n \le 2 \times 10^5)$$$ — the number of time intervals.

Then $$$n$$$ pairs of integers follow ($$$2n$$$ integers in total). Each pair of integers $$$s, t$$$ $$$(1 \le s \le t \le 10^8)$$$ represents a time interval $$$[s, t]$$$ with blocks on this track. It's guaranteed that intervals will not overlap and are sorted in ascending order of $$$s$$$. ($$$t_i \lt s_j$$$ if and only if $$$i \lt j$$$)

It is guaranteed that $$$\sum n \le 2 \times 10^5$$$.

Output

Output a single integer in a line — the maximum score Yoimiya can achieve.

Examples
Input
1 1 4
5 1 4 19 19 81 81 114 514 1919 1919810
1 1 4
1 1 4
1 1 4
1 1 4
Output
1918315
Input
1 1 10
1 2 11
1 3 12
1 4 13
1 5 14
1 6 15
Output
55

D. Add 9 Zeros Ⅱ
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

You have an array $$$a$$$ of $$$n$$$ distinct integers.

Now you need to select $$$m$$$ integers from the array $$$a$$$ to form a new array $$$b$$$ so that $$$b$$$ satisfies the following condition:

  • There has no two integers $$$i, j$$$ $$$(1 \le i, j \le m)$$$ satisfies $$$b_i = b_j + 9$$$.

You need to answer the maximum value of $$$m$$$.

Input

The first line of the input contains one integer $$$n$$$ $$$(1\le n\le 2 \times 10^5)$$$.

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

Output

Print one integer — the number satisfying the conditions above.

Example
Input
9
11 4 5 14 1 9 19 8 10
Output
7

E. XOR on Tree
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Hile likes XOR and trees very much.

She will give you a rooted tree with $$$n$$$ vertices. The root is $$$1$$$. The vertices are numbered from $$$1$$$ to $$$n$$$. Each vertex has a weight $$$a_i$$$.

Then she will give you $$$q$$$ queries. Each query consists of two numbers $$$u,v$$$. You need to find a vertex $$$i$$$ in the subtree of $$$v$$$ to maximize the bitwise XOR of $$$a_u$$$ and $$$a_i$$$ and tell Hile the maximum value.

Input

The first line contains one integer $$$n$$$ $$$(1 \le n \le 2 \times 10^5)$$$ — the number of vertices.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots , a_n$$$ $$$(1 \le a_i \lt 2^{30})$$$ — the weight of each vertex.

Then $$$n - 1$$$ lines follow, each containing two integers $$$u,v$$$ $$$(1 \le u,v \le n, u \ne v)$$$ denoting an edge connecting vertex $$$u$$$ with vertex $$$v$$$. It is guaranteed that these edges form a tree.

The following line contains one integer $$$q$$$ $$$(1 \le q \le 2 \times 10^5)$$$ — the number of queries.

Then $$$q$$$ lines follow, each containing two integers $$$u,v$$$ $$$(1 \le u,v \le n)$$$ denoting a query.

Output

For each query, print a single integer in a line — the maximum value of XOR.

Examples
Input
5
1 3 3 2 1
1 2
1 3
2 4
2 5
3
2 3
3 2
1 2
Output
0
2
3
Input
1
114514
1
1 1
Output
0
Note

This is the tree of the first sample:

For the first query, we can only choose $$$3$$$ as $$$i$$$ because it is the only vertex of the subtree of $$$3$$$. $$$a_2 \oplus a_3 = 0$$$.

For the second query, we can choose $$$2,4,5$$$ because they are in the subtree of $$$2$$$. We choose $$$5$$$ as $$$i$$$ to maximize $$$a_i \oplus a_u$$$, $$$a_5 \oplus a_3 = 2$$$.

For the last query, we choose $$$4$$$ as $$$i$$$, $$$a_4 \oplus a_1 = 3$$$.

F. Crazy Thursday, V me 50!
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

BSQ has $$$n$$$ QQ groups, and each group consists of some rich guys. BSQ can send a mystery message to these groups to get some money. The rules are the following:

  • BSQ can send "Crazy Thursday, V me 50!" to some group he has not sent the message to before.
  • Once BSQ sends the message to some group, the rich guys in this group will give him some money one by one in the lexicographical order of their name.
  • Each rich guy will give BSQ money as much as possible, but they must meet two constraints: Each guy will give BSQ at most $$$50$$$ in total (NOT in a single group), and BSQ can get at most $$$114$$$ in one group.
  • One rich guy can be in several groups. Every rich guy has a unique name consisting of lowercase letters. No two same names will be in the same group.

Now BSQ has decided to send messages to exactly $$$k$$$ different groups. He can decide the order of groups to send the message to. What is the maximum amount of money he can get?

Lexicographical order is defined in the following way. When we compare $$$s$$$ and $$$t$$$, first, we find the leftmost position with differing characters: $$$s_i \ne t_i$$$. If there is no such position (i. e. $$$s$$$ is a prefix of $$$t$$$ or vice versa), the shorter string is less. Otherwise, we compare characters $$$s_i$$$ and $$$t_i$$$ according to their order in the alphabet.

Input

The first line contains two integers $$$n$$$ and $$$k$$$ $$$(1 \le k \le n \le 8)$$$ — the number of groups and groups BSQ will send a message to.

Then $$$n$$$ lines follow, each starting with an integer $$$m$$$ $$$(1 \le m \le 10)$$$, the number of rich guys in this group. Following $$$m$$$ strings, the names of the rich guys. The length of each name will not exceed $$$10$$$. It is NOT guaranteed that the names have been sorted.

Output

Print a single integer in a line — the maximum amount BSQ can get.

Examples
Input
2 2
3 alice boboge cityu
3 ddddc faker euler
Output
228
Input
2 2
4 alice boboge cityu ddddc
1 alice
Output
164
Input
3 2
1 zawei
3 hile zawei meow
3 meow zawei hile
Output
150
Note

For the first sample, BSQ gets $$$114$$$ in both groups, $$$228$$$ in total.

For the second sample, BSQ first sends a message to the second group so that alice will give him $$$50$$$, and then other people in the first group will give him $$$114$$$. If BSQ starts with the first group, he will only get $$$114$$$ because alice has already given him $$$50$$$ in the first group.

G. Domino
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Yolo has $$$n$$$ domino cards, and the $$$i$$$-th of these cards has two numbers written on it: $$$A_i$$$ on the front side, and $$$B_i$$$ on the back side.

You should pick $$$K$$$ cards from them, then you can get the score of the sum of the numbers written on the front of the $$$K$$$ cards.

After that, you have to choose $$$L$$$ cards from the cards you picked up and you can get the score of the sum of the numbers written on the back of the $$$L$$$ cards.

Now you need to tell Yolo the highest score you can get.

Input

The first line contains an integer $$$n\ (1 \leq n \leq 10^5)$$$.

The second line contains $$$N$$$ integers $$$A_1, A_2, ..., A_N\ (1 \leq A_i \leq 10^9)$$$.

The third line contains $$$N$$$ integers $$$B_1, B_2, ..., B_N\ (1 \leq B_i \leq 10^9)$$$.

The fourth line contains two integers $$$K$$$ and $$$L\ (1 \leq L \leq K \leq N)$$$.

Output

Print one line containing an integer, representing the highest score possible.

Examples
Input
5
9 7 2 2 9
5 2 2 3 1
2 1
Output
23
Input
5
9 7 2 2 9
5 9 2 3 1
2 1
Output
25

H. Maze
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

There are $$$n \times m$$$ grids. Some grids have a cake on them.

Now Meow plans to eat all the cakes on the grids. She has the following two ways to eat cakes:

  • Choose a grid with a cake and eat the cake so that she will get $$$p$$$ satisfaction.

  • Choose two adjacent grids with cakes and eat the cakes on them so that she will get $$$q$$$ satisfaction. Two grids are considered adjacent if they share a common edge.

Please answer what is the maximum satisfaction that Meow can get.

Input

The first line contains four integers $$$n, m$$$ $$$(1 \le n, m \le 300, 1 \le p, q \le 10^9)$$$.

The following $$$n$$$ lines contain $$$m$$$ integers each, the $$$j$$$-th element in the $$$i$$$-th line is $$$a_{ij}$$$ $$$(0 \le a_{ij} \le 1)$$$ — $$$a_{ij} =1$$$ means there is a cake on the grid of $$$i$$$-th row and $$$j$$$-th column, and $$$a_{ij} = 0$$$ means there is no cake.

Output

Print one integer — the number satisfying the conditions above.

Example
Input
2 3 114514 1919810
100
011
Output
2034324

I. Magic Tree
time limit per test
1 с
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given a rooted tree consisting of $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$ and vertex $$$1$$$ is the root of the tree. The depth of vertex $$$1$$$ is $$$1$$$.

A tree is a connected undirected graph with $$$n - 1$$$ edges.

Now there are $$$q$$$ tasks that you need to do, and the $$$i$$$-th task is one of the following three types:

  • $$$1$$$ $$$x$$$ $$$(\ 2 \le x \lt n + i\ )$$$ — Add a new vertex numbered $$$n + i$$$ between vertex $$$x$$$ and its parent vertex.

  • $$$2$$$ $$$x$$$ $$$(\ 2 \le x \lt n + i\ )$$$ — Delete the vertex $$$x$$$ and turn all child vertex of $$$x$$$ into the child vertex of its parent vertex.

  • $$$3$$$ $$$x$$$ $$$(\ 1 \le x \lt n + i\ )$$$ — Query the depth of the vertex $$$x$$$.

It is guaranteed that the vertex $$$x$$$ must exist in the current tree.

Input

The first line of the input contains two integers $$$n, q$$$ $$$(2 \le n \le 2 \times 10^5, 1 \le q \le 2 \times 10^5)$$$.

The second line contains $$$n - 1$$$ integers $$$p_2, p_3, ..., p_n$$$ — the parents of vertices from the second to the $$$n$$$-th $$$(1 ≤ p_i \lt i)$$$.

The next $$$q$$$ lines each line contains two integers, and the $$$i$$$-th line belongs to one of the three types mentioned above.

It is guaranteed that there has at least one query task.

Output

For each query task, you should output one line containing an integer.

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

J. Disjoint-Set-Union Sum
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Boboge has an array $$$a$$$ with $$$n$$$ numbers in a line. In the beginning, each number forms a set. Then Boboge will do the following merging operation $$$n-1$$$ times:

Pick up two adjacent sets, merge them, and add the value of the new set into $$$ans$$$. The value of a set is the sum of numbers in it.

After $$$n-1$$$ merging operations, exactly one set will be left.

A set can be represented in an interval $$$[l, r]$$$ of the original array. Two sets $$$i, j(l_i \lt l_j)$$$ are adjacent if and only if $$$r_i=l_j-1$$$. Note that the same numbers can be in one set.

Now Boboge wants to know the $$$\sum{ans}$$$ for all possible merging ways.

Input

The first consists of a single integer $$$n$$$ $$$(1 \le n \le 500)$$$ — the array's length.

The second line consists of $$$n$$$ integers $$$a_1, a_2,\dots,a_{n-1},a_n$$$ $$$(1 \le a_i \le 10^9)$$$ — the array.

Output

Output a single integer — the answer.

As the answer may be very large, print it modulo $$$998244353$$$.

Examples
Input
3
1 2 3
Output
20
Input
6
1 1 4 5 1 4
Output
5710
Input
10
689908266 691306300 127791789 650024903 820790283 179240641 548340689 541264423 994511361 993667526
Output
792245278
Note

For the first example, There are two possible ways of merging.

1. $$$[1],[2],[3] \rightarrow [1, 2], [3] \rightarrow [1, 2, 3]$$$, the $$$ans$$$ of this order is $$$3+6=9$$$.

2. $$$[1],[2],[3] \rightarrow [1], [2, 3] \rightarrow [1, 2, 3]$$$, the $$$ans$$$ of this order is $$$5+6=11$$$.

$$$\sum{ans} = 20$$$.

K. Equal Difference Prime
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Hile likes prime numbers very much.

Now he wants you to count how many quadruples $$$a, b, c, d$$$ $$$(1 \le a \lt b \lt c \lt d \le n)$$$ satisfy $$$b-a=c-b=d-c$$$ and $$$a, b, c, d$$$ are all prime numbers.

Input

The input contains only one integer $$$n$$$ $$$(1 \le n \le 10^6)$$$.

Output

Print one integer — the number satisfying the conditions above.

Example
Input
23
Output
1
Note

The only quadruples for the test case are $$$(5, 11, 17, 23)$$$.

L. Auto Chess
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Auto chess is a type of strategic game with elements similar to chess. In the preparation phase, players place characters on the battlefield, and then the characters battle against the opponent's characters without direct control from the players.

Auto chess

Kwords is developing a new auto chess game in which one character attacks by eliminating all enemies within a $$$45$$$-degree angle in front of it. However, Kwords doesn't know how to find the best direction for the character to destroy as many enemies as possible. Therefore, he has thrown this problem to you.

To simplify the problem, the chessboard can be viewed as a two-dimensional plane. The character's location is the origin $$$(0, 0)$$$. $$$n$$$ different two-dimensional integer coordinates represent the coordinates of the $$$n$$$ enemies. All enemies within the $$$45$$$-degree angle between the two rays firing from the origin will be eliminated, including those on the rays themselves. Given the corresponding chessboard data, calculate the maximum number of enemies the character can eliminate.

Input

The first line contains an integer $$$n$$$ $$$(1 \le n \le 10^5)$$$ — the number of enemies.

Then follow $$$n$$$ lines, each contains of two integers $$$x,y$$$ $$$(-10^4\leq x,y\leq 10^4)$$$ representing a coordinate of an enemy. It is guaranteed that $$$x \ne 0$$$ or $$$y \ne 0$$$, and all coordinates are distinct.

Output

A single integer — the maximum number of enemies the character can eliminate.

Examples
Input
2
1 2
2 1
Output
2
Input
2
1 100
100 1
Output
1
Input
3
1 1
2 2
3 3
Output
3

M. Jiubei and Construction
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Jiubei came up with a fantastic constructive problem.

For given $$$n$$$ and $$$k$$$, construct a sequence with $$$n$$$ distinct integer elements with the sum of $$$k$$$. The absolute value of any element can not exceed $$$10^9$$$.

Input

Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ $$$(1 \le t \le 2 \times 10 ^ 5)$$$ — the number of test cases. The description of test cases follows.

Each test case contains two integers $$$n$$$ $$$(1 \le n \le 2 \times 10 ^ 5)$$$ and $$$k$$$ $$$(-10^8 \le k \le 10^8)$$$ — the constraint of construction descripted above.

It is guaranteed that $$$\sum n \le 2 \times 10^5$$$ for all test cases.

Output

For each test case, output $$$n$$$ distinct integers in a line, the sum of which should be $$$k$$$. Remember, the absolute value of any element you give can not exceed $$$10^9$$$.

Example
Input
2
5 15
2 0
Output
1 2 3 4 5
2 -2