vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
You are given n positive integers a1, a2, ..., an.

For every ai you need to find a positive integer ki such that the decimal notation of 2ki contains the decimal notation of ai as a substring among its last min(100, length(2ki)) digits. Here length(m) is the length of the decimal notation of m.

Note that you don't have to minimize ki. The decimal notations in this problem do not contain leading zeros.

Input

The first line contains a single integer n (1 ≤ n ≤ 2 000) — the number of integers ai.

Each of the next n lines contains a positive integer ai (1 ≤ ai < 1011).

Output

Print n lines. The i-th of them should contain a positive integer ki such that the last min(100, length(2ki)) digits of 2ki contain the decimal notation of ai as a substring. Integers ki must satisfy 1 ≤ ki ≤ 1050.

It can be shown that the answer always exists under the given constraints. If there are multiple answers, print any of them.

Examples

Input

2
8
2


Output

3
1


Input

2
3
4857


Output

5
20

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Anton, a young mathematician, comes from the cold region that is northern Sweden. He likes it there, since there are a lot of trees. Lately, however, this has made him a bit sad, since he can’t see the forest because of all the trees. Therefore, he has asked you to construct a forest.

Since Anton is a mathematician, he doesn’t want just any forest – he wants a graph theoretical forest. A forest is a (possibly disconnected) graph without cycles – i.e., a union of disjoint trees.

Anton has already decided how many vertices he wants in his forest, as well as the degree of each vertex. Now, it is your task to construct a forest according to his wishes, or determine that no such forest exists.

-----Input-----
The first line of the input is a single integer $0 \le V \le 100$, the number of vertices in his forest.

The next line contains $V$ integers $d_1, d_2, \ldots , d_ V$ ($0 \le d_ i \le 100$ for all $i$). These are the degrees which Anton wants the vertices to have.

-----Output-----
The first line of output should be IMPOSSIBLE if it is impossible to construct such a forest.

Otherwise, the first line should be POSSIBLE. The next lines should then contain two integers $1 \le a, b \le V$ each, denoting an edge between vertices $a$ and $b$. Note that the vertex with number $a$ must have exactly degree $d_ a$, i.e. the ordering of the vertices is important.

-----Examples-----
Sample Input 1:
3
1 1 2
Sample Output 1:
POSSIBLE
1 3
2 3

Sample Input 2:
2
1 2
Sample Output 2:
IMPOSSIBLE

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a triangle of numbers where each number is equal to the sum of the three numbers on top of it, find the first even number in a row.  

Explanatory Note:
The vertex of the triangle (at the top) is 1.
The structure of the triangle is shown below.
Each number is equal to the sum of the numbers at the following positions:
Position X: immediately above it.
Position Y: to the immediate left of X.
Position Z: to the immediate right of X.
If there are no numbers at positions X, Y, or Z, then assume those positions are occupied by a zero (0). This can occur for positions at the edge.

Here are four rows of the triangle:

         1
      1  1  1
   1  2  3  2  1
1  3  6  7  6  3  1

Input Format and Constraints 

First line contains a number T (number of test cases).

Each of the next T lines contain a number N (the row number, assuming that the top vertex of the triangle is Row 1).

Output Format 

For each test case, display an integer that denotes the position of the first even number. 

Note: Assume that the left most number in a row is Position 1.

If there is no even number in a row, print -1.

Constraints 

1<=T<=100 

3<=N<=1000000000  

Sample Input  

2
3
4

Sample Output  

2
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Anurag is a good boy. He studies at IIT Kharagpur, where a person's capabilities are measured on two scales 
CGPA : academic performance, denoted by C
Studapa: coolness/popularity, denoted by S

There are N challenges that one can face at IIT Kharagpur. To pass a challenge i one needs to have C ≥ ReqC[i] OR S ≥ ReqS[i]. Completing a challenge does not decrease the capabilities. In fact, P[i] spare points are awarded on completion of challenge i . Spare points can be used to boost the capabilities in any manner. 

