vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
If

the given input positive integer is equal to the sum of its proper positive divisors then it will form a triangular array of numbers in which those at the ends of the rows are 1 and each of the others is the sum of the nearest two numbers in the row above (the apex, 1, being at the top). OR it can also be understood as the triangle started by 1, then followed by the binomial coefficient (n,k),
where n is the non negative integer and k is the integer between 0 and n.

else

print error

NOTE

What you have to do??

Download our code in which there are mistakes.

Link to download : Download the solution code

You have to add or edit the code to solve the problem.

So, its very simple, correct our given solution to solve the above writen problem and submit it here :)

NOTE : The code given by us is in C but  you can mold the code to C++, JAVA, C# but please keep in mind that the logic code(the conditional statements,loops,etc.) should remain same.

If you come up with some other code that will be appreciable but will not be considered for giving prizes. 

SAMPLE INPUT
6

SAMPLE OUTPUT
1
11
121
1331
14641
15101051

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a positive number x. Find the smallest positive integer number that has the sum of digits equal to x and all digits are distinct (unique).

Input

The first line contains a single positive integer t (1 ≤ t ≤ 50) — the number of test cases in the test. Then t test cases follow.

Each test case consists of a single integer number x (1 ≤ x ≤ 50).

Output

Output t answers to the test cases:

  * if a positive integer number with the sum of digits equal to x and all digits are different exists, print the smallest such number; 
  * otherwise print -1. 

Example

Input


4
1
5
15
50


Output


1
5
69
-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are $n$ workers and $m$ tasks. The workers are numbered from $1$ to $n$. Each task $i$ has a value $a_i$ — the index of worker who is proficient in this task.

Every task should have a worker assigned to it. If a worker is proficient in the task, they complete it in $1$ hour. Otherwise, it takes them $2$ hours.

The workers work in parallel, independently of each other. Each worker can only work on one task at once.

Assign the workers to all tasks in such a way that the tasks are completed as early as possible. The work starts at time $0$. What's the minimum time all tasks can be completed by?


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.

The first line of each testcase contains two integers $n$ and $m$ ($1 \le n \le m \le 2 \cdot 10^5$) — the number of workers and the number of tasks.

The second line contains $m$ integers $a_1, a_2, \dots, a_m$ ($1 \le a_i \le n$) — the index of the worker proficient in the $i$-th task.

The sum of $m$ over all testcases doesn't exceed $2 \cdot 10^5$.


-----Output-----

For each testcase, print a single integer — the minimum time all tasks can be completed by.


-----Examples-----

Input
4
2 4
1 2 1 2
2 4
1 1 1 1
5 5
5 1 3 2 4
1 1
1
Output
2
3
1
1


-----Note-----

In the first testcase, the first worker works on tasks $1$ and $3$, and the second worker works on tasks $2$ and $4$. Since they both are proficient in the corresponding tasks, they take $1$ hour on each. Both of them complete $2$ tasks in $2$ hours. Thus, all tasks are completed by $2$ hours.

In the second testcase, it's optimal to assign the first worker to tasks $1, 2$ and $3$ and the second worker to task $4$. The first worker spends $3$ hours, the second worker spends $2$ hours (since they are not proficient in the taken task).

In the third example, each worker can be assigned to the task they are proficient at. Thus, each of them complete their task in $1$ hour.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Pikachu had an array with him. He wrote down all the non-empty subsequences of the array on paper. Note that an array of size n has 2^{n} - 1 non-empty subsequences in it. 

Pikachu being mischievous as he always is, removed all the subsequences in which Maximum_element_of_the_subsequence  -  Minimum_element_of_subsequence  ≥ d

Pikachu was finally left with X subsequences. 

However, he lost the initial array he had, and now is in serious trouble. He still remembers the numbers X and d. He now wants you to construct any such array which will satisfy the above conditions. All the numbers in the final array should be positive integers less than 10^18. 

Note the number of elements in the output array should not be more than 10^4. If no answer is possible, print  - 1.


-----Input-----

The only line of input consists of two space separated integers X and d (1 ≤ X, d ≤ 10^9).


-----Output-----

Output should consist of two lines.

First line should contain a single integer n (1 ≤ n ≤ 10 000)— the number of integers in the final array.

Second line should consist of n space separated integers — a_1, a_2, ... , a_{n} (1 ≤ a_{i} < 10^18).

If there is no answer, print a single integer -1. If there are multiple answers, print any of them.


-----Examples-----
Input
10 5

Output
6
5 50 7 15 6 100
Input
4 2

Output
4
10 100 1000 10000


-----Note-----

