TheForces Round #30 (Good-Forces)
A. Good Target
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Yugandhar was a captain in a gully cricket match. There he needs to chase $$$n$$$ runs as the target. There are some weird rules involved.

  1. There are unlimited balls in a single over.
  2. Only a single batsman will play the match; there is no non-striker player.
  3. The batsman is only allowed to score $$$4$$$ or $$$6$$$ runs on every ball.
  4. It is guaranteed that the batsman can hit $$$4$$$ or $$$6$$$ runs on every ball (the batsman will not score $$$0$$$ runs on his/her chance).

In short, in this problem, a batsman always gets $$$4$$$ or $$$6$$$ points with one ball, and a batsman should get at least $$$n$$$ points in total.

Yugandhar, as a captain, decided to send you as a batsman. So please tell him minimum and maximum balls required for you to chase the target.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). The description of the test cases follows.

The first line of each testcase contains a single integer $$$n$$$ ($$$1 \le n \le 10^3$$$) — total runs required to chase.

Output

For each test case, print $$$2$$$ space separated integers — minimum and maximum balls required to chase the target respectively.

Example
Input
4
10
20
30
40
Output
2 3
4 5
5 8
7 10
Note

In the $$$1^{st}$$$ testcase, the batsman can hit $$$10$$$ runs in minimum of $$$2$$$ balls and maximum of $$$3$$$ balls.

One of the possible sequence to hit $$$10$$$ runs in $$$2$$$ balls is $$$4$$$,$$$6$$$.

One of the possible sequence to hit $$$10$$$ runs in $$$3$$$ balls is $$$4$$$,$$$4$$$,$$$6$$$.

B. Good String
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Yugandhar bought a binary string$$$^\dagger$$$ $$$S$$$ of length $$$n$$$ for Diya's birthday gift. But later he knows that Diya likes only binary strings if it doesn't contain 01 and 10 as substrings, and termed it as Good String.

To make a string good, there are two possible operations available for Yugandhar.

  1. Choose a character and flip it(change 0 to 1 and vice-versa).
  2. Choose characters from two different positions in the string, and replace these characters with their XOR value.

Operation 1 costs $$$a$$$ coins and Operation 2 costs $$$b$$$ coins. Yugandhar doesn't have too much money. So he wants to convert the given string to Good String using minimum number of coins.

Can you help Yugandhar with minimum number of coins needed to convert the string Good?

$$$^\dagger$$$ A binary string is a string which only contains $$$0's$$$ and $$$1's$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10$$$). The description of the test cases follows.

The first line of each testcase contains three integers $$$n,a,b$$$ ($$$1 \le n,a,b \le 10^3$$$), the length of binary string, number of coins required for operation 1, number of coins required for operation 2 respectively.

The second line of each testcase contains a binary string $$$S$$$ of length $$$n$$$.

Output

For each test case, print a single integer — the minimum number of coins needed to convert the given string to Good String

Example
Input
4
2 1 1
10
3 2 1
110
4 4 2
1010
6 5 6
110011
Output
1
1
2
10
Note

In the $$$1^{st}$$$ testcase, It is optimal to convert the first character of the given string using Operation 1. So the total coins spent are $$$1$$$.

C. Good Permutation
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Pavan Kalyan likes permutations$$$^\dagger$$$. But Yugandhar likes Good permutations. So he asked Pavan Kalyan to give him a Good permutation of length $$$n$$$.

A permutation $$$P$$$ of length $$$n$$$ $$$(p_1,p_2,p_3.....,p_n)$$$ is Good if $$$F(P)$$$ has a minimum value.

Where, $$$$$$F(P)=\sum_{i = 1}^n⌊\frac{p_i}{i}⌋$$$$$$

Where, ⌊$$$x$$$⌋ denotes rounding down of $$$x$$$.

$$$^\dagger$$$ A permutation is an array of length $$$n$$$, where each number from $$$1$$$ to $$$n$$$ appears exactly once

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). The description of the test cases follows.

The first line of each testcase contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$), the length of the Good permutation.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each test case, print a Good permutation of length $$$n$$$.

If there are several answers, output any.

