vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
You are given two strings $s$, and $t$. Count the number of substrings of $s$ that contain $t$ as a subsequence at least once.

Note that a $substring$ and a $subsequence$ both consist of characters from the original string, in order. In a $substring$, the characters must be contiguous in the original string, but in a $subsequence$, they are not required to be contiguous. In the string abcde, ace is a subsequence but not a substring.

If $s$ is aa and $t$ is a, then the answer is $3$: [a]a, [aa], and a[a].

-----Input-----
Each test case will consist of exactly two lines.

The first line will contain string $s$ ($1\! \le \! |s|\! \le \! 10^5, s\! \in \! [a{-}z]^*$), with no other characters.

The second line will contain string $t$ ($1\! \le \! |t|\! \le \! 100, |t|\! \le \! |s|, t\! \in \! [a{-}z]^*$), with no other characters.

-----Output-----
Output a single integer, which is the number of substrings of $s$ that contain $t$ as a subsequence at least once.

-----Examples-----
Sample Input 1:
abcdefghijklmnopqrstuvwxyz
a
Sample Output 1:
26

Sample Input 2:
abcdefghijklmnopqrstuvwxyz
m
Sample Output 2:
182

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Production Manager of a dance company has been tasked with determining the cost for the seasonal dance recital. Because of their exceptional skills, many dancers will perform in more than one routine, but this presents a problem; each dance routine incorporates a unique costume, so between routines, dancers must report backstage to a Wardrobe Specialist, who can change the dancer’s costume in time to begin their next scheduled routine.

A Wardrobe Specialist does a normal change on a dancer when the dancer performs in two routines that are not consecutive, but when a dancer is required to perform in two consecutive routines, a quick change is necessary. A Wardrobe Specialist charges a flat rate per recital that covers all normal changes, but charges an exorbitant amount for each quick change. The Production Manager is responsible for keeping the show under budget, and has hired you to write a program to report the minimum number of quick changes needed for a given recital, given that the order of the dance routines could be changed.

To describe the cast of dancers that are to perform during a recital, each dancer is assigned an identifying uppercase letter. (Fortunately, there are never more than 26 dancers, so characters from A to Z suffice.) To describe a full recital, a list of individual routines is given, with a string of characters defining which dancers appear in a routine. For example, consider the following recital description:

    ABC ABEF DEF ABCDE FGH

The above list describes a recital with 5 dance routines, including a total of 8 individual performers (dancers A through H). The first routine listed includes dancers {A, B, and C}. The second routine includes dancers {A, B, E, and F}. Notice that if these first two routines are performed in the above order, dancers A and B will require a quick change between the routines. In fact, if these five routines are scheduled in the order given above, a total of six quick changes are required. However, the schedule can be rearranged as follows:

    ABEF DEF ABC FGH ABCDE

In this case, only two quick changes are required (those for E and F between the first two dances).

-----Input-----
The first line contains a single integer $R$, with $2 \leq R \leq 10$, that indicates the number of routines in the recital. Following that will be $R$ additional lines, each describing the dancers for one routine in the form of a nonempty string of up to 26 non-repeating, lexicographically sorted uppercase alphabetic characters identifying the dancers who perform in that routine. Although a dancer’s letter will not appear more than once in a single routine, that dancer may appear in many different routines, and it may be that two or more routines have the identical set of dancers.

-----Output-----
Output a single integer designating the minimum number of quick changes required for the recital.

-----Examples-----
Sample Input 1:
5
ABC
ABEF
DEF
ABCDE
FGH
Sample Output 1:
2

Sample Input 2:
6
BDE
FGH
DEF
ABC
BDE
ABEF
Sample Output 2:
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mahmoud and Ehab are in the fourth stage now.

Dr. Evil has a hidden binary string of length n. He guarantees that there is at least one '0' symbol and at least one '1' symbol in it. Now he wants Mahmoud and Ehab to find a position of any '0' symbol and any '1' symbol. In order to do this, Mahmoud and Ehab can ask Dr. Evil up to 15 questions. They tell Dr. Evil some binary string of length n, and Dr. Evil tells the Hamming distance between these two strings. Hamming distance between 2 binary strings of the same length is the number of positions in which they have different symbols. You can find the definition of Hamming distance in the notes section below.

Help Mahmoud and Ehab find these two positions.

You will get Wrong Answer verdict if 

  * Your queries doesn't satisfy interaction protocol described below. 
  * You ask strictly more than 15 questions and your program terminated after exceeding queries limit. Please note, that you can do up to 15 ask queries and one answer query. 
  * Your final answer is not correct. 

You will get Idleness Limit Exceeded if you don't print anything or if you forget to flush the output, including for the final answer (more info about flushing output below).

