vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Marina loves strings of the same length and Vasya loves when there is a third string, different from them in exactly t characters. Help Vasya find at least one such string.

More formally, you are given two strings s1, s2 of length n and number t. Let's denote as f(a, b) the number of characters in which strings a and b are different. Then your task will be to find any string s3 of length n, such that f(s1, s3) = f(s2, s3) = t. If there is no such string, print  - 1.

Input

The first line contains two integers n and t (1 ≤ n ≤ 105, 0 ≤ t ≤ n).

The second line contains string s1 of length n, consisting of lowercase English letters.

The third line contain string s2 of length n, consisting of lowercase English letters.

Output

Print a string of length n, differing from string s1 and from s2 in exactly t characters. Your string should consist only from lowercase English letters. If such string doesn't exist, print -1.

Examples

Input

3 2
abc
xyc


Output

ayd

Input

1 0
c
b


Output

-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ramu was a lazy farmer. He had inherited a fairly large farm and a nice house from his father. Ramu leased out the farm land to others and earned a rather handsome income. His father used to keep a buffalo at home and sell its milk but the buffalo died a few days after his father did.
Ramu too wanted to make some money from buffaloes, but in a quite a different way. He decided that his future lay in speculating on buffaloes. In the market in his village, buffaloes were bought and sold everyday. The price fluctuated over the year, but on any single day the price was always the same.
He decided that he would buy buffaloes when the price was low and sell them when the price was high and, in the process, accummulate great wealth. Unfortunately his house had space for just one buffalo and so he could own at most one buffalo at any time.
Before he entered the buffalo market, he decided to examine to examine the variation in the price of buffaloes over the last few days and determine the maximum profit he could have made. Suppose, the price of a buffalo over the last $10$ days varied as
1012811111012151310101281111101215131010\quad  12\quad  8\quad  11\quad  11\quad  10\quad  12\quad  15\quad  13\quad  10
Ramu is a lazy fellow and he reckoned that he would have been willing to visit the market at most $5$ times (each time to either buy or sell a buffalo) over the last $10$ days. Given this, the maximum profit he could have made is $9$ rupees. To achieve this, he buys a buffalo on day $1$, sells it on day $2$, buys one more on day $3$ and sells it on day $8$. If he was a little less lazy and was willing to visit the market $6$ times, then he could have made more money. He could have bought on day $1$, sold on day $2$, bought on day $3$, sold on day $4$, bought on day $6$ and sold on day $8$ to make a profit of $10$ rupees.
Your task is help Ramu calculate the maximum amount he can earn by speculating on buffaloes, given a history of daily buffalo prices over a period and a limit on how many times Ramu is willing to go to the market during this period.

-----Input:-----
- The first line of the input contains two integers $N$ and $K$, where $N$ is the number of days for which the price data is available and $K$ is the maximum number of times that Ramu is willing to visit the cattle market. 
- The next $N$ lines (line $2, 3,...,N+1$) contain a single positive integer each. The integer on line $i+1$, $1 \leq i \leq N$, indicates the price of a buffalo on day $i$.

-----Output:-----
A single nonnegative integer indicating that maximum amount of profit that Ramu can make if he were to make at most $K$ trips to the market.

-----Constraints:-----
- $1 \leq N \leq 400$.
- $1 \leq K \leq 400$.
- $0 \leq$ price of a buffalo on any day $\leq 1000$

-----Sample Input 1:-----
10 5
10
12
8
11
11
10
12
15
13
10

-----Sample Output 1:-----
9

-----Sample Input 2:-----
10 6
10
12
8
11
11
10
12
15
13
10

-----Sample Output 2:-----
10

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write a program that reads the coordinates of the vertices of a convex n-sided polygon (a polygon whose internal angles are less than 180 degrees, that is, a polygon that is not dented) and outputs its area. The vertices are named Vertex 1, Vertex 2, Vertex 3, ... Vertex n according to the order of edge connections.

However, n is 3 or more and 20 or less. You can also use the following formula to find the area S from the lengths a, b, and c of the three sides of the triangle.

<image>



input

The input is given in the following format:


x1, y1
x2, y2
::
xn, yn


xi and yi are real numbers that represent the x and y coordinates of vertex i, respectively.

output

Outputs the area S (real number) on one line. The output can contain an error of 0.000001 or less.

Example

Input

0.0,0.0
0.0,1.0
1.0,1.0
2.0,0.0
1.0,-1.0


Output

2.500000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef gives an array A with N elements to Babla. Babla's task is to find the maximum non-negative integer X such that:

No element in the array belongs to the range [-X, X]. In other words, for all (1≤ i ≤ N), either A_{i} < -X or A_{i} > X.