For example if Anurag wants to use 5 spare points then he can use it to increase his his C by 0 and S by 5 or, C by 1 and S by 4 or, C by 2 and S by 3, and so on. Even though spare points can be used at any time, once used, the spare points cannot be gained back.

Initially Anurag has C = 0 and S = 0. He has an image to keep and he wants to know before hand how many spare points will enable him to win how many challenges.

Constraints
1 ≤ T ≤ 20 (Number of test cases)
1 ≤ N ≤ 100 
0 ≤ ReqC[i] ≤10^9
0 ≤ ReqS[i] ≤ 10^9
0 ≤ P[i] ≤ 10^9

Input

The first line contains T, the number of test cases. Then T test cases follow.

The fist line of each test case contains N. The next line contains N integers of the array ReqC. The next line contains N integers of the array ReqS. The next line contains N integers of the array P. 

Output

Print T lines, one for each test case.
For each test case print N space separated integers. The first integer represents the minimum number of spare points needed to complete 1 challenge, the second integer represents the minimum number of spare points needed to complete 2 challenges, and so on.

SAMPLE INPUT
2
3
10 20 30
30 20 10
1 1 1
2
1 2
2 1
1 1

SAMPLE OUTPUT
10 19 28 
1 1

Explanation

In the first case:
Anurag needs atleast 10 spare points to solve even one mission. 
To solve two mission Anurag needs 19 spare points to start with. He can start out by using 10 of the spare points to increase his C. Then he can solve the first challenge and gain 1 spare point. Now after this he has 9 + 1 = 10 spare point by which he can boost C further to make it 20, which will get him the second challenge.
To solve three missions He will need an additional 9 points (a total of 28 points) so that he can boost his C further to 30.

In the second case:
He just needs 1 spare point to solve both the challenges. He can boost C by 1. Then solve the first challenge. Then use the gained spare point for further boosting the C to solve the second challenge.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Lifeguards have a very important job. They prevent people from drowning and allow millions of people every year to experience the joys of water. You are one of these lifeguards, and you take your job very seriously. If regulations were up to you, everyone would have to wear life vests when in the water, which is why you are part of the Buoyancy Activists Promoting Change. As a result of your persistent lobbying, the pool at which you are a lifeguard has decided to hire a second lifeguard. You are very happy with the increased security at your local swimming pool.

You get along quite well with the new lifeguard, but you discover you have not prepared his arrival properly; on the first day of working together you have some trouble figuring out who is supposed to watch which swimmers. This is completely unacceptable and could lead to casualties! You immediately start working on this problem: following the mantra “shared responsibility is no responsibility”, you try to divide the people in the swimming pool into two groups as follows: any swimmer is the responsibility of the lifeguard closest to this swimmer. Thus, knowing the exact positions of all swimmers, you and your coworker both find a position such that both of you are responsible for the exact same number of swimmers. Furthermore, you want at most one swimmer for whom the distance to you and your coworker is equal. This swimmer counts for both lifeguards.

As you and your coworker are amazing sprinters, you do not care for the actual distance between you and the swimmers, only that the swimmers are divided nicely into two equally sized groups.

-----Input-----
 - The first line contains an integer $2\leq n \leq 10^5$, the number of swimmers.
 - Each of the next $n$ lines contains two integers $-10^9\leq x\leq 10^9$ and $-10^9\leq y\leq 10^9$, the position of the swimmer.

-----Output-----
Print two lines, both containing integers $x$ and $y$ with $-10^{18}\leq x,y\leq 10^{18}$, the locations of you and your coworker.

If there are multiple valid solutions, you may output any one of them.

-----Examples-----
Sample Input 1:
5
0 0
0 1
1 0
0 -1
-1 0
Sample Output 1:
-3 -1
3 1

Sample Input 2:
4
2 4
6 -1
3 5
-1 -1
Sample Output 2:
3 4
3 -1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Four Segments

Time Limit: 2 seconds

Memory Limit: 64 megabytes