Example
Input
4
1
2
3
4
Output
1
1 2
1 3 2
1 4 2 3

D. Good String Again
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem

Yugandhar bought a binary string$$$^\dagger$$$ $$$S$$$ of length $$$n$$$ for Diya's birthday gift. So, he wants Diya to guess any positions of substrings $$$01$$$ and $$$10$$$ respectively. For that, she can ask the following type of query.

  • $$$?$$$ $$$T$$$, where $$$T$$$ is a binary string of length $$$n$$$. In return, Yugandhar will tell the number of $$$0's$$$ in $$$(S \oplus T)$$$, where $$$\oplus$$$ denotes the Bitwise XOR.

Diya got so confused with this task, so please help her to find the required answer within $$$40$$$ queries.

$$$^\dagger$$$ A binary string is a string which only contains $$$0's$$$ and $$$1's$$$.

Input

The first line contains an integer $$$t(1 \le t \le 10^5)$$$, denoting the number of test cases.

For each test case, the only line contains a single integer $$$n$$$ $$$(1 \le n \le 2 \cdot 10^{5})$$$ — the length of the hidden binary string.

It is guaranteed that the sum of $$$n$$$ over all testcases doesn't exceed $$$2 \cdot 10^{5}$$$.

Interaction

For each test case, the interaction starts with reading $$$n$$$.

Then you are allowed to ask atmost $$$40$$$ queries of the following way

"$$$?$$$ $$$T$$$" ($$$T$$$ is a binary string of length $$$n$$$).

After each one, you should read an integer $$$x$$$ which is equal to the number of $$$0's$$$ in $$$(S \oplus T)$$$, where $$$\oplus$$$ denotes the Bitwise XOR.

When you have found the positions of substrings $$$01$$$ and $$$10$$$ respectively, print a single line "$$$!$$$ $$$i$$$ $$$j$$$" (without quotes), representing $$${S_i}{S_{i+1}}$$$ is equal to $$$01$$$ and $$${S_j}{S_{j+1}}$$$ is equal to $$$10$$$. If there is no $$$01$$$ substring then $$$i = -1$$$, similarly, if there is no $$$10$$$ substring then $$$j = -1$$$. Outputting the answer does not count as a query.

The interactor for this problem is not adaptive: binary string $$$S$$$ is fixed before any queries are made.

After printing a query, do not forget to output the 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
1
4

3

1

1
Output
? 0101

? 1010

? 0110

! 3 -1
Note

In the $$$1^{st}$$$ testcase, the hidden string is $$$0001$$$.

The value of $$$0001$$$ $$$\oplus$$$ $$$0101$$$ is $$$0100$$$ which contains $$$3$$$ $$$0's$$$.

E. Good Game
time limit per test
6 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Yugandhar went to a sports club to play some indoor games. There, he saw a pinball machine which was differently designed.

The pinball machine is a rooted tree consisting of $$$n$$$ nodes rooted at $$$1$$$, which was inverted(i.e.,the root will be the bottom of the tree). So, if we put a ball at some place, it will reach downwards due to gravity until there is a possible movement (i.e., until there is no ball in the next node).

You will be given $$$m$$$ balls initial positions and put them sequentially on the pinball machine.

Tell the final positions of $$$m$$$ balls on the pinball machine. If there is a ball already in the mentioned position, tell $$$-1$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^{5}$$$). The description of the test cases follows.

The first line of each testcase contains two integers $$$n,m$$$ $$$(1 \le n,m \le 10^{6})$$$ — the number of nodes in the pinball machine and the number of balls.

The next $$$n-1$$$ lines contain two integers $$$u,v$$$ $$$(1 \le u,v \le n, u≠v)$$$ — there is an edge connecting $$$u$$$ and $$$v$$$.

The next line contains $$$m$$$ space separated integers $$$x_i$$$ $$$(1 \le x_i \le n, 1 \le i \le m)$$$ — the initial positions of $$$m$$$ balls.

It is guaranteed that the sum of $$$n$$$ and $$$m$$$ over all testcases doesn't exceed $$$2 \cdot 10^{6}$$$.

Output

For each testcase, print $$$m$$$ space separated integers — the final positions of $$$m$$$ balls.

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