Help Babla to find the maximum non-negative integer X for which the given condition is satisfied or determine if no such X exists.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains an integer N — the number of elements in the array.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \ldots, A_{N} representing the array A.

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

For each test case, output on a new line, the maximum non-negative integer X, satisfying the above condition.  
If no such X exists, output -1 instead.

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

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

----- Sample Input 1 ------ 
3
5
8 4 2 5 2
6
7 9 -10 8 12 17
4
0 -3 -1 -10

----- Sample Output 1 ------ 
1
6
-1

----- explanation 1 ------ 
Test case $1$: The maximum value of $X$ such that no element of the array belongs to the range $[-X, X]$ is $1$. All elements of the array are strictly greater than $1$.

Test case $2$: The maximum value of $X$ such that no element of the array belongs to the range $[-X, X]$ is $6$. All positive elements of the array are strictly greater than $6$ and negative elements are strictly less than $-6$.

Test case $3$: It is not possible to choose an element $X$ that satisfies the given condition.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
As you very well know, the whole Universe traditionally uses three-dimensional Cartesian system of coordinates. In this system each point corresponds to three real coordinates (x, y, z). In this coordinate system, the distance between the center of the Universe and the point is calculated by the following formula: <image>. Mushroom scientists that work for the Great Mushroom King think that the Universe isn't exactly right and the distance from the center of the Universe to a point equals xa·yb·zc.

To test the metric of mushroom scientists, the usual scientists offered them a task: find such x, y, z (0 ≤ x, y, z; x + y + z ≤ S), that the distance between the center of the Universe and the point (x, y, z) is maximum possible in the metric of mushroom scientists. The mushroom scientists aren't good at maths, so they commissioned you to do the task.

Note that in this problem, it is considered that 00 = 1.

Input

The first line contains a single integer S (1 ≤ S ≤ 103) — the maximum sum of coordinates of the sought point.

The second line contains three space-separated integers a, b, c (0 ≤ a, b, c ≤ 103) — the numbers that describe the metric of mushroom scientists.

Output

Print three real numbers — the coordinates of the point that reaches maximum value in the metrics of mushroom scientists. If there are multiple answers, print any of them that meets the limitations.

A natural logarithm of distance from the center of the Universe to the given point in the metric of mushroom scientists shouldn't differ from the natural logarithm of the maximum distance by more than 10 - 6. We think that ln(0) = - ∞.

Examples

Input

3
1 1 1


Output

1.0 1.0 1.0


Input

3
2 0 0


Output

3.0 0.0 0.0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef Vivek is good in mathematics and likes solving problems on prime numbers. One day his friend Jatin told him about Victory numbers. Victory number can be defined as a number formed after summing up all the prime numbers till given number n. Now, chef Vivek who is very fond of solving questions on prime numbers got busy in some other tasks. Your task is to help him finding victory number.

-----Input:-----
- First line will contain $T$, number of test cases. Then the test cases follow. 
- Each test case contains of a single line of input $N$ till which sum of all prime numbers between 1 to n has to be calculated.

-----Output:-----
For each test case, output in a single line answer to the victory number.

-----Constraints-----
- $1 <= T <= 1000$
- $1 <= N <= 10^6$

-----Sample Input:-----
3
22
13
10

-----Sample Output:-----
77
41
17

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Companies always have a lot of equipment, furniture and other things. All of them should be tracked. To do this, there is an inventory number assigned with each item. It is much easier to create a database by using those numbers and keep the track of everything.

During an audit, you were surprised to find out that the items are not numbered sequentially, and some items even share the same inventory number! There is an urgent need to fix it. You have chosen to make the numbers of the items sequential, starting with 1. Changing a number is quite a time-consuming process, and you would like to make maximum use of the current numbering.

You have been given information on current inventory numbers for n items in the company. Renumber items so that their inventory numbers form a permutation of numbers from 1 to n by changing the number of as few items as possible. Let us remind you that a set of n numbers forms a permutation if all the numbers are in the range from 1 to n, and no two numbers are equal.


-----Input-----

The first line contains a single integer n — the number of items (1 ≤ n ≤ 10^5).

The second line contains n numbers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^5) — the initial inventory numbers of the items.


-----Output-----

Print n numbers — the final inventory numbers of the items in the order they occur in the input. If there are multiple possible answers, you may print any of them.


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

Output
1 3 2 

Input
4
2 2 3 3

Output
2 1 3 4 

Input
1
2

Output
1 



-----Note-----

In the first test the numeration is already a permutation, so there is no need to change anything.

In the second test there are two pairs of equal numbers, in each pair you need to replace one number.