If you exceed the maximum number of queries, You should terminate with 0, In this case you'll get Wrong Answer, If you don't terminate you may receive any verdict because you'll be reading from a closed stream .

Input

The first line of input will contain a single integer n (2 ≤ n ≤ 1000) — the length of the hidden binary string.

Output

To print the final answer, print "! pos0 pos1" (without quotes), where pos0 and pos1 are positions of some '0' and some '1' in the string (the string is 1-indexed). Don't forget to flush the output after printing the answer!

Interaction

To ask a question use the format "? s" (without quotes), where s is a query string. Don't forget to flush the output after printing a query!

After each query you can read a single integer from standard input — the Hamming distance between the hidden string and the query string.

To flush the output you can use:- 

  * fflush(stdout) in C++; 
  * System.out.flush() in Java; 
  * stdout.flush() in Python; 
  * flush(output) in Pascal; 
  * See the documentation for other languages . 



Hacking.

To hack someone just print one binary string with length up to 1000, containing at least one '0' and at least one '1'.

Example

Input

3
2
1
3
2
1
0

Output

? 000
? 001
? 010
? 011
? 100
? 101
! 2 1

Note

Hamming distance definition: <https://en.wikipedia.org/wiki/Hamming_distance>

In the first test case the hidden binary string is 101, The first query is 000, so the Hamming distance is 2. In the second query the hidden string is still 101 and query is 001, so the Hamming distance is 1.

After some queries you find that symbol at position 2 is '0' and symbol at position 1 is '1', so you print "! 2 1".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given n k-digit integers. You have to rearrange the digits in the integers so that the difference between the largest and the smallest number was minimum. Digits should be rearranged by the same rule in all integers.

Input

The first line contains integers n and k — the number and digit capacity of numbers correspondingly (1 ≤ n, k ≤ 8). Next n lines contain k-digit positive integers. Leading zeroes are allowed both in the initial integers and the integers resulting from the rearranging of digits.

Output

Print a single number: the minimally possible difference between the largest and the smallest number after the digits are rearranged in all integers by the same rule.

Examples

Input

6 4
5237
2753
7523
5723
5327
2537


Output

2700


Input

3 3
010
909
012


Output

3


Input

7 5
50808
36603
37198
44911
29994
42543
50156


Output

20522

Note

In the first sample, if we rearrange the digits in numbers as (3,1,4,2), then the 2-nd and the 4-th numbers will equal 5237 and 2537 correspondingly (they will be maximum and minimum for such order of digits).

In the second sample, if we swap the second digits and the first ones, we get integers 100, 99 and 102.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mahmoud was trying to solve the vertex cover problem on trees. The problem statement is:

Given an undirected tree consisting of n nodes, find the minimum number of vertices that cover all the edges. Formally, we need to find a set of vertices such that for each edge (u, v) that belongs to the tree, either u is in the set, or v is in the set, or both are in the set. Mahmoud has found the following algorithm:

  * Root the tree at node 1. 
  * Count the number of nodes at an even depth. Let it be evenCnt. 
  * Count the number of nodes at an odd depth. Let it be oddCnt. 
  * The answer is the minimum between evenCnt and oddCnt. 



The depth of a node in a tree is the number of edges in the shortest path between this node and the root. The depth of the root is 0.

Ehab told Mahmoud that this algorithm is wrong, but he didn't believe because he had tested his algorithm against many trees and it worked, so Ehab asked you to find 2 trees consisting of n nodes. The algorithm should find an incorrect answer for the first tree and a correct answer for the second one.

Input

The only line contains an integer n (2 ≤ n ≤ 105), the number of nodes in the desired trees.

Output

The output should consist of 2 independent sections, each containing a tree. The algorithm should find an incorrect answer for the tree in the first section and a correct answer for the tree in the second. If a tree doesn't exist for some section, output "-1" (without quotes) for that section only.

If the answer for a section exists, it should contain n - 1 lines, each containing 2 space-separated integers u and v (1 ≤ u, v ≤ n), which means that there's an undirected edge between node u and node v. If the given graph isn't a tree or it doesn't follow the format, you'll receive wrong answer verdict.

If there are multiple answers, you can print any of them.

Examples

Input

2


Output

-1
1 2


Input

8


Output

1 2
1 3
2 4
2 5
3 6
4 7
4 8
1 2
1 3
2 4
2 5
2 6
3 7
6 8

Note

In the first sample, there is only 1 tree with 2 nodes (node 1 connected to node 2). The algorithm will produce a correct answer in it so we printed  - 1 in the first section, but notice that we printed this tree in the second section.

In the second sample:

In the first tree, the algorithm will find an answer with 4 nodes, while there exists an answer with 3 nodes like this: <image> In the second tree, the algorithm will find an answer with 3 nodes which is correct: <image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Katie, Kuro and Shiro are best friends. They have known each other since kindergarten. That's why they often share everything with each other and work together on some very hard problems.

Today is Shiro's birthday. She really loves pizza so she wants to invite her friends to the pizza restaurant near her house to celebrate her birthday, including her best friends Katie and Kuro.

She has ordered a very big round pizza, in order to serve her many friends. Exactly $n$ of Shiro's friends are here. That's why she has to divide the pizza into $n + 1$ slices (Shiro also needs to eat). She wants the slices to be exactly the same size and shape. If not, some of her friends will get mad and go home early, and the party will be over.

Shiro is now hungry. She wants to cut the pizza with minimum of straight cuts. A cut is a straight segment, it might have ends inside or outside the pizza. But she is too lazy to pick up the calculator.

As usual, she will ask Katie and Kuro for help. But they haven't come yet. Could you help Shiro with this problem?


-----Input-----

A single line contains one non-negative integer $n$ ($0 \le n \leq 10^{18}$) — the number of Shiro's friends. The circular pizza has to be sliced into $n + 1$ pieces.


-----Output-----

A single integer — the number of straight cuts Shiro needs.


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

Output
2
Input
4

Output
5


-----Note-----

To cut the round pizza into quarters one has to make two cuts through the center with angle $90^{\circ}$ between them.

To cut the round pizza into five equal parts one has to make five cuts.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
As Sherlock Holmes was investigating another crime, he found a certain number of clues. Also, he has already found direct links between some of those clues. The direct links between the clues are mutual. That is, the direct link between clues *A* and *B* and the direct link between clues *B* and *A* is the same thing. No more than one direct link can exist between two clues.

Of course Sherlock is able to find direct links between all clues. But it will take too much time and the criminals can use this extra time to hide. To solve the crime, Sherlock needs each clue to be linked to all other clues (maybe not directly, via some other clues). Clues *A* and *B* are considered linked either if there is a direct link between them or if there is a direct link between *A* and some other clue *C* which is linked to *B*. 

Sherlock Holmes counted the minimum number of additional direct links that he needs to find to solve the crime. As it turns out, it equals *T*.

Please count the number of different ways to find exactly *T* direct links between the clues so that the crime is solved in the end. Two ways to find direct links are considered different if there exist two clues which have a direct link in one way and do not have a direct link in the other way. 

As the number of different ways can turn out rather big, print it modulo *k*.

Input Specification:
The first line contains three space-separated integers *n*,<=*m*,<=*k* (1<=≤<=*n*<=≤<=105,<=0<=≤<=*m*<=≤<=105, 1<=≤<=*k*<=≤<=109) — the number of clues, the number of direct clue links that Holmes has already found and the divisor for the modulo operation.

Each of next *m* lines contains two integers *a* and *b* (1<=≤<=*a*,<=*b*<=≤<=*n*,<=*a*<=≠<=*b*), that represent a direct link between clues. It is guaranteed that any two clues are linked by no more than one direct link. Note that the direct links between the clues are mutual.

Output Specification:
Print the single number — the answer to the problem modulo *k*.

Demo Input:
['2 0 1000000000\n', '3 0 100\n', '4 1 1000000000\n1 4\n']

Demo Output:
['1\n', '3\n', '8\n']

Note:
The first sample only has two clues and Sherlock hasn't found any direct link between them yet. The only way to solve the crime is to find the link.

The second sample has three clues and Sherlock hasn't found any direct links between them. He has to find two of three possible direct links between clues to solve the crime — there are 3 ways to do it.

The third sample has four clues and the detective has already found one direct link between the first and the fourth clue. There are 8 ways to find two remaining clues to solve the crime.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
A magic island Geraldion, where Gerald lives, has its own currency system. It uses banknotes of several values. But the problem is, the system is not perfect and sometimes it happens that Geraldionians cannot express a certain sum of money with any set of banknotes. Of course, they can use any number of banknotes of each value. Such sum is called unfortunate. Gerald wondered: what is the minimum unfortunate sum?

Input Specification:
The first line contains number *n* (1<=≤<=*n*<=≤<=1000) — the number of values of the banknotes that used in Geraldion. 

The second line contains *n* distinct space-separated numbers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=106) — the values of the banknotes.

Output Specification:
Print a single line — the minimum unfortunate sum. If there are no unfortunate sums, print <=-<=1.

Demo Input:
['5\n1 2 3 4 5\n']