Problem Description:
Several months later Alex finally got his brother Bob's creation by post. And now, in his turn, Alex wants to boast about something to his brother. He thought for a while, and came to the conclusion that he has no ready creations, and decided to write a program for rectangles detection. According to his plan, the program detects if the four given segments form a rectangle of a positive area and with sides parallel to coordinate axes. As Alex does badly at school and can't write this program by himself, he asks you to help him.

Input Specification:
The input data contain four lines. Each of these lines contains four integers *x*1, *y*1, *x*2, *y*2 (<=-<=109<=≤<=*x*1,<=*y*1,<=*x*2,<=*y*2<=≤<=109) — coordinates of segment's beginning and end positions. The given segments can degenerate into points.

Output Specification:
Output the word «YES», if the given four segments form the required rectangle, otherwise output «NO».

Demo Input:
['1 1 6 1\n1 0 6 0\n6 0 6 1\n1 1 1 0\n', '0 0 0 3\n2 0 0 0\n2 2 2 0\n0 2 2 2\n']

Demo Output:
['YES\n', 'NO\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Igor the analyst fell asleep on the work and had a strange dream. In the dream his desk was crowded with computer mice, so he bought a mousetrap to catch them.

The desk can be considered as an infinite plane, then the mousetrap is a rectangle which sides are parallel to the axes, and which opposite sides are located in points (x1, y1) and (x2, y2).

Igor wants to catch all mice. Igor has analysed their behavior and discovered that each mouse is moving along a straight line with constant speed, the speed of the i-th mouse is equal to (vix, viy), that means that the x coordinate of the mouse increases by vix units per second, while the y coordinates increases by viy units. The mousetrap is open initially so that the mice are able to move freely on the desk. Igor can close the mousetrap at any moment catching all the mice that are strictly inside the mousetrap.

Igor works a lot, so he is busy in the dream as well, and he asks you to write a program that by given mousetrap's coordinates, the initial coordinates of the mice and their speeds determines the earliest time moment in which he is able to catch all the mice. Please note that Igor can close the mousetrap only once.

Input

The first line contains single integer n (1 ≤ n ≤ 100 000) — the number of computer mice on the desk.

The second line contains four integers x1, y1, x2 and y2 (0 ≤ x1 ≤ x2 ≤ 100 000), (0 ≤ y1 ≤ y2 ≤ 100 000) — the coordinates of the opposite corners of the mousetrap.

The next n lines contain the information about mice.

The i-th of these lines contains four integers rix, riy, vix and viy, (0 ≤ rix, riy ≤ 100 000,  - 100 000 ≤ vix, viy ≤ 100 000), where (rix, riy) is the initial position of the mouse, and (vix, viy) is its speed.

Output

In the only line print minimum possible non-negative number t such that if Igor closes the mousetrap at t seconds from the beginning, then all the mice are strictly inside the mousetrap. If there is no such t, print -1.

Your answer is considered correct if its absolute or relative error doesn't exceed 10 - 6. 

Formally, let your answer be a, and the jury's answer be b. Your answer is considered correct if <image>.

Examples

Input

4
7 7 9 8
3 5 7 5
7 5 2 4
3 3 7 8
6 6 3 2


Output

0.57142857142857139685


Input

4
7 7 9 8
0 3 -5 4
5 0 5 4
9 9 -1 -6
10 5 -7 -10


Output

-1

Note

Here is a picture of the first sample

Points A, B, C, D - start mice positions, segments are their paths.

<image>

Then, at first time when all mice will be in rectangle it will be looks like this:

<image>

Here is a picture of the second sample

<image>

Points A, D, B will never enter rectangle.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Problem statement

Find the number of integer sequences $ X_1, X_2, ..., X_N $ that satisfy the following conditions.


1. For any integer $ i $ ($ 1 \ leq i \ leq N $), there exists $ j $ ($ 1 \ leq j \ leq N $) such that $ X_j = i $.
2. $ X_s = t $
3. $ X_ {a_i} <X_ {b_i} $ ($ 1 \ leq i \ leq C $)

Constraint

* $ 1 \ leq N \ leq 2000 $
* $ 0 \ leq C \ leq N $
* $ 1 \ leq s \ leq N $
* $ 1 \ leq t \ leq N $
* $ 1 \ leq a_i \ leq N $
* $ 1 \ leq b_i \ leq N $
* $ a_i \ neq b_i $
* $ i \ neq j $ then $ a_i \ neq a_j $



input

Input follows the following format. All given numbers are integers.


$ N $ $ C $ $ s $ $ t $
$ a_1 $ $ b_1 $
$ a_2 $ $ b_2 $
$ ... $
$ a_C $ $ b_C $

output

Divide the number of sequences that satisfy the condition by $ 10 ^ 9 + 7 $ and output the remainder on one row (it is easy to show that the number of sequences that satisfy the condition is at most finite).

Examples

Input

3 1 1 1
1 3


Output

2


Input

4 2 1 1
2 3
3 2


Output

0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Makes solves problems on Decoforces and lots of other different online judges. Each problem is denoted by its difficulty — a positive integer number. Difficulties are measured the same across all the judges (the problem with difficulty d on Decoforces is as hard as the problem with difficulty d on any other judge). 

Makes has chosen n problems to solve on Decoforces with difficulties a_1, a_2, ..., a_{n}. He can solve these problems in arbitrary order. Though he can solve problem i with difficulty a_{i} only if he had already solved some problem with difficulty $d \geq \frac{a_{i}}{2}$ (no matter on what online judge was it).

Before starting this chosen list of problems, Makes has already solved problems with maximum difficulty k.

With given conditions it's easy to see that Makes sometimes can't solve all the chosen problems, no matter what order he chooses. So he wants to solve some problems on other judges to finish solving problems from his list. 

For every positive integer y there exist some problem with difficulty y on at least one judge besides Decoforces.

Makes can solve problems on any judge at any time, it isn't necessary to do problems from the chosen list one right after another.

Makes doesn't have too much free time, so he asked you to calculate the minimum number of problems he should solve on other judges in order to solve all the chosen problems from Decoforces.


-----Input-----

The first line contains two integer numbers n, k (1 ≤ n ≤ 10^3, 1 ≤ k ≤ 10^9).

The second line contains n space-separated integer numbers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9).