In the third test you need to replace 2 by 1, as the numbering should start from one.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In the X-ray lab at KTH some experiments require evacuated tubes between source and sample and between sample and detector so that the X-rays are not absorbed by the air. Since the positions of object and detector vary between different experiments, several tubes of different lengths are available. The tubes should be fixed together in pairs, since they have a vacuum window only in one end. Two such tube pairs should be chosen, one to place between the source and the object and one to place between the object and the detector. This, however, gives a large set of possible lengths and makes it difficult to figure out which tubes to use for an experiment. The length of the tubes used should be as long as possible to minimize air absorption, but there is a limited amount of space between source and object $L_1$ and between object and detector $L_2$. What is the maximum length of air that can be replaced by vacuum tubes in this way? 

-----Task-----
Given a set of tube lengths and the two distances $L_1$ and $L_2$, find four tubes with the total length being as long as possible under the constraint that the sum of the first two tube lengths is at most $L_1$ and the sum of the last two tube lengths is at most $L_2$.

-----Input-----
The first line of input contains three positive integers, $L_1$ and $L_2$, denoting the distances explained above in mm ($1 \leq L_1, L_2 \leq 10000$) and $N$, the number of available tubes ($4 \leq N \leq 2000$). The following $N$ lines each contain a single positive integer less than or equal to $10000$, the length of a tube in mm.

-----Output-----
Output one line containing the maximum total length of air that can be avoided, i.e., the sum of the four tubes chosen. If there are no two pairs of tubes fitting into the setup, output the single word “Impossible” instead.

-----Examples-----
Sample Input:
1000 2000 7
100
480
500
550
1000
1400
1500
Sample Output:
2930

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Guy-Manuel and Thomas have an array $a$ of $n$ integers [$a_1, a_2, \dots, a_n$]. In one step they can add $1$ to any element of the array. Formally, in one step they can choose any integer index $i$ ($1 \le i \le n$) and do $a_i := a_i + 1$.

If either the sum or the product of all elements in the array is equal to zero, Guy-Manuel and Thomas do not mind to do this operation one more time.

What is the minimum number of steps they need to do to make both the sum and the product of all elements in the array different from zero? Formally, find the minimum number of steps to make $a_1 + a_2 +$ $\dots$ $+ a_n \ne 0$ and $a_1 \cdot a_2 \cdot$ $\dots$ $\cdot a_n \ne 0$.


-----Input-----

Each test contains multiple test cases. 

The first line contains the number of test cases $t$ ($1 \le t \le 10^3$). The description of the test cases follows.

The first line of each test case contains an integer $n$ ($1 \le n \le 100$) — the size of the array.

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($-100 \le a_i \le 100$) — elements of the array .


-----Output-----

For each test case, output the minimum number of steps required to make both sum and product of all elements in the array different from zero.


-----Example-----
Input
4
3
2 -1 -1
4
-1 0 0 1
2
-1 2
3
0 -2 1

Output
1
2
0
2



-----Note-----

In the first test case, the sum is $0$. If we add $1$ to the first element, the array will be $[3,-1,-1]$, the sum will be equal to $1$ and the product will be equal to $3$.

In the second test case, both product and sum are $0$. If we add $1$ to the second and the third element, the array will be $[-1,1,1,1]$, the sum will be equal to $2$ and the product will be equal to $-1$. It can be shown that fewer steps can't be enough.

In the third test case, both sum and product are non-zero, we don't need to do anything.

In the fourth test case, after adding $1$ twice to the first element the array will be $[2,-2,1]$, the sum will be $1$ and the product will be $-4$.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The Berland capital is shaken with three bold crimes committed by the Pihsters, a notorious criminal gang.

The Berland capital's map is represented by an *n*<=×<=*m* rectangular table. Each cell of the table on the map represents some districts of the capital. 

The capital's main detective Polycarpus took a map and marked there the districts where the first three robberies had been committed as asterisks. Deduction tells Polycarpus that the fourth robbery will be committed in such district, that all four robbed districts will form the vertices of some rectangle, parallel to the sides of the map. 

Polycarpus is good at deduction but he's hopeless at math. So he asked you to find the district where the fourth robbery will be committed.

Input Specification:
The first line contains two space-separated integers *n* and *m* (2<=≤<=*n*,<=*m*<=≤<=100) — the number of rows and columns in the table, correspondingly.

Each of the next *n* lines contains *m* characters — the description of the capital's map. Each character can either be a "." (dot), or an "*" (asterisk). A character equals "*" if the corresponding district has been robbed. Otherwise, it equals ".".

It is guaranteed that the map has exactly three characters "*" and we can always find the fourth district that meets the problem requirements.

Output Specification:
Print two integers — the number of the row and the number of the column of the city district that is the fourth one to be robbed. The rows are numbered starting from one from top to bottom and the columns are numbered starting from one from left to right.

