2020 ICPC, COMPFEST 12, Indonesia Multi-Provincial Contest (Unrated, Online Mirror, ICPC Rules, Teams Preferred)
A. Arena of Greed
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Lately, Mr. Chanek frequently plays the game Arena of Greed. As the name implies, the game's goal is to find the greediest of them all, who will then be crowned king of Compfestnesia.

The game is played by two people taking turns, where Mr. Chanek takes the first turn. Initially, there is a treasure chest containing $$$N$$$ gold coins. The game ends if there are no more gold coins in the chest. In each turn, the players can make one of the following moves:

  • Take one gold coin from the chest.
  • Take half of the gold coins on the chest. This move is only available if the number of coins in the chest is even.

Both players will try to maximize the number of coins they have. Mr. Chanek asks your help to find the maximum number of coins he can get at the end of the game if both he and the opponent plays optimally.

Input

The first line contains a single integer $$$T$$$ $$$(1 \le T \le 10^5)$$$ denotes the number of test cases.

The next $$$T$$$ lines each contain a single integer $$$N$$$ $$$(1 \le N \le 10^{18})$$$.

Output

$$$T$$$ lines, each line is the answer requested by Mr. Chanek.

Example
Input
2
5
6
Output
2
4
Note

For the first case, the game is as follows:

  1. Mr. Chanek takes one coin.
  2. The opponent takes two coins.
  3. Mr. Chanek takes one coin.
  4. The opponent takes one coin.

For the second case, the game is as follows:

  1. Mr. Chanek takes three coins.
  2. The opponent takes one coin.
  3. Mr. Chanek takes one coin.
  4. The opponent takes one coin.

B. Blue and Red of Our Faculty!
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

It's our faculty's 34th anniversary! To celebrate this great event, the Faculty of Computer Science, University of Indonesia (Fasilkom), held CPC - Coloring Pavements Competition. The gist of CPC is two players color the predetermined routes of Fasilkom in Blue and Red. There are $$$N$$$ Checkpoints and $$$M$$$ undirected predetermined routes. Routes $$$i$$$ connects checkpoint $$$U_i$$$ and $$$V_i$$$, for $$$(1 \le i \le M)$$$. It is guaranteed that any pair of checkpoints are connected by using one or more routes.

The rules of CPC is as follows:

  • Two players play in each round. One player plays as blue, the other plays as red. For simplicity, let's call these players $$$Blue$$$ and $$$Red$$$.
  • $$$Blue$$$ will color every route in he walks on blue, $$$Red$$$ will color the route he walks on red. Both players start at checkpoint number $$$1$$$. Initially, all routes are gray.
  • Each phase, from their current checkpoint, $$$Blue$$$ and $$$Red$$$ select a different gray route and moves to the checkpoint on the other end of the route simultaneously.
  • The game ends when $$$Blue$$$ or $$$Red$$$ can no longer move. That is, there is no two distinct gray routes they can choose to continue moving.

Chaneka is interested in participating. However, she does not want to waste much energy. So, She is only interested in the number of final configurations of the routes after each round. Turns out, counting this is also exhausting, so Chaneka asks you to figure this out!

Two final configurations are considered different if there is a route $$$U$$$ in a different color in the two configurations.

Input

The first line contains two integers $$$N$$$ and $$$M$$$. $$$N$$$ $$$(2 \le N \le 2 \cdot 10^3)$$$ denotes the number of checkpoints, $$$M$$$ $$$(1 \le M \le 2 \cdot N)$$$ denotes the number of routes. It is guaranteed that every checkpoint except checkpoint $$$1$$$ has exactly two routes connecting it.

The next $$$M$$$ lines each contains two integers $$$U_i$$$ and $$$V_i$$$ $$$(1 \le U_i, V_i \le N, U_i \ne V_i)$$$, which denotes the checkpoint that route $$$i$$$ connects.

It is guaranteed that for every pair of checkpoints, there exists a path connecting them directly or indirectly using the routes.

Output

Output a single integer which denotes the number of final configurations after each round of CPC modulo $$$10^9 + 7$$$

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

