2023 ICPC HIAST Collegiate Programming Contest
A. Gym Plates
time limit per test
1 second
memory limit per test
256 MB
input
standard input
output
standard output

Yaman and Omar are playing in a gym, and they want to prepare themselves for the tournament.

The gym in which they exercise has $$$n$$$ barbell plates numbered from $$$1$$$ to $$$n$$$, and the weight of the $$$i$$$-th plate is $$$w_i$$$.

Yaman noticed that he can lift any number of barbell plates if the following condition is held:

  • For any digit from $$$0$$$ to $$$9$$$, the digit must not occur in the weights more than twice.

For example: Yaman can lift plates with weights $$$[11, 23, 2]$$$, but he can't lift $$$[10, 999]$$$ or $$$[99, 9, 10]$$$ because the digit $$$9$$$ repeated $$$3$$$ times.

Now Omar is wondering what is the maximum weight that Yaman can lift, help him to find it out.

Input

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

The first line of each test case contains one integer $$$n$$$ $$$( 1 \le n \le 100 )$$$ — the number of barbell plates in the gym

The second line contains $$$n$$$ integers $$$w_1, w_2, .., w_n$$$ $$$( 1 \le w_i \le 10^{16} )$$$ — the wights of the barbell plates

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$100$$$

Output

For each test case, output the maximum weight that Yaman can lift.

Example
Input
3
3
11 23 2
1
222
3
97 98 99
Output
36
0
195

B. Convarge To 1
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Zaher has an array $$$a$$$ of $$$n$$$ integers, one day Zaher decided to make a challenge to the students in his math class.

At first, Zaher repeats the following operation on the array in front of his students until all the elements in the array are equal to one.

Each operation has two steps:

  1. Choose the maximum number from the array $$$a$$$, let it be $$$a_i$$$ (if there are multiple numbers equal to the maximum, choose the number with the lowest index).
  2. Divide $$$a_i$$$ by the largest prime number that divides it.

Then the challenge can be represented by $$$q$$$ questions. In each question, Zaher will give his students two numbers, $$$l$$$ and $$$r$$$, and the students should know the first time that all elements of the subarray $$$[a_l, a_{l+1}, .., a_r]$$$ become equal to $$$1$$$.

The students in the math class are not able to solve all of Zaher's questions, help them to find the answers.

Input

The first line contains one integer $$$n$$$ $$$( 1 \le n, q \le 2 \cdot 10^{6} )$$$ — the length of the array $$$a$$$ and the number of questions respectively.

The second line contains $$$n$$$ integers $$$a_1, a_2, .., a_n$$$ $$$( 1 \le a_i \le 2 \cdot 10^{6} )$$$ — Zaher's array.

The next $$$q$$$ lines contain two integers $$$l_i, r_i$$$ $$$( 1 \le l_i \le r_i\le n )$$$ — the numbers that Zaher gave to his students in the $$$i$$$-th question.

Output

Output $$$q$$$ lines, the $$$i$$$-th line should contain the first time that all elements of the array $$$[a_l, a_{l+1}, .., a_r]$$$ equal to $$$1$$$.

Examples
Input
3 2
4 6 5
1 3
1 2
Output
5
5
Input
6 6
12 22 5 7 25 8
1 3
1 6
2 5
2 6
3 5
4 6
Output
11
12
11
12
7
12
Note

Description of the first testcase:

Applying Zaher's operations done as follows:

Firstly we choose $$$6$$$ since it's the largest element in the array and divide it by its largest prime factor which is $$$3$$$, and get the array: $$$[4, 5, 2]$$$.

Secondly, we choose the $$$5$$$ since it's the largest number and divide it by its largest factor and get the array $$$[4, 1, 2]$$$.

Third, we choose $$$4$$$ and divide it by $$$2$$$ and get the array $$$[2, 1, 2]$$$.

Fourth we choose $$$2$$$ (first one) and divide it by $$$2$$$ and get the array $$$[1, 1, 2]$$$.

Fifth we choose $$$2$$$ and divide it by $$$2$$$ and get the array $$$[1, 1, 1]$$$.