-----Output-----

Print minimum number of problems Makes should solve on other judges in order to solve all chosen problems on Decoforces.


-----Examples-----
Input
3 3
2 1 9

Output
1

Input
4 20
10 3 6 3

Output
0



-----Note-----

In the first example Makes at first solves problems 1 and 2. Then in order to solve the problem with difficulty 9, he should solve problem with difficulty no less than 5. The only available are difficulties 5 and 6 on some other judge. Solving any of these will give Makes opportunity to solve problem 3.

In the second example he can solve every problem right from the start.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Bayan Bus

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The final round of Bayan Programming Contest will be held in Tehran, and the participants will be carried around with a yellow bus. The bus has 34 passenger seats: 4 seats in the last row and 3 seats in remaining rows. 

The event coordinator has a list of *k* participants who should be picked up at the airport. When a participant gets on the bus, he will sit in the last row with an empty seat. If there is more than one empty seat in that row, he will take the leftmost one. 

In order to keep track of the people who are on the bus, the event coordinator needs a figure showing which seats are going to be taken by *k* participants. Your task is to draw the figure representing occupied seats.

Input Specification:
The only line of input contains integer *k*, (0<=≤<=*k*<=≤<=34), denoting the number of participants.

Output Specification:
Print the figure of a bus with *k* passengers as described in sample tests. Character '#' denotes an empty seat, while 'O' denotes a taken seat. 'D' is the bus driver and other characters in the output are for the purpose of beautifying the figure. Strictly follow the sample test cases output format. Print exactly six lines. Do not output extra space or other characters.

Demo Input:
['9\n', '20\n']

