vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Fox Ciel is participating in a party in Prime Kingdom. There are n foxes there (include Fox Ciel). The i-th fox is ai years old.

They will have dinner around some round tables. You want to distribute foxes such that:

  1. Each fox is sitting at some table. 
  2. Each table has at least 3 foxes sitting around it. 
  3. The sum of ages of any two adjacent foxes around each table should be a prime number. 



If k foxes f1, f2, ..., fk are sitting around table in clockwise order, then for 1 ≤ i ≤ k - 1: fi and fi + 1 are adjacent, and f1 and fk are also adjacent.

If it is possible to distribute the foxes in the desired manner, find out a way to do that.

Input

The first line contains single integer n (3 ≤ n ≤ 200): the number of foxes in this party. 

The second line contains n integers ai (2 ≤ ai ≤ 104).

Output

If it is impossible to do this, output "Impossible".

Otherwise, in the first line output an integer m (<image>): the number of tables.

Then output m lines, each line should start with an integer k -=– the number of foxes around that table, and then k numbers — indices of fox sitting around that table in clockwise order.

If there are several possible arrangements, output any of them.

Examples

Input

4
3 4 8 9


Output

1
4 1 2 4 3


Input

5
2 2 2 2 2


Output

Impossible


Input

12
2 3 4 5 6 7 8 9 10 11 12 13


Output

1
12 1 2 3 6 5 12 9 8 7 10 11 4


Input

24
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25


Output

3
6 1 2 3 6 5 4
10 7 8 9 12 15 14 13 16 11 10
8 17 18 23 22 19 20 21 24

Note

In example 1, they can sit around one table, their ages are: 3-8-9-4, adjacent sums are: 11, 17, 13 and 7, all those integers are primes.

In example 2, it is not possible: the sum of 2+2 = 4 is not a prime number.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Vasya and Petya's Game

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Vasya and Petya are playing a simple game. Vasya thought of number *x* between 1 and *n*, and Petya tries to guess the number.

Petya can ask questions like: "Is the unknown number divisible by number *y*?".

The game is played by the following rules: first Petya asks all the questions that interest him (also, he can ask no questions), and then Vasya responds to each question with a 'yes' or a 'no'. After receiving all the answers Petya should determine the number that Vasya thought of.

Unfortunately, Petya is not familiar with the number theory. Help him find the minimum number of questions he should ask to make a guaranteed guess of Vasya's number, and the numbers *y**i*, he should ask the questions about.

Input Specification:
A single line contains number *n* (1<=≤<=*n*<=≤<=103).

Output Specification:
Print the length of the sequence of questions *k* (0<=≤<=*k*<=≤<=*n*), followed by *k* numbers — the questions *y**i* (1<=≤<=*y**i*<=≤<=*n*).

If there are several correct sequences of questions of the minimum length, you are allowed to print any of them.

Demo Input:
['4\n', '6\n']

Demo Output:
['3\n2 4 3 \n', '4\n2 4 3 5 \n']

Note:
The sequence from the answer to the first sample test is actually correct.

If the unknown number is not divisible by one of the sequence numbers, it is equal to 1.

If the unknown number is divisible by 4, it is 4.

If the unknown number is divisible by 3, then the unknown number is 3.

Otherwise, it is equal to 2. Therefore, the sequence of questions allows you to guess the unknown number. It can be shown that there is no correct sequence of questions of length 2 or shorter.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a random string consisting of numbers, letters, symbols, you need to sum up the numbers in the string. 

Note:

- Consecutive integers should be treated as a single number. eg, `2015` should be treated as a single number `2015`, NOT four numbers
- All the numbers should be treaded as positive integer. eg, `11-14` should be treated as two numbers `11` and `14`. Same as `3.14`, should be treated as two numbers `3` and `14`
- If no number was given in the string, it should return `0`


Example:

```
str = "In 2015, I want to know how much does iPhone 6+ cost?"
```

 The numbers are `2015`, `6`

Sum is `2021`.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There was once young lass called Mary,  

Whose jokes were occasionally scary.  

On this April's Fool  

Fixed limerick rules  

Allowed her to trip the unwary.



Can she fill all the lines

To work at all times?

On juggling the words

Right around two-thirds

She nearly ran out of rhymes.




-----Input-----

The input contains a single integer $a$ ($4 \le a \le 998$). Not every integer in the range is a valid input for the problem; you are guaranteed that the input will be a valid integer.


-----Output-----

Output a single number.


-----Examples-----
Input
35

Output
57

Input
57

Output
319

Input
391

Output
1723

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The finalists of the "Russian Code Cup" competition in 2214 will be the participants who win in one of the elimination rounds.