In the first query: the array becomes all equal to $$$1$$$ after $$$5$$$ operations.

In the second query: the subarray $$$[a_1, a_2]$$$ become all equal to $$$2$$$ after $$$4$$$ operations.

C. Tree Permutation
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Saeed and Ahmad are planning to go out on a trip to Treeland, The Treeland is a city that has $$$n$$$ tourist places, the roads between these tourist places are specific which means you can move from a tourist place to another if and only if there is a road between them, there are $$$n - 1$$$ road between all tourist places in total and it's guaranteed that you can go from any tourist place to any other tourist place throughout a finite sequence of roads, that is the $$$n$$$ tourist places form a connected tree.

Ahmad and Saeed want to visit all $$$n$$$ tourist places in the following way:

First of all, they will specify the order that they will visit tourist places, that is; they will give every tourist place a unique number between $$$1$$$ and $$$n$$$.

Secondly, they will start with the tourist place with the number $$$1$$$, go to the tourist place with the number $$$2$$$, then go to the tourist place with the number $$$3$$$, and so on till they visit the tourist place with the number $$$n$$$.

Ahmad is lazy, he will get tired after making a few steps, so Saeed wants to provide him with the number of steps of the trip before they go out, The problem is that they didn't plan the order that they will visit tourist places so that Saeed decided to calculate the expected number of steps of the trip over all possible orders.

The number of steps between two tourist places is the number of roads in the shortest path between them.

Input

The first line in the input contains one integer $$$T$$$ the number of test cases.

The first line of each test case contains one integer $$$n$$$ $$$(1 \le n \le 2 \cdot 10^5)$$$, the number of tourist places in Treeland.

The following $$$n - 1$$$ lines of each test case have two integers $$$u$$$ and $$$v$$$ means that there is a road between $$$u-th$$$ tourist place and $$$v-th$$$ tourist place.

Output

For every test case, you have to print one float number, The expected number of steps of the trip.

The absolute error between your answer and the judge's answer should not exceed $$$10^{-6}$$$.

Examples
Input
1
5
1 2
1 3
3 4
3 5
Output
7.2000000
Input
1
10
1 10
10 2
4 3
9 1
7 6
3 1
6 3
4 5
8 3
Output
23.4000000

D. To Be Named
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a string $$$s$$$ of length $$$n$$$ that has digits from $$$0$$$ to $$$9$$$, A TBN is defined as a sorted subsequence of the a string.

The cost of building TBN in a string $$$s$$$ is the sum of $$${s_i}^a$$$ Where $$$s_i$$$ is used in the subsequence of the TBN.

In addition to the string $$$s$$$ you are given an integer $$$a$$$ and $$$q$$$ queries, In each query you are given two integers L and R, and you have to print the total cost of building every possible unique TBN of the string $$$s$$$ with the length between $$$l$$$ and $$$r$$$ (inclusive).

The length of the TBN is the number of digits used in it for example the TBN $$$1223$$$ has a length of $$$4$$$.

Two TBNs ($$$s$$$ and $$$t$$$) are different if at least one of the following conditions is met:

  • The length of $$$s$$$ doesn't equal the length of $$$t$$$.
  • The length of $$$s$$$ equals the length of $$$t$$$ and there is at least one index $$$i$$$ such that $$$s_i \neq t_i$$$.

Since the answer could be arbitrarily large, You have to print the answer modulo $$$m$$$, $$$(m \le 10^9+7)$$$.

Please note that $$$m$$$ isn't necessarily prime.

Input

The first line of input contains one integer $$$T$$$ $$$(1 \le T \le 1000$$$), the number of test cases.

The first line of each testcase contains three integers $$$n$$$, $$$m$$$ and $$$a$$$ $$$(1 \le n \le 4 \cdot 10^4 $$$) $$$(1 \le m \le 10^9 + 7 $$$) $$$(1 \le a \le 10^5$$$).

The second line of each testcase contains the string s. $$$(0 \le s_i \le 9)$$$ for every $$$(1 \le i \le n)$$$

The third line of each test case contains one integer q, The number of queries $$$(1 \le q \le 10^5)$$$.