Demo Output:
['+------------------------+\n|O.O.O.#.#.#.#.#.#.#.#.|D|)\n|O.O.O.#.#.#.#.#.#.#.#.|.|\n|O.......................|\n|O.O.#.#.#.#.#.#.#.#.#.|.|)\n+------------------------+\n', '+------------------------+\n|O.O.O.O.O.O.O.#.#.#.#.|D|)\n|O.O.O.O.O.O.#.#.#.#.#.|.|\n|O.......................|\n|O.O.O.O.O.O.#.#.#.#.#.|.|)\n+------------------------+\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Mentors

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
In BerSoft $n$ programmers work, the programmer $i$ is characterized by a skill $r_i$.

A programmer $a$ can be a mentor of a programmer $b$ if and only if the skill of the programmer $a$ is strictly greater than the skill of the programmer $b$ $(r_a &gt; r_b)$ and programmers $a$ and $b$ are not in a quarrel.

You are given the skills of each programmers and a list of $k$ pairs of the programmers, which are in a quarrel (pairs are unordered). For each programmer $i$, find the number of programmers, for which the programmer $i$ can be a mentor.

Input Specification:
The first line contains two integers $n$ and $k$ $(2 \le n \le 2 \cdot 10^5$, $0 \le k \le \min(2 \cdot 10^5, \frac{n \cdot (n - 1)}{2}))$ — total number of programmers and number of pairs of programmers which are in a quarrel.

The second line contains a sequence of integers $r_1, r_2, \dots, r_n$ $(1 \le r_i \le 10^{9})$, where $r_i$ equals to the skill of the $i$-th programmer.

Each of the following $k$ lines contains two distinct integers $x$, $y$ $(1 \le x, y \le n$, $x \ne y)$ — pair of programmers in a quarrel. The pairs are unordered, it means that if $x$ is in a quarrel with $y$ then $y$ is in a quarrel with $x$. Guaranteed, that for each pair $(x, y)$ there are no other pairs $(x, y)$ and $(y, x)$ in the input.

Output Specification:
Print $n$ integers, the $i$-th number should be equal to the number of programmers, for which the $i$-th programmer can be a mentor. Programmers are numbered in the same order that their skills are given in the input.

Demo Input:
['4 2\n10 4 10 15\n1 2\n4 3\n', '10 4\n5 4 1 5 4 3 7 1 2 5\n4 6\n2 1\n10 8\n3 5\n']

Demo Output:
['0 0 1 2 \n', '5 4 0 5 3 3 9 0 2 5 \n']

Note:
In the first example, the first programmer can not be mentor of any other (because only the second programmer has a skill, lower than first programmer skill, but they are in a quarrel). The second programmer can not be mentor of any other programmer, because his skill is minimal among others. The third programmer can be a mentor of the second programmer. The fourth programmer can be a mentor of the first and of the second programmers. He can not be a mentor of the third programmer, because they are in a quarrel.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Sherlock has a new girlfriend (so unlike him!). Valentine's day is coming and he wants to gift her some jewelry.

He bought n pieces of jewelry. The i-th piece has price equal to i + 1, that is, the prices of the jewelry are 2, 3, 4, ... n + 1.

Watson gave Sherlock a challenge to color these jewelry pieces such that two pieces don't have the same color if the price of one piece is a prime divisor of the price of the other piece. Also, Watson asked him to minimize the number of different colors used.

Help Sherlock complete this trivial task.


-----Input-----

The only line contains single integer n (1 ≤ n ≤ 100000) — the number of jewelry pieces.


-----Output-----

The first line of output should contain a single integer k, the minimum number of colors that can be used to color the pieces of jewelry with the given constraints.

The next line should consist of n space-separated integers (between 1 and k) that specify the color of each piece in the order of increasing price.

If there are multiple ways to color the pieces using k colors, you can output any of them.


-----Examples-----
Input
3

Output
2
1 1 2 
Input
4

Output
2
2 1 1 2



-----Note-----

In the first input, the colors for first, second and third pieces of jewelry having respective prices 2, 3 and 4 are 1, 1 and 2 respectively.

In this case, as 2 is a prime divisor of 4, colors of jewelry having prices 2 and 4 must be distinct.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.