Every possible final configuration for the example is listed below:

The blue-colored numbers give the series of moves $$$Blue$$$ took, and the red-colored numbers give the series of moves $$$Red$$$ took.

C. Captain of Knights
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Mr. Chanek just won the national chess tournament and got a huge chessboard of size $$$N \times M$$$. Bored with playing conventional chess, Mr. Chanek now defines a function $$$F(X, Y)$$$, which denotes the minimum number of moves to move a knight from square $$$(1, 1)$$$ to square $$$(X, Y)$$$. It turns out finding $$$F(X, Y)$$$ is too simple, so Mr. Chanek defines:

$$$G(X, Y) = \sum_{i=X}^{N} \sum_{j=Y}^{M} F(i, j)$$$

Given X and Y, you are tasked to find $$$G(X, Y)$$$.

A knight can move from square $$$(a, b)$$$ to square $$$(a', b')$$$ if and only if $$$|a - a'| \gt 0$$$, $$$|b - b'| \gt 0$$$, and $$$|a - a'| + |b - b'| = 3$$$. Of course, the knight cannot leave the chessboard.

Input

The first line contains an integer $$$T$$$ $$$(1 \le T \le 100)$$$, the number of test cases.

Each test case contains a line with four integers $$$X$$$ $$$Y$$$ $$$N$$$ $$$M$$$ $$$(3 \leq X \leq N \leq 10^9, 3 \leq Y \leq M \leq 10^9)$$$.

Output

For each test case, print a line with the value of $$$G(X, Y)$$$ modulo $$$10^9 + 7$$$.

Example
Input
2
3 4 5 6
5 5 8 8
Output
27
70

D. Danger of Mad Snakes
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Mr. Chanek The Ninja is one day tasked with a mission to handle mad snakes that are attacking a site. Now, Mr. Chanek already arrived at the hills where the destination is right below these hills. The mission area can be divided into a grid of size $$$1000 \times 1000$$$ squares. There are $$$N$$$ mad snakes on the site, the i'th mad snake is located on square $$$(X_i, Y_i)$$$ and has a danger level $$$B_i$$$.

Mr. Chanek is going to use the Shadow Clone Jutsu and Rasengan that he learned from Lord Seventh to complete this mission. His attack strategy is as follows:

  1. Mr. Chanek is going to make $$$M$$$ clones.
  2. Each clone will choose a mad snake as the attack target. Each clone must pick a different mad snake to attack.
  3. All clones jump off the hills and attack their respective chosen target at once with Rasengan of radius $$$R$$$. If the mad snake at square $$$(X, Y)$$$ is attacked with a direct Rasengan, it and all mad snakes at squares $$$(X', Y')$$$ where $$$max(|X' - X|, |Y' - Y|) \le R$$$ will die.
  4. The real Mr. Chanek will calculate the score of this attack. The score is defined as the square of the sum of the danger levels of all the killed snakes.

Now Mr. Chanek is curious, what is the sum of scores for every possible attack strategy? Because this number can be huge, Mr. Chanek only needs the output modulo $$$10^9 + 7$$$.

Input

The first line contains three integers $$$N$$$ $$$M$$$ $$$R$$$ $$$(1 \le M \le N \le 2 \cdot 10^3, 0 \le R \lt 10^3)$$$, the number of mad snakes, the number of clones, and the radius of the Rasengan.

The next $$$N$$$ lines each contains three integers, $$$X_i$$$, $$$Y_i$$$, dan $$$B_i$$$ $$$(1 \le X_i, Y_i \le 10^3, 1 \le B_i \le 10^6)$$$. It is guaranteed that no two mad snakes occupy the same square.

Output

A line with an integer that denotes the sum of scores for every possible attack strategy.

Example
Input
4 2 1
1 1 10
2 2 20
2 3 30
5 2 40
Output
33800
Note

Here is the illustration of all six possible attack strategies. The circles denote the chosen mad snakes, and the blue squares denote the region of the Rasengan:

So, the total score of all attacks is: $$$3.600 + 3.600 + 4.900 + 3.600 + 10.000 + 8.100 = 33.800$$$.