Demo Output:
['-1\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Return the number of permutations of 1 to n so that prime numbers are at prime indices (1-indexed.)
(Recall that an integer is prime if and only if it is greater than 1, and cannot be written as a product of two positive integers both smaller than it.)
Since the answer may be large, return the answer modulo 10^9 + 7.
 
Example 1:
Input: n = 5
Output: 12
Explanation: For example [1,2,5,4,3] is a valid permutation, but [5,2,3,4,1] is not because the prime number 5 is at index 1.

Example 2:
Input: n = 100
Output: 682289015

 
Constraints:

1 <= n <= 100

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
> When no more interesting kata can be resolved, I just choose to create the new kata, to solve their own, to enjoy the process  --myjinxin2015 said

# Description:

In this Kata, we have to try to create a mysterious pattern.

Given a positive integer `m`, you can generate a Fibonacci sequence with a length of `m`:
```
1 1 2 3 5 8 13 21 34 ...
```

Given a positive integer `n`, you need to execute `%` operation on each element of the Fibonacci sequence:
 
```
m = 9, n = 3
Fibonacci sequence: 1 1 2 3 5 8 13 21 34
               ---> 1%3 1%3 2%3 3%3 5%3 8%3 13%3 21%3 34%3
               --->  1   1   2   0   2   2    1    0    1
```
Finally, make `n` rows string to show the pattern:

```
112022101
|||||||||
   o   o
oo    o o
  o oo
```

Please note:
* Each row is separated by `"\n"`;
* You should trim the end of each row;
* If there are some empty rows at the start or end of string, you should trim them too. But, if the empty row is in the middle(see the last example), you should not trim it.



# Examples:


For m = 5, n = 5, the output should be:
```
    o 
oo
  o
   o
```
For m = 12, n = 4, the output should be:
```
     o     o
oo  o oo  o
  o     o
   o     o
```
For m = 1, n = 1, the output should be:`"o"`

For: m = 6, n = 15, the output should be:
```
oo
  o
   o

    o


     o
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This is a fact for almost all the students out there that Mathematics subject is a very fearful subject for them.

And no wonder this fact is also true for our friend Primo. But to challenge his fear he went to the Mathe-Matica Town for his summer vacations.

In Mathe-Matica town every person is assigned a Friend Score.

A Friendship Score is an integer value such that 

(i) It is unique and 

(ii) It can not be equal to Friend Score when other Friend Scores are multiplied with each-other

Now our Primo can not enjoy his vacations alone. So he asked help from the Mathe-Matica town Mayor. The Mayor gave him a Friendship Score and told him that he can be friend with two persons of town only and only if the addition of those two persons' Friend Score is equal to the Friendship Score.

Primo is not good in Mathematics so he wants your help to find out his friends in town.

Input : First line of Input contains the Number of Test Cases T .  Next T lines contain a single Integer N. N denotes the Friendship Score

Output : Output Friend Score of his friends in town. If he can not have any friend then print -1 -1 Produce output for each Test Case in a new line.

Note : Output should be in Increasing Order of Friend Scores

Constrains

1 ≤ T ≤50

2 ≤ N ≤ 10^6

Note :- To be Eligible for Prizes you have to register and create your home address maptag.

Click here to create your Maptag

SAMPLE INPUT
3
10
100
1000

SAMPLE OUTPUT
3 7
47 53
491 509

Explanation

Case 1: Friendship Score (= 10) is equal to Friend Score ( 3 + 7)

Case 2: Friendship Score (= 100) is equal to Friend Score ( 47 + 53)

Case 3: Friendship Score (= 1000) is equal to Friend Score ( 491 + 509)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Michael works in a bakery. At the end of his shift, his boss wants the breads sorted in a certain order. She can’t seem to decide on which order, though – every day there seems to be a new one – to Michael’s despair. Michael has worked there for a while now and has learned a neat trick with his wooden bakery paddle. He can take three breads next to each other on his paddle and throw them up in the air such that when they land, the right-most has moved to the left-most position, and the two other breads have moved one place to the right. In other words, he can rotate to the right a subsequence of breads of length three.

Before the end of the shift, his coworkers place the breads in a long line. Michael would like to sort the line of breads using his paddle trick. He can take any three consecutive breads along the line on his paddle, rotate them, and then put them back. Sometimes though, it does not matter how many times he uses his paddle – the line of bread just doesn’t seem to be possible to sort the way the boss wants…

-----Input-----
The first line of input contains a positive integer $N, (3 \leq N \leq 100000)$, denoting the number of breads. Then two lines follow: On the first line, a permutation of the integers $1$ through $N$ describing the order in which the breads are lined up. On the second line, a permutation of the integers $1$ through $N$ describing how Michael’s boss wants the breads sorted.

-----Output-----
Output “Possible” if Michael can sort the breads with his paddle in the order prescribed by his boss, otherwise “Impossible”.

-----Examples-----
Sample Input:
4
1 3 4 2
4 3 2 1
Sample Output:
Possible

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