In the $$$2^{nd}$$$ testcase,

The movement of the $$$1^{st}$$$ ball is $$$4$$$ $$$\rightarrow$$$ $$$3$$$ $$$\rightarrow$$$ $$$1$$$, hence the final position is $$$1$$$.

The movement of the $$$2^{st}$$$ ball is $$$4$$$ $$$\rightarrow$$$ $$$3$$$, hence the final position is $$$3$$$.

F. Good Tree Queries
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Yugandhar gave a weighted tree initially containing $$$n$$$ nodes to Naveen and Pavan Kalyan in 2023. Almost a year has completed, so he came up with $$$3$$$ types of queries to test their knowledge on trees.

Before asking about queries, Yugandhar came up with an infinite integer array $$$A$$$ defined as $$$(A_0 = 1, A_{n} = A_{n-1}+4)$$$ and an infinite binary array $$$B$$$ defined as $$$(B_0 = 0, B_{2n} = B_{n}, B_{2n+1} = 1-B_{n})$$$. And also he gave one empty array to Naveen and one empty array to Pavan Kalyan and called them as Naveen's array and Pavan kalyan's array respectively.

Later he splits each element of $$$A_i (i \ge 0)$$$ to Naveen's array and Pavan Kalyan's array in the following way:

  1. If $$$B_i=0$$$, then he will append $$$⌊\frac{A_i}{2}⌋$$$ to Naveen's array and $$$⌊\frac{A_i}{2}⌋+1$$$ to Pavan Kalyan's array.
  2. If $$$B_i=1$$$, then he will append $$$⌊\frac{A_i}{2}⌋$$$ to Pavan Kalyan's array and $$$⌊\frac{A_i}{2}⌋+1$$$ to Naveen's array.

After splitting, he will ask the following type of queries to both:

  1. 1 x y w — He asked Naveen and Pavan Kalyan to add an edge between $$$x$$$ and $$$y$$$ with weight $$$w$$$ (note that after this query it is guaranteed that the graph is a tree).One of the $$$x$$$ and $$$y$$$ is already present in the tree and another is the new node, i.e., after this operation the size of the given tree will increase by $$$1$$$.
  2. 2 0 — He asked Naveen to find the number of simple paths whose bitwise XOR of their edges has to be in his array (note that the path between $$$(x,y)$$$ is different from $$$(y,x)$$$ ).
  3. 2 1 — He asked Pavan Kalyan to find the number of simple paths whose bitwise XOR of their edges has to be in his array (note that the path between $$$(x,y)$$$ is different from $$$(y,x)$$$ ).

Note that the given tree is guaranteed that there is atmost $$$1$$$ edge between two nodes.

Unfortunately, both Naveen and Pavan Kalyan didn't learn much about trees, so please help them by telling answers to the $$$2^{nd}$$$ and $$$3^{rd}$$$ type queries.

Input

The first line of each test contains two integers $$$n,q$$$ $$$(1 \le n,q \le 10^6)$$$ — initial number of nodes in the tree and number of queries.

The next $$$n-1$$$ lines contain three integers $$$x,y,w$$$ $$$(1 \le x,y \le n, x≠y, 1 \le w \le 10^9)$$$ — there is an edge between $$$x$$$ and $$$y$$$ with weight $$$w$$$.

The following $$$q$$$ lines can fall into three cases:

  • The first type of query: The $$$i^{th}$$$ line contains — 1 x y w $$$(1 \le w \le 10^9)$$$ Ensure that one node is an unseen node and is the smallest numbered.
  • The second type of query: The $$$i^{th}$$$ line contains — 2 0
  • The third type of query: The $$$i^{th}$$$ line contains — 2 1

Queries description was mentioned in the problem statement.

Output

For each test, print the required answer for the $$$2^{nd}$$$ and $$$3^{rd}$$$ type queries respectively.

Example
Input
5 5
1 2 2
1 5 2
2 3 2
2 4 2
2 0
2 1
1 5 6 2
2 0
2 1
Output
8
12
14
16