Each of the following $$$Q$$$ lines contains two integers $$$l$$$ and $$$r$$$ $$$(1 \le l \le r \le n)$$$.

It is guaranteed that the sum of $$$n$$$ and $$$q$$$ over all test cases doesn't exceed $$$4 \cdot 10^4$$$ and $$$10^5$$$ respectively.

Output

For each query, you have to print one integer, The answer for the query modulo $$$m$$$.

Example
Input
2
2 1003 2
22
2
1 1
1 2
4 1000000007 1
1221
2
1 2
2 3
Output
4
12
12
18
Note

In the second test, the TBNs of length 1 and 2 are {1}, {2}, {11}, {12}, {22} with cost (1 + 2 + 2 + 3 + 4) = 12

E. Sad Teacher
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Muhammed is a teacher, but being a teacher isn't that easy, especially when teaching more than one subject. Muhammed is teaching Physics and Chemistry in some schools and the most difficult part of his work is calculating the total mark of a student in both subjects, That's why he is asking you to help him with such a near-impossible task. Muhammed will give you the Physics mark and the Chemistry mark of some student and you have to calculate the total mark of that student, that is, the sum of both marks, how hard!!

Input

The input contains two integer value $$$a, b$$$, $$$(1 \le a, b \le 10^{18})$$$.

Output

Must be one integer, the answer of the problem.

Examples
Input
70 80
Output
150
Input
4 5
Output
9

F. New Board Game
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Master GH-Splinter got a new board game where the board is a square grid of size $$$n$$$ and each cell of the grid contains an integer between $$$1$$$ and $$$n$$$. Each integer from $$$1$$$ to $$$n$$$ is repeated exactly $$$n$$$ times in the grid.

The grid is called $$$\it{beautiful}$$$ if both of the following conditions are met:

  1. Each row of the grid is a permutation of length $$$n$$$.
  2. Each column of the grid is a permutation of length $$$n$$$.

The game is played with one player, and he will try to make the grid $$$\it{beautiful}$$$ by making finite number of operations. In each operation, he will perform one of the following:

  • Shift all the rows one step to the right.
  • Shift all the columns one step down.

A permutation of length $$$n$$$ is a sequence of integers from $$$1$$$ to $$$n$$$ containing each number exactly once. For example, $$$[1]$$$, $$$[4,3,5,1,2]$$$, $$$[3,2,1]$$$ are permutations, and $$$[1,1]$$$, $$$[4,3,1]$$$, $$$[2,3,4$$$] are not.

Master GH-Splinter thinks this game is useful for the ninja's mind, so he wants you to train his ninja turtles on solving this problem. You're given the initial board and you should tell the ninja turtles if the board is $$$\it{beautiful}$$$ after applying $$$0$$$ or more operations.

Input

The first line of the input has one integer $$$n$$$ $$$(1 \le n \le 1000)$$$ — the size of the game board.

Each of the next $$$n$$$ lines contains $$$n$$$ integers which represent the rows of the game board $$$(1 \le a_{i,j} \le n)$$$ — $$$a_{i,j}$$$ is the $$$j$$$-th element in the $$$i$$$-th row.

Output

You have to print "YES" (without quotes) if you can make the grid $$$\it{beautiful}$$$, otherwise you have to print "NO" (without quotes).

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

Examples
Input
3
1 2 3
3 1 2
2 3 1
Output
YES
Input
4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
Output
NO

G. Don't Make It 2
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Ismail hates the number $$$2$$$ due to hard problems related to that number, but his friend Ahmed always gives him numbers containing the number $$$2$$$ to make him angry. But one time, Ismail was very angry. Ahmad thought of a way to calm him down, so he gave him a number $$$N$$$ and asked him to find the largest number $$$X$$$ that satisfies the following conditions:

  • $$$X$$$ must be strictly smaller than $$$N$$$
  • $$$X$$$ must be indivisible by $$$2$$$
  • If you divide $$$X$$$ by 2 repeatedly (until it becomes 1), $$$X$$$ mustn't become divisible by $$$2$$$ after any division step

