vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
The median of a sequence is the element in the middle of the sequence after it is sorted. For a sequence with even size, the median is the average of the two middle elements of the sequence after sorting. For example, for a sequence $A = [1, 3, 3, 5, 4, 7, 11]$, the median is equal to $4$, and for $A = [2, 3, 4, 5]$, the median is equal to $(3+4)/2 = 3.5$.
Fulu is a famous programmer in his country. He wrote the following program (given in pseudocode) for finding the median in a sequence $A$ with length $N$:
read(N)
read(A[0], A[1], ..., A[N-1])
sort(A)
# simultaneously remove elements A[K] and A[N mod K] from the array A
# the order of the remaining N-2 elements is unchanged
remove(A[K], A[N mod K])
return A[(N-2)/2] # integer division

The program takes an integer $K$ as a parameter. Fulu can choose this integer arbitrarily between $1$ and $N-1$ inclusive.
Little Lima, Fulu's friend, thinks Fulu's program is wrong (as always). As finding one counterexample would be an easy task for Lima (he has already found the sequence $A = [34, 23, 35, 514]$, which is a counterexample for any $K \le 3$), Lima decided to make hacking more interesting. Fulu should give him four parameters $S, K, m, M$ (in addition to $N$) and Lima should find the lexicographically smallest proper sequence $A$ with length $N$ as a counterexample.
We say that a sequence $A$ with length $N$ ($0$-indexed) is proper if it satisfies the following conditions:
- it contains only positive integers
- $A_0 + A_1 +A_2 + \dots + A_{N-1} = S$
- $m \le A_i \le M$ for each $0 \le i < N$
- the number returned by Fulu's program, ran with the given parameter $K$, is different from the correct median of the sequence $A$
Can you help Lima find the lexicographically smallest counterexample or determine that Fulu's program works perfectly for the given parameters?

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first and only line of each test case contains five space-separated integers $N$, $S$, $K$, $m$ and $M$.

-----Output-----
For each test case, if there is no proper sequence, print a single line containing the integer $-1$; otherwise, print a single line containing $N$ space-separated integers — the lexicographically smallest proper sequence.

-----Constraints-----
- $1 \le T \le 8$
- $3 \le N \le 10^5$
- $1 \le K \le N-1$
- $1 \le S \le 10^9$
- $1 \le m \le M \le S$

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

-----Example Output-----
1 1 4
-1

-----Explanation-----
Example case 1: For the sequence $A = [1, 1, 4]$, it is already sorted, so the program would just remove the first two elements ($K=1$, $N\%K=0$) and return the only remaining element $4$. Obviously, the median of the original sequence is $1$. It can be shown that there is no lexicographically smaller proper sequence.
Example case 2: The only possible sequence is $A = [1, 1, 1, 1]$, which is not proper, since Fulu's program will give the correct answer $1$ for it.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a rectangular grid of size $n \times m$. Each cell has a number written on it; the number on the cell ($i, j$) is $a_{i, j}$. Your task is to calculate the number of paths from the upper-left cell ($1, 1$) to the bottom-right cell ($n, m$) meeting the following constraints:

  You can move to the right or to the bottom only. Formally, from the cell ($i, j$) you may move to the cell ($i, j + 1$) or to the cell ($i + 1, j$). The target cell can't be outside of the grid.  The xor of all the numbers on the path from the cell ($1, 1$) to the cell ($n, m$) must be equal to $k$ (xor operation is the bitwise exclusive OR, it is represented as '^' in Java or C++ and "xor" in Pascal). 

Find the number of such paths in the given grid.


-----Input-----

The first line of the input contains three integers $n$, $m$ and $k$ ($1 \le n, m \le 20$, $0 \le k \le 10^{18}$) — the height and the width of the grid, and the number $k$.

The next $n$ lines contain $m$ integers each, the $j$-th element in the $i$-th line is $a_{i, j}$ ($0 \le a_{i, j} \le 10^{18}$).


-----Output-----