E. Excitation of Atoms
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Mr. Chanek is currently participating in a science fair that is popular in town. He finds an exciting puzzle in the fair and wants to solve it.

There are $$$N$$$ atoms numbered from $$$1$$$ to $$$N$$$. These atoms are especially quirky. Initially, each atom is in normal state. Each atom can be in an excited. Exciting atom $$$i$$$ requires $$$D_i$$$ energy. When atom $$$i$$$ is excited, it will give $$$A_i$$$ energy. You can excite any number of atoms (including zero).

These atoms also form a peculiar one-way bond. For each $$$i$$$, $$$(1 \le i \lt N)$$$, if atom $$$i$$$ is excited, atom $$$E_i$$$ will also be excited at no cost. Initially, $$$E_i$$$ = $$$i+1$$$. Note that atom $$$N$$$ cannot form a bond to any atom.

Mr. Chanek must change exactly $$$K$$$ bonds. Exactly $$$K$$$ times, Mr. Chanek chooses an atom $$$i$$$, $$$(1 \le i \lt N)$$$ and changes $$$E_i$$$ to a different value other than $$$i$$$ and the current $$$E_i$$$. Note that an atom's bond can remain unchanged or changed more than once. Help Mr. Chanek determine the maximum energy that he can achieve!

note: You must first change exactly $$$K$$$ bonds before you can start exciting atoms.

Input

The first line contains two integers $$$N$$$ $$$K$$$ $$$(4 \le N \le 10^5, 0 \le K \lt N)$$$, the number of atoms, and the number of bonds that must be changed.

The second line contains $$$N$$$ integers $$$A_i$$$ $$$(1 \le A_i \le 10^6)$$$, which denotes the energy given by atom $$$i$$$ when on excited state.

The third line contains $$$N$$$ integers $$$D_i$$$ $$$(1 \le D_i \le 10^6)$$$, which denotes the energy needed to excite atom $$$i$$$.

Output

A line with an integer that denotes the maximum number of energy that Mr. Chanek can get.

Example
Input
6 1
5 6 7 8 10 2
3 5 6 7 1 10
Output
35
Note

An optimal solution to change $$$E_5$$$ to 1 and then excite atom 5 with energy 1. It will cause atoms 1, 2, 3, 4, 5 be excited. The total energy gained by Mr. Chanek is (5 + 6 + 7 + 8 + 10) - 1 = 35.

Another possible way is to change $$$E_3$$$ to 1 and then exciting atom 3 (which will excite atom 1, 2, 3) and exciting atom 4 (which will excite atom 4, 5, 6). The total energy gained by Mr. Chanek is (5 + 6 + 7 + 8 + 10 + 2) - (6 + 7) = 25 which is not optimal.

F. Flamingoes of Mystery
time limit per test
2 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().

Mr. Chanek wants to buy a flamingo to accompany his chickens on his farm. Before going to the pet shop, Mr. Chanek stops at an animal festival to have fun. It turns out there is a carnival game with a flamingo as the prize.

There are $$$N$$$ mysterious cages, which are numbered from $$$1$$$ to $$$N$$$. Cage $$$i$$$ has $$$A_i$$$ $$$(0 \le A_i \le 10^3)$$$ flamingoes inside $$$(1 \le i \le N)$$$. However, the game master keeps the number of flamingoes inside a secret. To win the flamingo, Mr. Chanek must guess the number of flamingoes in each cage.

Coincidentally, Mr. Chanek has $$$N$$$ coins. Each coin can be used to ask once, what is the total number of flamingoes inside cages numbered $$$L$$$ to $$$R$$$ inclusive? With $$$L \lt R$$$.

Input

Use standard input to read the responses of your questions.

Initially, the judge will give an integer $$$N$$$ $$$(3 \le N \le 10^3)$$$, the number of cages, and the number of coins Mr. Chanek has.

For each of your questions, the jury will give an integer that denotes the number of flamingoes from cage $$$L$$$ to $$$R$$$ inclusive.

If your program does not guess the flamingoes or ask other questions, you will get "Wrong Answer". Of course, if your program asks more questions than the allowed number, your program will get "Wrong Answer".