For example, $$$9$$$ is invalid $$$X$$$ because if we divide it by $$$2$$$ it becomes $$$4$$$ and $$$4$$$ is a multiple of $$$2$$$. $$$3$$$ and $$$1$$$ are examples for valid $$$X$$$

Input

The first line contains the number of test cases $$$T$$$ $$$( 1 \le T \le 2 \cdot 10^{5} )$$$. Each test case contains a single line with one integer $$$N$$$ $$$( 2 \le N \le 10^{18} )$$$ — the number that Ahmad gave to Ismail.

Output

For each test case, output single integer $$$X$$$ that satisfies problem conditions.

Example
Input
2
5
6
Output
3
3

H. Yaser In Baradah
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There is a well-known river named Baradah. The river is divided into $$$n$$$ sections and at the end of each section there is a fish net. Initially, section $$$i$$$ contains $$$a_{i}$$$ fish and its fish net is closed.

Yaser wants to research the river, The research can be represented by doing $$$Q$$$ operations.

In each operation Yaser chooses a section $$$i$$$ that he has not chosen before and opens its fish net, which causes moving all fish that exist within section $$$i$$$, The fish move forward and stop at the first section whose its fish net is closed. Yaser will not close the fish net after the operation.

After applying each operation, Yaser wants to know the maximum number of fish over all sections.

Input

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

The first line of each test case contains one integer $$$n$$$ $$$( 2 \le n \le 10^{5} )$$$ — the number of sections of Baradah River.

The second line contains $$$n$$$ integers $$$a_1, a_2, .., a_n$$$ $$$( 1 \le a_i \le 10^{9} )$$$ — the number of fish in the $$$i$$$ section.

The third line contains one integer $$$Q$$$ $$$( 1 \le Q \lt n )$$$ — the number of operations

The next $$$Q$$$ lines contain one integer $$$s_i$$$ $$$( 1 \le s_i \le n )$$$ — the section that will be opened in the $$$i$$$-th operation.

It is guaranteed that the sum of $$$n$$$ and the sum of $$$Q$$$ over all test cases do not exceed $$$10^{5}$$$

It is guaranteed that the last section won't be opened during Yaser's operations.

Output

For each test case, Output $$$Q+1$$$ lines, the first line should contain the maximum number of fish over all sections before opening any fish net. Then $$$Q$$$ lines, the $$$i$$$-th line should contain the maximum number of fish over all sections after opening the fish net of the $$$s_i$$$-th section.

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

I. Ajam's Password
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Ajam loves to deal in digital currencies, so he has a digital wallet in which he stores his digital money.

Unfortunately, Ajam forgot his wallet's password, which contained a large amount of money

Ajam only remembers these things about his password:

  • It consists of zeros and ones only.
  • It contains $$$n_0$$$ number of zeros and $$$n_1$$$ number of ones.
  • It shall not contain less than $$$l_0$$$ consecutive zero and no more than $$$r_0$$$ consecutive zero.
  • It shall not contain less than $$$l_1$$$ consecutive one and no more than $$$r_1$$$ consecutive one.

Ajam wants to hire Abdul Rahman to recover his password, can you help Abdul Rahman to find out how many passwords meet the conditions mentioned by Ajam?

Since the number of passwords is very large, print it modulo $$$10^{9} + 7$$$.

Input

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

The first line of each test case contains two integers $$$n_0, n_1$$$ $$$( 100 \le n_0,n_1 \le 10^{5} )$$$ — The number of zeros and the number of ones in the password respectively.

The second line of each test case contains two integers $$$l_0, r_0$$$ $$$( 50 \le l_0 \le r_0 \le n_0 )$$$ — the minimum and maximum number of consecutive zeros in the password respectively.

The third line of each test case contains two integers $$$l_1, r_1$$$ $$$( 50 \le l_1 \le r_1 \le n_1 )$$$ — the minimum and maximum number of consecutive ones in the password respectively.

It is guaranteed that the sum of $$$n_0$$$ and $$$n_1$$$ over all test cases does not exceed $$$2 \cdot 10^{5}$$$

Output