In the output of the first example case, the remaining subsequences after removing those with Maximum_element_of_the_subsequence  -  Minimum_element_of_subsequence  ≥ 5 are [5], [5, 7], [5, 6], [5, 7, 6], [50], [7], [7, 6], [15], [6], [100]. There are 10 of them. Hence, the array [5, 50, 7, 15, 6, 100] is valid.

Similarly, in the output of the second example case, the remaining sub-sequences after removing those with Maximum_element_of_the_subsequence  -  Minimum_element_of_subsequence  ≥ 2 are [10], [100], [1000], [10000]. There are 4 of them. Hence, the array [10, 100, 1000, 10000] is valid.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array A of size N.

A partitioning of the array A is the splitting of A into one or more non-empty contiguous subarrays such that each element of A belongs to exactly one of these subarrays.

Find the number of ways to partition A such that the parity of the sum of elements within the subarrays is alternating. In other words, if S_{i} denotes the sum of the elements in the i-th subarray, then either
S_{1} is odd, S_{2} is even, S_{3} is odd and so on.
or S_{1} is even, S_{2} is odd, S_{3} is even and so on.

For example if A = [1, 2, 3, 3, 5]. One way to partition A is [1, 2] [3, 3] [5]. Another way to partition A is [1] [2] [3] [3, 5]. Note that there exists more ways to partition this array.

Since the answer may be large, output it modulo 998244353.

------ Input Format ------ 

- The first line contains a single integer T - the number of test cases. Then the test cases follow.
- The first line of each test case contains an integer N - the size of the array A.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \dots, A_{N} denoting the array A.

------ Output Format ------ 

For each test case, output the answer modulo 998244353.

------ Constraints ------ 

$1 ≤ T ≤ 10000$
$1 ≤ N ≤ 2 \cdot 10^{5} $
$0 ≤ A_{i} ≤ 10^{9} $
- Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$

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

----- explanation 1 ------ 
Test case 1: The array can be partitioned as follows
- $[1] [2] [3]$
- $[1, 2, 3]$

Test case 2: The array can be partitioned as follows
- $[4, 4, 4, 4]$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Andryusha and Colored Balloons

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Andryusha goes through a park each day. The squares and paths between them look boring to Andryusha, so he decided to decorate them.

The park consists of *n* squares connected with (*n*<=-<=1) bidirectional paths in such a way that any square is reachable from any other using these paths. Andryusha decided to hang a colored balloon at each of the squares. The baloons' colors are described by positive integers, starting from 1. In order to make the park varicolored, Andryusha wants to choose the colors in a special way. More precisely, he wants to use such colors that if *a*, *b* and *c* are distinct squares that *a* and *b* have a direct path between them, and *b* and *c* have a direct path between them, then balloon colors on these three squares are distinct.

Andryusha wants to use as little different colors as possible. Help him to choose the colors!

Input Specification:
The first line contains single integer *n* (3<=≤<=*n*<=≤<=2·105) — the number of squares in the park.

Each of the next (*n*<=-<=1) lines contains two integers *x* and *y* (1<=≤<=*x*,<=*y*<=≤<=*n*) — the indices of two squares directly connected by a path.

It is guaranteed that any square is reachable from any other using the paths.

Output Specification:
In the first line print single integer *k* — the minimum number of colors Andryusha has to use.

In the second line print *n* integers, the *i*-th of them should be equal to the balloon color on the *i*-th square. Each of these numbers should be within range from 1 to *k*.

Demo Input:
['3\n2 3\n1 3\n', '5\n2 3\n5 3\n4 3\n1 3\n', '5\n2 1\n3 2\n4 3\n5 4\n']

Demo Output:
['3\n1 3 2 ', '5\n1 3 2 5 4 ', '3\n1 2 3 1 2 ']

Note:
In the first sample the park consists of three squares: 1 → 3 → 2. Thus, the balloon colors have to be distinct.

In the second example there are following triples of consequently connected squares: 
 -  1 → 3 → 2 -  1 → 3 → 4 -  1 → 3 → 5 -  2 → 3 → 4 -  2 → 3 → 5 -  4 → 3 → 5 
In the third example there are following triples: 
 -  1 → 2 → 3 -  2 → 3 → 4 -  3 → 4 → 5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Liliputs are holding a drawing competition for K kids, but with K human-sized pencils stolen from humans. In order to make life easier for the kids, the organizers want to give a pencil to each kid in a way such that the sum of the absolute differences of the height of a kid and the length of the pencil assigned to him/her is minimized. What is the minimum sum of absolute differences that can be achieved?

Input
The first line contains the number of test cases N (0 < N ≤ 3). 
For each test case, the first line contains the number of kids and pencils K (0 < K ≤ 100). The second line contains K positive integers, each containing the height in millimeter of a kid. The third line contains K positive integers, each containing the length in millimeter of a pencil.