Demo Input:
['3 2\n.*\n..\n**\n', '3 3\n*.*\n*..\n...\n']

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mr. Modulo comes up with another problem related to modulo and this time he is interested in finding all the possible pairs a and b in the array arr[] such that a % b = k where k is a given integer. The array given will have distinct elements.
You are required to print how many such pairs exist.
Example 1:
Input:
N=5, K=3
arr[] = {2, 3, 5, 4, 7}
Output: 4
Explanation:
The pairs are -: 
7 % 4 = 3
3 % 4 = 3
3 % 5 = 3
3 % 7 = 3
 
Example 2:
Input:
N=2, K=3
arr[] = {1, 2} 
Output: 0
 
Your Task:
Since, this is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function printPairs() that takes array arr, integer n and integer k as parameters and return the total number of such pairs in the array.
 
Expected Time Complexity:  O(N* sqrt(max)) where max is the maximum element in the array.
Expected Auxiliary Space: O(N).
 
Constraints:
1 ≤ N ≤ 10^{4}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
If you have gone that far, you'll probably skip unnecessary legends anyway...

You are given a binary string <image> and an integer <image>. Find the number of integers k, 0 ≤ k < N, such that for all i = 0, 1, ..., m - 1

<image> Print the answer modulo 109 + 7.

Input

In the first line of input there is a string s consisting of 0's and 1's (1 ≤ |s| ≤ 40).

In the next line of input there is an integer n (1 ≤ n ≤ 5·105).

Each of the next n lines contains two space-separated integers pi, αi (1 ≤ pi, αi ≤ 109, pi is prime). All pi are distinct.

Output

A single integer — the answer to the problem.

Examples

Input

1
2
2 1
3 1


Output

2


Input

01
2
3 2
5 1


Output

15


Input

1011
1
3 1000000000


Output

411979884

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Piegirl is buying stickers for a project. Stickers come on sheets, and each sheet of stickers contains exactly *n* stickers. Each sticker has exactly one character printed on it, so a sheet of stickers can be described by a string of length *n*. Piegirl wants to create a string *s* using stickers. She may buy as many sheets of stickers as she wants, and may specify any string of length *n* for the sheets, but all the sheets must be identical, so the string is the same for all sheets. Once she attains the sheets of stickers, she will take some of the stickers from the sheets and arrange (in any order) them to form *s*. Determine the minimum number of sheets she has to buy, and provide a string describing a possible sheet of stickers she should buy.

Input Specification:
The first line contains string *s* (1<=≤<=|*s*|<=≤<=1000), consisting of lowercase English characters only. The second line contains an integer *n* (1<=≤<=*n*<=≤<=1000).

Output Specification:
On the first line, print the minimum number of sheets Piegirl has to buy. On the second line, print a string consisting of *n* lower case English characters. This string should describe a sheet of stickers that Piegirl can buy in order to minimize the number of sheets. If Piegirl cannot possibly form the string *s*, print instead a single line with the number -1.

Demo Input:
['banana\n4\n', 'banana\n3\n', 'banana\n2\n']

Demo Output:
['2\nbaan\n', '3\nnab\n', '-1\n']

Note:
In the second example, Piegirl can order 3 sheets of stickers with the characters "nab". She can take characters "nab" from the first sheet, "na" from the second, and "a" from the third, and arrange them to from "banana".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Read problems statements in Mandarin Chinese  and Russian. 

Tanu has got interested in signs and gestures that we use for communication. One such gesture is the head-bob.
When we want to signal "Yes" to someone, we move the head up-and-down. For "No", the head is moved left-and-right, rotating about the vertical axis.
There is a peculiar way of gesturing "Yes", commonly seen in India, by moving head sideways (rotating about the forward-back axis). This is called the  Indian head-bob.Tanu observed many people on the railways station, and made a list of gestures that they made. Usual "Yes" gesture is recorded as "Y", no as "N" and Indian "Yes" gesture as "I". (Assume no foreigner uses the Indian "Yes" gesture and vice-versa). Identify which of them were Indians, which were not Indian, and which one you cannot be sure about.
------ Input ------ 
First line contains T, number of people observed by Tanu.
Each person is described in two lines. First line of the description contains a single integer N, the number of gestures recorded for this person. Next line contains a string of N characters, each character can be "Y", "N" or "I".
------ Output ------ 
For each person, print "INDIAN" if he/she is from India, "NOT INDIAN" if not from India, and "NOT SURE" if the information is insufficient to make a decision.
------ Constraints ------ 
For 30 points: 1 ≤ T,N ≤ 100For 70 points: 1 ≤ T,N ≤ 1000

----- Sample Input 1 ------ 
3
5
NNNYY
6
NNINNI
4
NNNN
----- Sample Output 1 ------ 
NOT INDIAN
INDIAN
NOT SURE

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