For each test case, output the number of passwords that meet problem conditions modulo $$$10^{9} + 7$$$.

Examples
Input
1
100 100
50 83
50 50
Output
2
Input
1
1000 1000
50 100
50 100
Output
234019247

J. Completely Balanced
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Omar is an AI engineer who is studying statistics. Recently, he knew about $$$mean$$$ and $$$median$$$.

His curiosity makes him wonder, if you have an array $$$a$$$ of $$$n$$$ integers, can you add just one integer $$$\bf{X}$$$ such that the $$$mean$$$ and the $$$median$$$ of the updated array would be equal?

Where the $$$mean$$$ of an array $$$a$$$ equals: $$$\frac{\sum_{i = 1}^n a_i}{n}$$$. The $$$mean$$$ of the array $$$[2, 6, 1, 2, 4]$$$ is $$$\frac{2+6+1+2+4}{5} = 3$$$.

A $$$median$$$ of an array of $$$n$$$ numbers is the element which occupies position number $$$\lfloor \frac{n+1}{2} \rfloor$$$ after we sort the elements in the non-decreasing order (the array elements are numbered starting from 1). The $$$median$$$ of the array $$$[2, 6, 1, 2, 3]$$$ is $$$2$$$, and the $$$median$$$ of the array $$$[0, 96, 17, 23]$$$ is 17.

We define an expression $$$\lfloor \frac{a}{b} \rfloor$$$ as the integer part of dividing number $$$a$$$ by number $$$b$$$.

It's guaranteed that The answer is always exists under the given constraints

Input

The first line contains $$$1 \le T \le 1000$$$ number of test cases.

For each test case, you will be given an integer $$$1 \le n \le 10^6$$$ followed by $$$n$$$ integers $$$-10^9 \le a_i \le 10^9$$$.

It is guaranteed that the sum of n over all test cases doesn't exceed $$$10^6$$$.

Output

For each test case, you have to print one integer $$$\bf{X}$$$ that solves the problem.

If there are multiple solutions print the minimum one.

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

In the first test case, the updated array will be [1, 2, 3], $$$mean$$$ = $$$median$$$ = 2.

In the second test case, the updated array will be [-4, 1, 2, 3, 4, 6], $$$mean$$$ = $$$median$$$ = 2.

K. Sam-Oh, the funny coach
time limit per test
2 s
memory limit per test
256 megabytes
input
standard input
output
standard output

Sam-Oh is teaching a course for his university contestants on how to be funny (instead of teaching them useful algorithms for SCPC). The course consists of $$$m$$$ parts, each part contains 26 jokes where a joke is represented as a small Latin English letter. But Sam-Oh is depressed as the contestants aren't funny at all! they only learn one joke of each part out of the 26 jokes!!

So, after the course ends, each contestant is learned $$$m$$$ jokes. In other words, the learned jokes of each person can be represented as a string of length $$$m$$$ consisting of small Latin English letters. Not only this! Sam-Oh found out that these strings are sorted in non-decreasing order! To overcome his depression, Sam-Oh will make the funny dual event. In this event, he will choose $$$Q$$$ pairs of contestants and test their fun compatibility by finding the number of shared jokes at each index $$$i$$$ of the two strings. More formally, let $$$s$$$ be the string of jokes of the first contestant and $$$t$$$ the string of the other one, and count the number of indices $$$i$$$ such that: $$$s_i = t_i$$$

Sam-Oh is busy telling jokes and making other coaches happy (he thinks so) so he will give you the pairs of contestants and asks you to find the results.

Note: Every string is sorted, The array of strings isn't sorted necessarily.

Input

The first line contains two integers $$$n, m$$$ $$$( 2 \le n \cdot m \le 5 \cdot 10^{5} )$$$ — the number of contestants and the number of jokes respectively.

The next $$$n$$$ lines contain string $$$s_i$$$ $$$( | s_i | = m )$$$ — the learned jokes by the $$$i$$$-th contestant, sorted in non-decreasing order.

The third line contains one integer $$$Q$$$ $$$( 1 \le Q \le 10^{6} )$$$ — the number of tests Sam-Oh will do.