Output
For each test case, print the case number, followed by a colon, followed by a single space, followed by a single integer indicating the minimum sum of absolute differences achieved (in millimeter).

Sample Input

2
5
51 60 51 72 70 
65 60 88 72 88 
4 
123 234 188 175 
219 334 122 233

Sample Output

Case 1: 69 
Case 2: 190

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given the prices of three presents. Also there are three sisters. It is known that the most valuable present is for the eldest sister. The second (by price) is for the second sister. And the less valuable present is for the youngest sister. If two (or three) presents have the same price, corresponding sisters may get the in a random way.

Input

The only line contains three integer numbers a1, a2, a3 (1 ≤ a1, a2, a3 ≤ 100) — the prices of the presents.

Output

Print three numbers i1, i2, i3 (1 ≤ i1, i2, i3 ≤ 3), all of them should be distinct. The first number stands for the seniority of the sister which will get the first present (1 stands for the eldest, 3 for the youngest). The second and third numbers mean the seniority of the sisters which get the second and the third present respectively.

If there are multiple answers, print any of them.

Examples

Input

11 13 1


Output

2 1 3 

Input

30 10 30


Output

1 3 2 

Note

In the second sample another possible answer is "2 3 1".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Overlooking the captivating blend of myriads of vernal hues, Arkady the painter lays out a long, long canvas.

Arkady has a sufficiently large amount of paint of three colours: cyan, magenta, and yellow. On the one-dimensional canvas split into n consecutive segments, each segment needs to be painted in one of the colours.

Arkady has already painted some (possibly none or all) segments and passes the paintbrush to you. You are to determine whether there are at least two ways of colouring all the unpainted segments so that no two adjacent segments are of the same colour. Two ways are considered different if and only if a segment is painted in different colours in them.


-----Input-----

The first line contains a single positive integer n (1 ≤ n ≤ 100) — the length of the canvas.

The second line contains a string s of n characters, the i-th of which is either 'C' (denoting a segment painted in cyan), 'M' (denoting one painted in magenta), 'Y' (one painted in yellow), or '?' (an unpainted one).


-----Output-----

If there are at least two different ways of painting, output "Yes"; otherwise output "No" (both without quotes).

You can print each character in any case (upper or lower).


-----Examples-----
Input
5
CY??Y

Output
Yes

Input
5
C?C?Y

Output
Yes

Input
5
?CYC?

Output
Yes

Input
5
C??MM

Output
No

Input
3
MMY

Output
No



-----Note-----

For the first example, there are exactly two different ways of colouring: CYCMY and CYMCY.

For the second example, there are also exactly two different ways of colouring: CMCMY and CYCMY.

For the third example, there are four ways of colouring: MCYCM, MCYCY, YCYCM, and YCYCY.

For the fourth example, no matter how the unpainted segments are coloured, the existing magenta segments will prevent the painting from satisfying the requirements. The similar is true for the fifth example.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n students at Berland State University. Every student has two skills, each measured as a number: ai — the programming skill and bi — the sports skill.

It is announced that an Olympiad in programming and sports will be held soon. That's why Berland State University should choose two teams: one to take part in the programming track and one to take part in the sports track.

There should be exactly p students in the programming team and exactly s students in the sports team. A student can't be a member of both teams.

The university management considers that the strength of the university on the Olympiad is equal to the sum of two values: the programming team strength and the sports team strength. The strength of a team is the sum of skills of its members in the corresponding area, so the strength of the programming team is the sum of all ai and the strength of the sports team is the sum of all bi over corresponding team members.

Help Berland State University to compose two teams to maximize the total strength of the university on the Olympiad.

Input

The first line contains three positive integer numbers n, p and s (2 ≤ n ≤ 3000, p + s ≤ n) — the number of students, the size of the programming team and the size of the sports team.

The second line contains n positive integers a1, a2, ..., an (1 ≤ ai ≤ 3000), where ai is the programming skill of the i-th student.

The third line contains n positive integers b1, b2, ..., bn (1 ≤ bi ≤ 3000), where bi is the sports skill of the i-th student.

Output

In the first line, print the the maximum strength of the university on the Olympiad. In the second line, print p numbers — the members of the programming team. In the third line, print s numbers — the members of the sports team.

The students are numbered from 1 to n as they are given in the input. All numbers printed in the second and in the third lines should be distinct and can be printed in arbitrary order.

If there are multiple solutions, print any of them.

Examples

Input

5 2 2
1 3 4 5 2
5 3 2 1 4


Output

18
3 4 
1 5 


Input

4 2 2
10 8 8 3
10 7 9 4


Output

31
1 2 
3 4 


Input

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


Output

23
1 3 5 
4 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two convex polygons $A$ and $B$. It is guaranteed that $B$ is strictly contained inside of $A$.