The elimination rounds are divided into main and additional. Each of the main elimination rounds consists of c problems, the winners of the round are the first n people in the rating list. Each of the additional elimination rounds consists of d problems. The winner of the additional round is one person. Besides, k winners of the past finals are invited to the finals without elimination.

As a result of all elimination rounds at least n·m people should go to the finals. You need to organize elimination rounds in such a way, that at least n·m people go to the finals, and the total amount of used problems in all rounds is as small as possible.


-----Input-----

The first line contains two integers c and d (1 ≤ c, d ≤ 100) — the number of problems in the main and additional rounds, correspondingly. The second line contains two integers n and m (1 ≤ n, m ≤ 100). Finally, the third line contains an integer k (1 ≤ k ≤ 100) — the number of the pre-chosen winners. 


-----Output-----

In the first line, print a single integer — the minimum number of problems the jury needs to prepare.


-----Examples-----
Input
1 10
7 2
1

Output
2

Input
2 2
2 1
2

Output
0

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. You need to print elements of A in alternate order (starting from index 0).
Example 1:
Input:
N = 4
A[] = {1, 2, 3, 4}
Output:
1 3
Example 2:
Input:
N = 5
A[] = {1, 2, 3, 4, 5}
Output:
1 3 5
Your Task:
Since this is a function problem, you just need to complete the provided function print() which takes A and n as input parameters and print the resultant array in the function itself. You have to print the final number of array ending with a space as Printing of newline character is taken care in driver code itself.
Constraints:
1 <= N <= 10^{5}
1 <= A_{i }<= 10^{5}
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Five-In-a-Row

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Alice and Bob play 5-in-a-row game. They have a playing field of size 10<=×<=10. In turns they put either crosses or noughts, one at a time. Alice puts crosses and Bob puts noughts.

In current match they have made some turns and now it's Alice's turn. She wonders if she can put cross in such empty cell that she wins immediately.

Alice wins if some crosses in the field form line of length not smaller than 5. This line can be horizontal, vertical and diagonal.

Input Specification:
You are given matrix 10<=×<=10 (10 lines of 10 characters each) with capital Latin letters 'X' being a cross, letters 'O' being a nought and '.' being an empty cell. The number of 'X' cells is equal to the number of 'O' cells and there is at least one of each type. There is at least one empty cell.

It is guaranteed that in the current arrangement nobody has still won.

Output Specification:
Print 'YES' if it's possible for Alice to win in one turn by putting cross in some empty cell. Otherwise print 'NO'.