The next $$$Q$$$ lines contains two integers $$$p_{1_i}, p_{2_i}$$$ $$$( 1 \le p_{1_i}, p_{2_i}\le n)$$$ — The pair of the $$$i$$$-th test.

It's guaranteed that there are at least two contestants in the university.

Output

Output $$$Q$$$ lines, the $$$i$$$-th line should contain the $$$i$$$-th test result.

Example
Input
3 4
aaab
aabb
abbc
5
1 1
2 2
1 2
2 3
1 3
Output
4
4
3
2
1

L. Trip Discount
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

A famous travel and tourism company succeed to win a new discount coupon, The coupon is only allowed to be used in the Treeland. In case you haven't heard about Treeland yet, Treeland is a city that has $$$n$$$ tourist places, the roads between these tourist places are specific which means you can move from a tourist place to another if and only if there is a road between them, Every road has a cost $$$w_i$$$ and you have to pay $$$w_i$$$ $$$sp$$$ for traveling using the $$$i-th$$$ road, there are $$$n - 1$$$ road between all tourist places in total and it's guaranteed that you can go from any tourist place to any other tourist place throughout a finite sequence of roads, that is, the $$$n$$$ tourist places form a weighted connected tree.

The discount coupon can be used as follows: The travel and tourism company can choose a set $$$S$$$ of $$$k$$$ tourist places, and for every road $$$i$$$ that lies on the shortest path between two nodes $$$u$$$ and $$$v$$$ such that $$$u \in S$$$ and $$$v \in S$$$, the company can travel using this road for free for one month.

The company has a schedule of $$$m$$$ trips for the next month and it wants to use the coupon to achieve the biggest discount, asking you to choose the set $$$S$$$ optimally for them.

The trip starts at some node $$$u$$$ and finishes at some node $$$v$$$ and it passes on every other node that lies on the shortest path between nodes $$$u$$$ and $$$v$$$, and the cost of the trip is the total cost of roads which the trip uses them.

The $$$m$$$ trips run individually which means the second trip starts when the first trip finishes, the third trip starts when the second trip finishes, and so on.

You have to calculate the total cost of the $$$m$$$ trips if we have chosen the set $$$S$$$ optimally.

Input

The first line in the input contains one integer $$$T$$$ the number of testcases.

The first line of each test case contains three integers $$$n$$$, $$$k$$$, $$$m$$$ $$$(1 \le n \le 10^{4})$$$ $$$(1 \le k \le min(n,1000))$$$ $$$(1 \le m \le 10^{5})$$$, the number of tourist places in Treeland, the size of the set $$$S$$$, and the number of the trips of the next month.

The following $$$n - 1$$$ lines of each test case have three integers $$$u$$$, $$$v$$$, and $$$w$$$ means that there is a road between $$$u-th$$$ tourist place and $$$v-th$$$ tourist place with a cost of $$$w$$$ $$$(1 \le w \le 1000)$$$.

Each of the following $$$m$$$ lines has two integers $$$u$$$ and $$$v$$$ means that there is a trip that starts from node $$$u$$$ and finishes in node $$$v$$$.

Output

The output for each test case should contain one integer, The minimum total cost of all trips after choosing the set $$$S$$$ optimally.

Examples
Input
1
5 1 5
2 3 25
5 3 7
3 4 3
1 3 10
1 1
3 4
4 3
1 1
1 4
Output
19
Input
1
5 2 6
3 4 2
5 3 3
1 3 10
3 2 5
2 4
1 1
2 4
4 4
1 3
2 3
Output
4

M. Ahmad's Dish
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Ahmad is passionate about physics, and recently he learned something new.

He learned that to keep an object from falling off the table, the center of mass of that object must be positioned on the table, even if the rest of this object is outside the table.

Ahmad was thrilled to learn this new concept, so he went to Ismail to share this idea.

Unfortunately, Ismail loves geometry and is a quick learner and quickly understood Ahmad's new idea and gave him a good problem.

The problem involves a circular table with radius $$$R$$$ and a dish with a regular polygon shape of $$$N$$$ sides, each side of length $$$L$$$.