You would like to make a sequence of cuts to cut out $B$ from $A$. To do this, you draw a straight line completely through $A$ that is incident to one of the edges of $B$, which separates $A$ into two pieces. You cut along this line and discard the piece that doesn’t contain $B$. You repeat this until the piece that you have left is exactly B.

The cost of making a cut is equal to the length of the cut (i.e. the length of the line through the remainder of $A$). Given $A$ and $B$, find the minimum cost needed to cut $B$ out.

-----Input-----
Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. Each test case will begin with a line containing a single integer $a$ ($3 \le a \le 200$), which is the number of points in polygon $A$. Each of the next $a$ lines will contain two integers $x$ and $y$ ($-10^6 \le x,y \le 10^6$), which are the vertices of polygon $A$, in clockwise order. It is guaranteed that polygon $A$ will be convex.

The next line will contain a single integer $b$ ($3 \le b \le 200$), which is the number of points in polygon $B$. Each of the next $b$ lines will contain two integers $x$ and $y$ ($-10^6 < x,y < 10^6$), which are the vertices of polygon $B$, in clockwise order. It is guaranteed that polygon $B$ will be convex. It is also guaranteed that polygon $B$ will reside entirely within the interior of polygon $A$.

No three points, within a polygon or across polygons, will be collinear.

-----Output-----
Output a single floating point number, which is the minimum cost to cut $B$ out of $A$. To be considered correct, this number must be within a relative error of $10^{-6}$ of the judges’ answer.

-----Examples-----
Sample Input:
4
0 0
0 14
15 14
15 0
4
8 3
4 6
7 10
11 7
Sample Output:
40.0000000000

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Two integers *x* and *y* are compatible, if the result of their bitwise "AND" equals zero, that is, *a* &amp; *b*<==<=0. For example, numbers 90 (10110102) and 36 (1001002) are compatible, as 10110102 &amp; 1001002<==<=02, and numbers 3 (112) and 6 (1102) are not compatible, as 112 &amp; 1102<==<=102.

You are given an array of integers *a*1,<=*a*2,<=...,<=*a**n*. Your task is to find the following for each array element: is this element compatible with some other element from the given array? If the answer to this question is positive, then you also should find any suitable element.

Input Specification:
The first line contains an integer *n* (1<=≤<=*n*<=≤<=106) — the number of elements in the given array. The second line contains *n* space-separated integers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=4·106) — the elements of the given array. The numbers in the array can coincide.

Output Specification:
Print *n* integers *ans**i*. If *a**i* isn't compatible with any other element of the given array *a*1,<=*a*2,<=...,<=*a**n*, then *ans**i* should be equal to -1. Otherwise *ans**i* is any such number, that *a**i* &amp; *ans**i*<==<=0, and also *ans**i* occurs in the array *a*1,<=*a*2,<=...,<=*a**n*.

Demo Input:
['2\n90 36\n', '4\n3 6 3 6\n', '5\n10 6 9 8 2\n']

Demo Output:
['36 90', '-1 -1 -1 -1', '-1 8 2 2 8']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given three arrays of integers, return the sum of elements that are common in all three arrays.

For example: 

```
common([1,2,3],[5,3,2],[7,3,2]) = 5 because 2 & 3 are common in all 3 arrays
common([1,2,2,3],[5,3,2,2],[7,3,2,2]) = 7 because 2,2 & 3 are common in the 3 arrays
```

More examples in the test cases. 

Good luck!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The NumPy module also comes with a number of built-in routines for linear algebra calculations. These can be found in the sub-module linalg.  

linalg.det

The linalg.det tool computes the determinant of an array.  

print numpy.linalg.det([[1 , 2], [2, 1]])       #Output : -3.0

linalg.eig

The linalg.eig computes the eigenvalues and right eigenvectors of a square array.    

vals, vecs = numpy.linalg.eig([[1 , 2], [2, 1]])
print vals                                      #Output : [ 3. -1.]
print vecs                                      #Output : [[ 0.70710678 -0.70710678]
                                                #          [ 0.70710678  0.70710678]]

linalg.inv  

The linalg.inv tool computes the (multiplicative) inverse of a matrix.

print numpy.linalg.inv([[1 , 2], [2, 1]])       #Output : [[-0.33333333  0.66666667]
                                                #          [ 0.66666667 -0.33333333]]

Other routines can be found here

Task

You are given a square matrix $\mbox{A}$ with dimensions $N$X$N$. Your task is to find the determinant. Note: Round the answer to 2 places after the decimal.

Input Format

The first line contains the integer $N$. 

The next $N$ lines contains the $N$ space separated elements of array $\mbox{A}$. 

Output Format

Print the determinant of $\mbox{A}$.

Sample Input
2
1.1 1.1
1.1 1.1

Sample Output
0.0

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