Output

To ask questions, your program must use standard output.

Then, you can ask at most $$$N$$$ questions. Questions are asked in the format "? L R", ($$$1 \le L \lt R \le N$$$).

To guess the flamingoes, print a line that starts with "!" followed by $$$N$$$ integers where the $$$i$$$-th integer denotes the number of flamingo in cage $$$i$$$. After answering, your program must terminate or will receive the "idle limit exceeded" verdict. You can only guess the flamingoes once.

Examples
Input
6
 
5
 
15
 
10
 
Output
 
? 1 2
 
? 5 6
 
? 3 4
 
! 1 4 4 6 7 8
Note

In the sample input, the correct flamingoes amount is $$$[1, 4, 4, 6, 7, 8]$$$.

H. Huge Boxes of Animal Toys
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Chaneka has a hobby of playing with animal toys. Every toy has a different fun value, a real number. Chaneka has four boxes to store the toys with specification:

  • The first box stores toys with fun values in range of $$$(-\infty,-1]$$$.
  • The second box stores toys with fun values in range of $$$(-1, 0)$$$.
  • The third box stores toys with fun values in range of $$$(0, 1)$$$.
  • The fourth box stores toys with fun value in range of $$$[1, \infty)$$$.

Chaneka has $$$A$$$, $$$B$$$, $$$C$$$, $$$D$$$ toys in the first, second, third, and fourth box, respectively. One day she decides that she only wants one toy, a super toy. So she begins to create this super toy by sewing all the toys she has.

While the number of toys Chaneka has is more than 1, she takes two different toys randomly and then sews them together, creating a new toy. The fun value of this new toy is equal to the multiplication of fun values of the sewn toys. She then puts this new toy in the appropriate box. She repeats this process until she only has one toy. This last toy is the super toy, and the box that stores this toy is the special box.

As an observer, you only know the number of toys in each box initially but do not know their fun values. You also don't see the sequence of Chaneka's sewing. Determine which boxes can be the special box after Chaneka found her super toy.

Input

The first line has an integer $$$T$$$ $$$(1 \le T \le 5 \cdot 10^4)$$$, the number of test cases.

Every case contains a line with four space-separated integers $$$A$$$ $$$B$$$ $$$C$$$ $$$D$$$ $$$(0 \le A, B, C, D \le 10^6, A + B + C + D \gt 0)$$$, which denotes the number of toys in the first, second, third, and fourth box, respectively.

Output

For each case, print four space-separated strings. Each string represents the possibility that the first, second, third, and fourth box can be the special box from left to right.

For each box, print "Ya" (Without quotes, Indonesian for yes) if that box can be the special box. Print "Tidak" (Without quotes, Indonesian for No) otherwise.

Example
Input
2
1 2 0 1
0 1 0 0
Output
Ya Ya Tidak Tidak
Tidak Ya Tidak Tidak
Note

For the first case, here is a scenario where the first box is the special box:

  • The first box had toys with fun values $$$\{-3\}$$$.
  • The second box had toys with fun values $$$\{ -0.5, -0.5 \}$$$
  • The fourth box had toys with fun values $$$\{ 3 \}$$$

The sewing sequence:

  1. Chaneka sews the toy with fun $$$-0.5$$$ and $$$-0.5$$$ to a toy with fun $$$0.25$$$ and then put it in the third box.
  2. Chaneka sews the toy with fun $$$-3$$$ and $$$0.25$$$ to a toy with fun $$$-0.75$$$ and then put it in the second box.
  3. Chaneka sews the toy with fun $$$-0.75$$$ and $$$3$$$ to a toy with fun $$$-1.25$$$ and then put it in the first box, which then became the special box.

Here is a scenario where the second box ends up being the special box:

  • The first box had toys with fun values $$$\{-3\}$$$
  • The second box had toys with fun values $$$\{ -0.33, -0.25 \}$$$.
  • The fourth box had toys with fun values $$$\{ 3 \}$$$.