There are an unlimited number of dishes; The dishes can be placed anywhere on the table as long as they don't fall off the table and at least one side of them is parallel to the x-axis.

The task is to find the maximum possible area that can be covered using the dishes.

$$$ $$$

In the above example$$$R = 4, N = 4, L = 2$$$. The purple shape is the maximum area the dishes can cover.

$$$ $$$

As a good friend of Ahmad, you want to help him solve this problem.

Input

The first line contains one integer number $$$T$$$ the number of testcases ($$$1 \le T \le 10^6 $$$)

The following $$$T$$$ lines contain 3 integers $$$R, N, L$$$ ($$$1 \le R,L \le 10^3$$$ , $$$3 \le N \le 100$$$)

Output

For each test case, print a single value of the answer for the problem. Your answers must have a relative or absolute error of at most $$$10^{-6}$$$.

Examples
Input
1
4 4 2
Output
86.265482457437
Input
1
4 5 2
Output
97.147392059793

N. Ziftawi's Tree
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Yaman and Ziftawi were good friends who shared a love for nature, Ziftawi had a magnificent tree in his backyard, a connected graph with no cycles and a value assigned to each node. The tree was a symbol of their friendship, bringing them joy and tranquility.

One day, Yaman, driven by curiosity, decided to play a mischievous prank on Ziftawi. He secretly stole the entire tree, leaving behind only the root node with the number $$$1$$$ which has the value of $$$x$$$. Yaman regrets his actions and is determined to fix his mistake by restoring the tree with your help.

You will be given $$$q$$$ queries of three types:

  • $$$1$$$ $$$u$$$ $$$y$$$ $$$-$$$ Assuming the tree initially has $$$n$$$ nodes, you should add a node with the number $$$n + 1$$$ and a value of $$$y$$$ as a child of node $$$u$$$.

    For example: if the tree initially has $$$10$$$ nodes, and the children of node $$$1$$$ are $$$[2, 3, 5]$$$, when you add a new node as a child of the node $$$1$$$, its children will be: $$$[2, 3, 5, 11]$$$

  • $$$2$$$ $$$l$$$ $$$r$$$ $$$-$$$ Consider an array $$$b$$$ that represents the DFS ORDER of the current tree starting from node $$$1$$$, you need to reverse the values of the nodes appearing in the array $$$b$$$ from index $$$l$$$ to index $$$r$$$.
  • $$$3$$$ $$$u$$$ $$$-$$$ Print the value of the node $$$u$$$.

A DFS ORDER is an array $$$b$$$ that represents the ordering of the nodes in a rooted tree, constructed by recursively calling a DFS procedure starting from the root. When called on a given node $$$v$$$, the procedure does the following:

  1. Append $$$v$$$ to array $$$b$$$.
  2. Traverse the sorted list of node $$$v$$$ children and recursively calls DFS-procedure on each child, except for node $$$u$$$ if $$$v$$$ was reached directly from $$$u$$$.
Input

The first line contains two integers $$$x, q$$$ $$$(1 \le x, q \le 10^5)$$$, the value of the node number $$$1$$$, and the number of queries.

The next $$$q$$$ lines contain the queries as follows:

If the $$$i$$$-th query type is $$$1$$$ then it will be followed by two numbers $$$u$$$, $$$y$$$ $$$(1 \le u, y \le 10^5)$$$, the parent node, the value of the child node (It is guaranteed that the node $$$u$$$ has been added to the tree)

If the $$$i$$$-th query type is $$$2$$$ then it will be followed by two numbers $$$l$$$, $$$r$$$ $$$(1 \le l \le r \le 10^5)$$$, the boundaries of the range that we want to reverse its values (It is guaranteed that $$$l, r$$$ is less than or equal to the number of nodes in the current tree)

If the $$$i$$$-th query type is $$$3$$$ then it will be followed by one number $$$u$$$ $$$(1 \le u \le 10^5)$$$, the number of the node that you have to print its value (It is guaranteed that the node $$$u$$$ has been added to the tree)

Output

For each query of type $$$3$$$ print the value of the node $$$u$$$ in that query.

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