Demo Input:
['XX.XX.....\n.....OOOO.\n..........\n..........\n..........\n..........\n..........\n..........\n..........\n..........\n', 'XXOXX.....\nOO.O......\n..........\n..........\n..........\n..........\n..........\n..........\n..........\n..........\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.
Sig has built his own keyboard. Designed for ultimate simplicity, this keyboard only has 3 keys on it: the `0` key, the `1` key and the backspace key.

To begin with, he is using a plain text editor with this keyboard. This editor always displays one string (possibly empty). Just after the editor is launched, this string is empty. When each key on the keyboard is pressed, the following changes occur to the string:

* The `0` key: a letter `0` will be inserted to the right of the string.
* The `1` key: a letter `1` will be inserted to the right of the string.
* The backspace key: if the string is empty, nothing happens. Otherwise, the rightmost letter of the string is deleted.



Sig has launched the editor, and pressed these keys N times in total. As a result, the editor displays a string s. Find the number of such ways to press the keys, modulo 10^9 + 7.

Constraints

* 1 ≦ N ≦ 5000
* 1 ≦ |s| ≦ N
* s consists of the letters `0` and `1`.

Input

The input is given from Standard Input in the following format:


N
s


Output

Print the number of the ways to press the keys N times in total such that the editor displays the string s in the end, modulo 10^9+7.

Examples

Input

3
0


Output

5


Input

300
1100100


Output

519054663


Input

5000
01000001011101000100001101101111011001000110010101110010000


Output

500886057

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Fox Ciel and her friends are in a dancing room. There are *n* boys and *m* girls here, and they never danced before. There will be some songs, during each song, there must be exactly one boy and one girl are dancing. Besides, there is a special rule:
 -  either the boy in the dancing pair must dance for the first time (so, he didn't dance with anyone before); -  or the girl in the dancing pair must dance for the first time. 
Help Fox Ciel to make a schedule that they can dance as many songs as possible.

Input Specification:
The first line contains two integers *n* and *m* (1<=≤<=*n*,<=*m*<=≤<=100) — the number of boys and girls in the dancing room.

Output Specification:
In the first line print *k* — the number of songs during which they can dance. Then in the following *k* lines, print the indexes of boys and girls dancing during songs chronologically. You can assume that the boys are indexed from 1 to *n*, and the girls are indexed from 1 to *m*.

Demo Input:
['2 1\n', '2 2\n']

Demo Output:
['2\n1 1\n2 1\n', '3\n1 1\n1 2\n2 2\n']

Note:
In test case 1, there are 2 boys and 1 girl. We can have 2 dances: the 1st boy and 1st girl (during the first song), the 2nd boy and 1st girl (during the second song).

And in test case 2, we have 2 boys with 2 girls, the answer is 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array $a_1, a_2, \dots, a_n$, consisting of $n$ positive integers. 

Initially you are standing at index $1$ and have a score equal to $a_1$. You can perform two kinds of moves:   move right — go from your current index $x$ to $x+1$ and add $a_{x+1}$ to your score. This move can only be performed if $x<n$.  move left — go from your current index $x$ to $x-1$ and add $a_{x-1}$ to your score. This move can only be performed if $x>1$. Also, you can't perform two or more moves to the left in a row. 

You want to perform exactly $k$ moves. Also, there should be no more than $z$ moves to the left among them.

What is the maximum score you can achieve?


-----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 three integers $n, k$ and $z$ ($2 \le n \le 10^5$, $1 \le k \le n - 1$, $0 \le z \le min(5, k)$) — the number of elements in the array, the total number of moves you should perform and the maximum number of moves to the left you can perform.

The second line of each testcase contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^4$) — the given array.

The sum of $n$ over all testcases does not exceed $3 \cdot 10^5$.


-----Output-----

Print $t$ integers — for each testcase output the maximum score you can achieve if you make exactly $k$ moves in total, no more than $z$ of them are to the left and there are no two or more moves to the left in a row.


-----Example-----
Input
4
5 4 0
1 5 4 3 2
5 4 1
1 5 4 3 2
5 4 4
10 20 30 40 50
10 7 3
4 6 8 2 9 9 7 4 10 9

Output
15
19
150
56



-----Note-----

In the first testcase you are not allowed to move left at all. So you make four moves to the right and obtain the score $a_1 + a_2 + a_3 + a_4 + a_5$.

In the second example you can move one time to the left. So we can follow these moves: right, right, left, right. The score will be $a_1 + a_2 + a_3 + a_2 + a_3$.

In the third example you can move four times to the left but it's not optimal anyway, you can just move four times to the right and obtain the score $a_1 + a_2 + a_3 + a_4 + a_5$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Today a plane was hijacked by a maniac. All the passengers of the flight are taken as hostage. Chef is also one of them.
He invited one of the passengers to play a game with him. If he loses the game, he will release all the passengers, otherwise he will kill all of them. A high risk affair it is.

Chef volunteered for this tough task. He was blindfolded by Hijacker. Hijacker brought a big black bag from his pockets. The contents of the bag is not visible. He tells Chef that the bag contains R red, G green and B blue colored balloons.

Hijacker now asked Chef to take out some balloons from the box such that there are at least K balloons of the same color and hand him over. If the taken out balloons does not contain at least K balloons of the same color, then the hijacker will shoot everybody. Chef is very scared and wants to leave this game as soon as possible, so he will draw the minimum number of balloons so as to save the passengers. Can you please help scared Chef to find out the minimum number of balloons he should take out.

-----Input-----
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. 

The first line of each test case contains a three space-separated integers R, G and B. 

The second line contains only one integer K.

-----Output-----
For each test case, output a single line containing one integer - the minimum number of balloons Chef need to take out from the bag.

-----Constraints-----
- 1 ≤ T ≤ 1000
- 1 ≤ R, G, B ≤ 109
- 1 ≤ K ≤ max{R, G, B}

-----Subtasks-----
- Subtask 1 (44 points): 1 ≤ R, G, B ≤ 10
- Subtask 2 (56 points):  No additional constraints

-----Example-----
Input:
2
3 3 3
1
3 3 3
2

Output:
1
4

-----Explanation-----
Example case 2. In the worst-case scenario first three balloons will be of the three different colors and only after fourth balloon Chef will have two balloons of the same color. So, Chef might need to fetch 4 balloons

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bob recently read about bitwise operations used in computers: AND, OR and XOR. He have studied their properties and invented a new game.

Initially, Bob chooses integer m, bit depth of the game, which means that all numbers in the game will consist of m bits. Then he asks Peter to choose some m-bit number. After that, Bob computes the values of n variables. Each variable is assigned either a constant m-bit number or result of bitwise operation. Operands of the operation may be either variables defined before, or the number, chosen by Peter. After that, Peter's score equals to the sum of all variable values.

Bob wants to know, what number Peter needs to choose to get the minimum possible score, and what number he needs to choose to get the maximum possible score. In both cases, if there are several ways to get the same score, find the minimum number, which he can choose.


-----Input-----

The first line contains two integers n and m, the number of variables and bit depth, respectively (1 ≤ n ≤ 5000; 1 ≤ m ≤ 1000). 

The following n lines contain descriptions of the variables. Each line describes exactly one variable. Description has the following format: name of a new variable, space, sign ":=", space, followed by one of:  Binary number of exactly m bits.  The first operand, space, bitwise operation ("AND", "OR" or "XOR"), space, the second operand. Each operand is either the name of variable defined before or symbol '?', indicating the number chosen by Peter.  

Variable names are strings consisting of lowercase Latin letters with length at most 10. All variable names are different.


-----Output-----

In the first line output the minimum number that should be chosen by Peter, to make the sum of all variable values minimum possible, in the second line output the minimum number that should be chosen by Peter, to make the sum of all variable values maximum possible. Both numbers should be printed as m-bit binary numbers.


-----Examples-----
Input
3 3
a := 101
b := 011
c := ? XOR b

Output
011
100

Input
5 1
a := 1
bb := 0
cx := ? OR a
d := ? XOR ?
e := d AND bb

Output
0
0



-----Note-----

In the first sample if Peter chooses a number 011_2, then a = 101_2, b = 011_2, c = 000_2, the sum of their values is 8. If he chooses the number 100_2, then a = 101_2, b = 011_2, c = 111_2, the sum of their values is 15.

For the second test, the minimum and maximum sum of variables a, bb, cx, d and e is 2, and this sum doesn't depend on the number chosen by Peter, so the minimum Peter can choose is 0.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Anastasia loves going for a walk in Central Uzhlyandian Park. But she became uninterested in simple walking, so she began to collect Uzhlyandian pebbles. At first, she decided to collect all the pebbles she could find in the park.

She has only two pockets. She can put at most k pebbles in each pocket at the same time. There are n different pebble types in the park, and there are w_{i} pebbles of the i-th type. Anastasia is very responsible, so she never mixes pebbles of different types in same pocket. However, she can put different kinds of pebbles in different pockets at the same time. Unfortunately, she can't spend all her time collecting pebbles, so she can collect pebbles from the park only once a day.

Help her to find the minimum number of days needed to collect all the pebbles of Uzhlyandian Central Park, taking into consideration that Anastasia can't place pebbles of different types in same pocket.


-----Input-----

The first line contains two integers n and k (1 ≤ n ≤ 10^5, 1 ≤ k ≤ 10^9) — the number of different pebble types and number of pebbles Anastasia can place in one pocket.

The second line contains n integers w_1, w_2, ..., w_{n} (1 ≤ w_{i} ≤ 10^4) — number of pebbles of each type. 


-----Output-----

The only line of output contains one integer — the minimum number of days Anastasia needs to collect all the pebbles.


-----Examples-----
Input
3 2
2 3 4

Output
3

Input
5 4
3 1 8 9 7

Output
5



-----Note-----

In the first sample case, Anastasia can collect all pebbles of the first type on the first day, of second type — on the second day, and of third type — on the third day.

Optimal sequence of actions in the second sample case:   In the first day Anastasia collects 8 pebbles of the third type.  In the second day she collects 8 pebbles of the fourth type.  In the third day she collects 3 pebbles of the first type and 1 pebble of the fourth type.  In the fourth day she collects 7 pebbles of the fifth type.  In the fifth day she collects 1 pebble of the second type.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a positive integer N, write a function to find if it is a power of three or not.
 
Example 1:
Input:
N = 3
Output:
Yes
Explanation:
3^{1} is a power of 3.
 
Example 2:
Input:
N = 5
Output:
No
Explanation:
5 is not a power of 3.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function isPowerof3() which takes an integer N and returns "Yes" if N is a power of 3, else "No" if N is not a power of 3.
 
Expected Time Complexity: O(1)
Expected Auxiliary Space: O(1)
 
Constraints:
1<=N<=(32-bit largest integer)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The odd and even numbers are fighting against each other!

You are given a list of positive integers. The odd numbers from the list will fight using their `1` bits from their binary representation, while the even numbers will fight using their `0` bits. If present in the list, number `0` will be neutral, hence not fight for either side.

You should return:

* `odds win` if number of `1`s from odd numbers is larger than `0`s from even numbers
* `evens win` if number of `1`s from odd numbers is smaller than `0`s from even numbers
* `tie` if equal, including if list is empty

Please note that any prefix that might appear in the binary representation, e.g. `0b`, should not be counted towards the battle.

### Example:
For an input list of `[5, 3, 14]`:

* odds: `5` and `3` => `101` and `11` => four `1`s
* evens: `14` => `1110` => one `0`

Result: `odds win` the battle with 4-1

If you enjoyed this kata, you can find a nice variation of it [here](https://www.codewars.com/kata/world-bits-war).

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