The sewing sequence:

  1. Chaneka sews the toy with fun $$$-3$$$ and $$$-0.33$$$ to a toy with fun $$$0.99$$$ and then put it in the third box.
  2. Chaneka sews the toy with fun $$$0.99$$$ and $$$3$$$ to a toy with fun $$$2.97$$$ and then put in it the fourth box.
  3. Chaneka sews the toy with fun $$$2.97$$$ and $$$-0.25$$$ to a toy with fun $$$-0.7425$$$ and then put it in the second box, which then became the special box.
There is only one toy for the second case, so Chaneka does not have to sew anything because that toy, by definition, is the super toy.

I. Impressive Harvesting of The Orchard
time limit per test
7 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Mr. Chanek has an orchard structured as a rooted ternary tree with $$$N$$$ vertices numbered from $$$1$$$ to $$$N$$$. The root of the tree is vertex $$$1$$$. $$$P_i$$$ denotes the parent of vertex $$$i$$$, for $$$(2 \le i \le N)$$$. Interestingly, the height of the tree is not greater than $$$10$$$. Height of a tree is defined to be the largest distance from the root to a vertex in the tree.

There exist a bush on each vertex of the tree. Initially, all bushes have fruits. Fruits will not grow on bushes that currently already have fruits. The bush at vertex $$$i$$$ will grow fruits after $$$A_i$$$ days since its last harvest.

Mr. Chanek will visit his orchard for $$$Q$$$ days. In day $$$i$$$, he will harvest all bushes that have fruits on the subtree of vertex $$$X_i$$$. For each day, determine the sum of distances from every harvested bush to $$$X_i$$$, and the number of harvested bush that day. Harvesting a bush means collecting all fruits on the bush.

For example, if Mr. Chanek harvests all fruits on subtree of vertex $$$X$$$, and harvested bushes $$$[Y_1, Y_2, \dots, Y_M]$$$, the sum of distances is $$$\sum_{i = 1}^M \text{distance}(X, Y_i)$$$

$$$\text{distance}(U, V)$$$ in a tree is defined to be the number of edges on the simple path from $$$U$$$ to $$$V$$$.

Input

The first line contains two integers $$$N$$$ and $$$Q$$$ $$$(1 \le N,\ Q,\le 5 \cdot 10^4)$$$, which denotes the number of vertices and the number of days Mr. Chanek visits the orchard.

The second line contains $$$N$$$ integers $$$A_i$$$ $$$(1 \le A_i \le 5 \cdot 10^4)$$$, which denotes the fruits growth speed on the bush at vertex $$$i$$$, for $$$(1 \le i \le N)$$$.

The third line contains $$$N-1$$$ integers $$$P_i$$$ $$$(1 \le P_i \le N, P_i \ne i)$$$, which denotes the parent of vertex $$$i$$$ in the tree, for $$$(2 \le i \le N)$$$. It is guaranteed that each vertex can be the parent of at most $$$3$$$ other vertices. It is also guaranteed that the height of the tree is not greater than $$$10$$$.

The next $$$Q$$$ lines contain a single integer $$$X_i$$$ $$$(1 \le X_i \le N)$$$, which denotes the start of Mr. Chanek's visit on day $$$i$$$, for $$$(1 \le i \le Q)$$$.

Output

Output $$$Q$$$ lines, line $$$i$$$ gives the sum of distances from the harvested bushes to $$$X_i$$$, and the number of harvested bushes.

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

For the first example:

  • On day 1, Mr. Chanek starts at vertex $$$2$$$ and can harvest the bush at vertex 2.
  • On day 2, Mr. Chanek starts at vertex $$$1$$$ and only harvest from bush $$$1$$$ (bush 2's fruit still has not grown yet).
  • On day 3, Mr. Chanek starts at vertex $$$1$$$ and harvests the fruits on bush $$$1$$$ and $$$2$$$. The sum of distances from every harvested bush to $$$1$$$ is $$$1$$$.

For the second example, Mr. Chanek always starts at vertex $$$1$$$. The bushes which Mr. Chanek harvests on day one, two, and three are $$$[1, 2, 3, 4, 5], [2, 3], [1, 2, 3, 5]$$$, respectively.