G. Good but not Excellent
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Yugandhar, the owner of Algorithm shop, gave a directed weighted tree containing $$$n$$$ nodes and $$$m$$$ pairs of integers in the form of {$$$x$$$,$$$y$$$} to Vardhan, who is a daily customer and frequents this shop, and asked him to run the following algorithm:

  1. Do the following for every pair of nodes $$$u$$$,$$$v$$$ $$$(1 \le u,v \le n)$$$:
    • if there is a directed edge from $$$u$$$ to $$$v$$$ and there is no directed edge from $$$v$$$ to $$$u$$$, then add a directed edge from $$$v$$$ to $$$u$$$.
  2. Change all edge weights of the tree to $$$1$$$.
  3. Create a variable $$$ans$$$=0.
  4. Do the following for every pair from $$$1$$$ to $$$m$$$ in order:
    • Let Operation 1 be initializing the variable $$$sum1$$$ and $$$sum1$$$ be the sum of the weights of edges on the shortest path from $$$x$$$ to $$$y$$$ on the tree.
    • Let Operation 2 be initializing the variable $$$sum2$$$ and $$$sum2$$$ be the sum of the weights of edges on the shortest path from $$$y$$$ to $$$x$$$ on the tree.
    • If you choose Operation 1 as your good operation for this particular pair, then do $$$ans$$$+=$$$sum1$$$ and change the weights of all edges on the shortest path from $$$x$$$ to $$$y$$$ on the tree to $$$0$$$. Otherwise do $$$ans$$$+=$$$sum2$$$ and change the weights of all edges on the shortest path from $$$y$$$ to $$$x$$$ on the tree to $$$0$$$.

After successfully running this algorithm, Yugandhar asked Vardhan to find the maximum value of variable $$$ans$$$ if he chooses Operation 1 or Operation 2 optimally for every pair from $$$1$$$ to $$$m$$$.

Vardhan got so confused, so please help him to find the required solution.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^{4}$$$). The description of the test cases follows.

The first line of each testcase contains two integers $$$n,m$$$ $$$(1 \le n,m \le 5000)$$$ — the number of nodes in the given tree and the number of pairs of integers.

The next $$$n-1$$$ lines contain two integers $$$u,v$$$ $$$(1 \le u,v \le n, u≠v)$$$ — there is a directed edge from $$$u$$$ to $$$v$$$.

The next line contains $$$m$$$ space separated pairs of integers {$$$x_i$$$,$$$y_i$$$} $$$(1 \le x_i,y_i \le n, x_i≠y_i, 1 \le i \le m)$$$.

It is guaranteed that the sum of $$$n$$$ and $$$m$$$ over all testcases doesn't exceed $$$10^{4}$$$.

Output

For each test case, print two lines:

  1. Maximum value of the variable $$$ans$$$.
  2. An array of $$$m$$$ elements, where every element is either $$$1$$$ if you choose Operation 1 as the good operation for that particular pair or $$$2$$$ if you choose Operation 2 as the good operation for that particular pair. If there are multiple arrays which gives the maximum value of $$$ans$$$, then output any.
Example
Input
3
3 1
1 2
1 3
1 2
3 2
1 2
1 3
1 2
1 3
5 3
1 2
4 3
3 1
5 3
2 3
4 5
1 5
Output
1
1
2
1 2
6
1 1 2
Note

In the $$$3^{rd}$$$ testcase, all possible ways to choose operations are:

  1. If you choose operations $$$[1,1,1]$$$ then $$$ans=4$$$.
  2. If you choose operations $$$[1,1,2]$$$ then $$$ans=6$$$.
  3. If you choose operations $$$[1,2,1]$$$ then $$$ans=5$$$.
  4. If you choose operations $$$[2,1,1]$$$ then $$$ans=5$$$.
  5. If you choose operations $$$[2,1,2]$$$ then $$$ans=5$$$.
  6. If you choose operations $$$[2,2,1]$$$ then $$$ans=6$$$.
  7. If you choose operations $$$[1,2,2]$$$ then $$$ans=5$$$.
  8. If you choose operations $$$[2,2,2]$$$ then $$$ans=4$$$.

Hence, the maximum value of $$$ans$$$ is $$$6$$$.