Print one integer — the number of paths from ($1, 1$) to ($n, m$) with xor sum equal to $k$.


-----Examples-----
Input
3 3 11
2 1 5
7 10 0
12 6 4

Output
3

Input
3 4 2
1 3 3 3
0 3 3 2
3 0 1 1

Output
5

Input
3 4 1000000000000000000
1 3 3 3
0 3 3 2
3 0 1 1

Output
0



-----Note-----

All the paths from the first example:   $(1, 1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 2) \rightarrow (3, 3)$;  $(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3)$;  $(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3)$. 

All the paths from the second example:   $(1, 1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 2) \rightarrow (3, 3) \rightarrow (3, 4)$;  $(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3) \rightarrow (3, 4)$;  $(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (2, 4) \rightarrow (3, 4)$;  $(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3) \rightarrow (3, 4)$;  $(1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3) \rightarrow (3, 4)$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Leo Jr. draws pictures in his notebook with checkered sheets (that is, each sheet has a regular square grid printed on it). We can assume that the sheets are infinitely large in any direction.

To draw a picture, Leo Jr. colors some of the cells on a sheet gray. He considers the resulting picture beautiful if the following conditions are satisfied:

  * The picture is connected, that is, it is possible to get from any gray cell to any other by following a chain of gray cells, with each pair of adjacent cells in the path being neighbours (that is, sharing a side).
  * Each gray cell has an even number of gray neighbours.
  * There are exactly n gray cells with all gray neighbours. The number of other gray cells can be arbitrary (but reasonable, so that they can all be listed).



Leo Jr. is now struggling to draw a beautiful picture with a particular choice of n. Help him, and provide any example of a beautiful picture.

To output cell coordinates in your answer, assume that the sheet is provided with a Cartesian coordinate system such that one of the cells is chosen to be the origin (0, 0), axes 0x and 0y are orthogonal and parallel to grid lines, and a unit step along any axis in any direction takes you to a neighbouring cell.

Input

The only line contains a single integer n (1 ≤ n ≤ 500) — the number of gray cells with all gray neighbours in a beautiful picture.

Output

In the first line, print a single integer k — the number of gray cells in your picture. For technical reasons, k should not exceed 5 ⋅ 10^5.

Each of the following k lines should contain two integers — coordinates of a gray cell in your picture. All listed cells should be distinct, and the picture should satisdfy all the properties listed above. All coordinates should not exceed 10^9 by absolute value.

One can show that there exists an answer satisfying all requirements with a small enough k.

Example

Input


4


Output


12
1 0
2 0
0 1
1 1
2 1
3 1
0 2
1 2
2 2
3 2
1 3
2 3

Note

The answer for the sample is pictured below:

<image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The city administration of IT City decided to fix up a symbol of scientific and technical progress in the city's main square, namely an indicator board that shows the effect of Moore's law in real time.

Moore's law is the observation that the number of transistors in a dense integrated circuit doubles approximately every 24 months. The implication of Moore's law is that computer performance as function of time increases exponentially as well.

You are to prepare information that will change every second to display on the indicator board. Let's assume that every second the number of transistors increases exactly 1.000000011 times.

Input

The only line of the input contains a pair of integers n (1000 ≤ n ≤ 10 000) and t (0 ≤ t ≤ 2 000 000 000) — the number of transistors in the initial time and the number of seconds passed since the initial time.

Output

Output one number — the estimate of the number of transistors in a dence integrated circuit in t seconds since the initial time. The relative error of your answer should not be greater than 10 - 6.

Examples

Input

1000 1000000


Output

1011.060722383550382782399454922040

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You found a complete, undirected graph with $n$ nodes, labeled $1$ to $n$. Each edge has a color. For simplicity, each color is identified by a number between $1$ and $300$ inclusive. Interestingly, you noticed that for each and every simple cycle in this graph, there are at least two adjacent edges on this cycle which have the same color.

For each non-empty subset of nodes in graph $S$, let $f(S)$ denote the size of the maximum subset of nodes you can choose from $S$ such that all edges between the chosen nodes are the same color. Compute the sum of $f(S)$ over all non empty subsets $S$ of nodes in the graph.

-----Input-----
Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. The first line of input will contain a single integer $n$ ($1 \le n \le 300$), which is the number of nodes in the graph.

The next $n$ lines will each contain $n$ integers $c$ ($0 \le c \le 300$), which is a matrix representing the colors of the edges, where $c[x,y]$ is the color of the edge between node $x$ and node $y$. It is guaranteed that the values on the diagonal will be $0$ ($c[x,x]=0$), since there is no edge from a node to itself. It is also guaranteed that the matrix is symmetric and the off-diagonal colors range from $1$ to $300$ ($1 \le c[x,y] = c[y,x] \le 300$ for $x \ne y$).

-----Output-----
Output a single integer, which is the sum of $f(S)$ over all non empty subsets $S$ of nodes in the graph. Since this number may be very large, output it modulo $10^9+7$.

-----Examples-----
Sample Input:
4
0 1 1 1
1 0 2 2
1 2 0 3
1 2 3 0
Sample Output:
26

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You should have done Product Partitions I to do this second part.
If you solved it, you should have notice that we try to obtain the multiplicative partitions with ```n ≤ 100 ```.

In this kata we will have more challenging values, our ```n ≤  10000```. So, we need a more optimized a faster code.

We need the function ```prod_int_partII()``` that will give all the amount of different products, excepting the number itself multiplied by one.

The function ```prod_int_partII()``` will receive two arguments, the number ```n``` for the one we have to obtain all the multiplicative partitions, and an integer s that determines the products that have an amount of factors equals to ```s```.

The function will output a list with this structure:
```python
[(1), (2), [(3)]]

(1) Total amount of different products we can obtain, using the factors of n. (We do not consider the product n . 1)

(2) Total amount of products that have an amount of factors equals to s.

[(3)] A list of lists with each product represented with by a sorted list of the factors. All the product- lists should be sorted also.
If we have only one product-list as a result, the function will give only the list 
and will not use the list of lists
```
Let's see some cases:
```python
prod_int_partII(36, 3) == [8, 3, [[2, 2, 9], [2, 3, 6], [3, 3, 4]]]

/// (1) ----> 8 # Amount of different products, they are: [2, 2, 3, 3], [2, 2, 9], 
[2, 3, 6], [2, 18], [3, 3, 4], [3, 12], [4, 9], [6, 6] (8 products)
    
    (2) ----> 3 # Amount of products with three factors (see them bellow)

    (3) ----> [[2, 2, 9], [2, 3, 6], [3, 3, 4]] # These are the products with 3 factors
```
```python
prod_int_partII(48, 5) == [11, 1, [2, 2, 2, 2, 3]] # Only one list.
```
Again consider that some numbers will not have multiplicative partitions.
```python
prod_int_partII(37, 2) == [0, 0, []]
```
Happy coding!!

(Recursion is advisable)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Today was a sad day. Having bought a new beard trimmer, I set it to the max setting and shaved away at my joyous beard. Stupidly, I hadnt checked just how long the max setting was, and now I look like Ive just started growing it!

Your task, given a beard represented as an arrayof arrays, is to trim the beard as follows:

['|', 'J', '|', '|'],
['|', '|', '|', 'J'],
['...', '...', '...', '...'];

To trim the beard use the following rules:

trim any curled hair --> replace 'J' with '|'
trim any hair from the chin (last array) --> replace '|' or 'J' with '...'

All sub arrays will be same length. Return the corrected array of arrays

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an integer array nums that may contain duplicates. Your task is to return all possible subsets. Return only unique subsets and they can be in any order.
Example: 
Input: 
nums = [1,2,2] 
Output: 
[[],[1],[1,2],[1,2,2],[2],[2,2]]
Explanation: 
We can have subsets ranging from length 0 to 3. which are listed above. Also the subset [1,2] appears twice but is printed only once as we require only unique subsets.
Your Task:
Complete the function vector> printUniqueSubset(), which takes  a vector nums and return a vector of vector consisting of all unique subsets.
Expected Time Complexity: O(K2^{N}).
Expected Auxiliary Space: O(K2^{N}).
Constraints:
1 <= nums.length <= 10
-10 <= nums[i] <= 10

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given a table consisting of *n* rows and *m* columns. Each cell of the table contains either 0 or 1. In one move, you are allowed to pick any row or any column and invert all values, that is, replace 0 by 1 and vice versa.

What is the minimum number of cells with value 1 you can get after applying some number of operations?

Input Specification:
The first line of the input contains two integers *n* and *m* (1<=≤<=*n*<=≤<=20, 1<=≤<=*m*<=≤<=100<=000) — the number of rows and the number of columns, respectively.

Then *n* lines follows with the descriptions of the rows. Each line has length *m* and contains only digits '0' and '1'.

Output Specification:
Output a single integer — the minimum possible number of ones you can get after applying some sequence of operations.

Demo Input:
['3 4\n0110\n1010\n0111\n']

Demo Output:
['2\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alexey recently held a programming contest for students from Berland. n students participated in a contest, i-th of them solved ai problems. Now he wants to award some contestants. Alexey can award the students with diplomas of three different degrees. Each student either will receive one diploma of some degree, or won't receive any diplomas at all. Let cntx be the number of students that are awarded with diplomas of degree x (1 ≤ x ≤ 3). The following conditions must hold:

  * For each x (1 ≤ x ≤ 3) cntx > 0; 
  * For any two degrees x and y cntx ≤ 2·cnty. 



Of course, there are a lot of ways to distribute the diplomas. Let bi be the degree of diploma i-th student will receive (or  - 1 if i-th student won't receive any diplomas). Also for any x such that 1 ≤ x ≤ 3 let cx be the maximum number of problems solved by a student that receives a diploma of degree x, and dx be the minimum number of problems solved by a student that receives a diploma of degree x. Alexey wants to distribute the diplomas in such a way that:

  1. If student i solved more problems than student j, then he has to be awarded not worse than student j (it's impossible that student j receives a diploma and i doesn't receive any, and also it's impossible that both of them receive a diploma, but bj < bi); 
  2. d1 - c2 is maximum possible; 
  3. Among all ways that maximize the previous expression, d2 - c3 is maximum possible; 
  4. Among all ways that correspond to the two previous conditions, d3 - c - 1 is maximum possible, where c - 1 is the maximum number of problems solved by a student that doesn't receive any diploma (or 0 if each student is awarded with some diploma). 



Help Alexey to find a way to award the contestants!

Input

The first line contains one integer number n (3 ≤ n ≤ 3000).

The second line contains n integer numbers a1, a2, ..., an (1 ≤ ai ≤ 5000).

Output

Output n numbers. i-th number must be equal to the degree of diploma i-th contestant will receive (or  - 1 if he doesn't receive any diploma).

If there are multiple optimal solutions, print any of them. It is guaranteed that the answer always exists.

Examples

Input

4
1 2 3 4


Output

3 3 2 1 


Input

6
1 4 3 1 1 2


Output

-1 1 2 -1 -1 3 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Btoh yuo adn yuor roomatme lhoate wianshg disehs, btu stlil sdmoeboy msut peorrfm tihs cohre dialy. Oen dya yuo decdie to idourtcne smoe syestm. Yuor rmmotaoe sstgegus teh fooniwllg dael. Yuo argee on tow arayrs of ientgres M adn R, nmebur upmicnog dyas (induiclng teh cunrret oen) wtih sicsescuve irnegets (teh ceurrnt dya is zreo), adn yuo wsah teh diehss on dya D if adn olny if terhe etsixs an iednx i scuh taht D mod M[i] = R[i], otwsehrie yuor rmootmae deos it. Yuo lkie teh cncepot, btu yuor rmotaome's cuinnng simle meaks yuo ssecupt sthnoemig, so yuo itennd to vefriy teh fnerisas of teh aemnrgeet.

Yuo aer geivn ayarrs M adn R. Cuaclatle teh pceanregte of dyas on wchih yuo edn up dnoig teh wisahng. Amsuse taht yuo hvae iiiftlneny mnay dyas aehad of yuo. 

Input

The first line of input contains a single integer N (1 ≤ N ≤ 16).

The second and third lines of input contain N integers each, all between 0 and 16, inclusive, and represent arrays M and R, respectively. All M[i] are positive, for each i R[i] < M[i].

Output

Output a single real number. The answer is considered to be correct if its absolute or relative error does not exceed 10 - 4.

Examples

Input

1
2
0


Output

0.500000


Input

2
2 3
1 0


Output

0.666667

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Igor is a post-graduate student of chemistry faculty in Berland State University (BerSU). He needs to conduct a complicated experiment to write his thesis, but laboratory of BerSU doesn't contain all the materials required for this experiment.

Fortunately, chemical laws allow material transformations (yes, chemistry in Berland differs from ours). But the rules of transformation are a bit strange.

Berland chemists are aware of *n* materials, numbered in the order they were discovered. Each material can be transformed into some other material (or vice versa). Formally, for each *i* (2<=≤<=*i*<=≤<=*n*) there exist two numbers *x**i* and *k**i* that denote a possible transformation: *k**i* kilograms of material *x**i* can be transformed into 1 kilogram of material *i*, and 1 kilogram of material *i* can be transformed into 1 kilogram of material *x**i*. Chemical processing equipment in BerSU allows only such transformation that the amount of resulting material is always an integer number of kilograms.

For each *i* (1<=≤<=*i*<=≤<=*n*) Igor knows that the experiment requires *a**i* kilograms of material *i*, and the laboratory contains *b**i* kilograms of this material. Is it possible to conduct an experiment after transforming some materials (or none)?

Input Specification:
The first line contains one integer number *n* (1<=≤<=*n*<=≤<=105) — the number of materials discovered by Berland chemists.

The second line contains *n* integer numbers *b*1,<=*b*2... *b**n* (1<=≤<=*b**i*<=≤<=1012) — supplies of BerSU laboratory.

The third line contains *n* integer numbers *a*1,<=*a*2... *a**n* (1<=≤<=*a**i*<=≤<=1012) — the amounts required for the experiment.

Then *n*<=-<=1 lines follow. *j*-th of them contains two numbers *x**j*<=+<=1 and *k**j*<=+<=1 that denote transformation of (*j*<=+<=1)-th material (1<=≤<=*x**j*<=+<=1<=≤<=*j*,<=1<=≤<=*k**j*<=+<=1<=≤<=109).

Output Specification:
Print YES if it is possible to conduct an experiment. Otherwise print NO.

Demo Input:
['3\n1 2 3\n3 2 1\n1 1\n1 1\n', '3\n3 2 1\n1 2 3\n1 1\n1 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.
Caracal is fighting with a monster.
The health of the monster is H.
Caracal can attack by choosing one monster. When a monster is attacked, depending on that monster's health, the following happens:
 - If the monster's health is 1, it drops to 0.
 - If the monster's health, X, is greater than 1, that monster disappears. Then, two new monsters appear, each with the health of \lfloor X/2 \rfloor.
(\lfloor r \rfloor denotes the greatest integer not exceeding r.)
Caracal wins when the healths of all existing monsters become 0 or below.
Find the minimum number of attacks Caracal needs to make before winning.

-----Constraints-----
 - 1 \leq H \leq 10^{12}
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
H

-----Output-----
Find the minimum number of attacks Caracal needs to make before winning.

-----Sample Input-----
2

-----Sample Output-----
3

When Caracal attacks the initial monster, it disappears, and two monsters appear, each with the health of 1.
Then, Caracal can attack each of these new monsters once and win with a total of three attacks.

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