vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
You are given a description of a depot. It is a rectangular checkered field of n × m size. Each cell in a field can be empty (".") or it can be occupied by a wall ("*"). 

You have one bomb. If you lay the bomb at the cell (x, y), then after triggering it will wipe out all walls in the row x and all walls in the column y.

You are to determine if it is possible to wipe out all walls in the depot by placing and triggering exactly one bomb. The bomb can be laid both in an empty cell or in a cell occupied by a wall.


-----Input-----

The first line contains two positive integers n and m (1 ≤ n, m ≤ 1000) — the number of rows and columns in the depot field. 

The next n lines contain m symbols "." and "*" each — the description of the field. j-th symbol in i-th of them stands for cell (i, j). If the symbol is equal to ".", then the corresponding cell is empty, otherwise it equals "*" and the corresponding cell is occupied by a wall.


-----Output-----

If it is impossible to wipe out all walls by placing and triggering exactly one bomb, then print "NO" in the first line (without quotes).

Otherwise print "YES" (without quotes) in the first line and two integers in the second line — the coordinates of the cell at which the bomb should be laid. If there are multiple answers, print any of them.


-----Examples-----
Input
3 4
.*..
....
.*..

Output
YES
1 2

Input
3 3
..*
.*.
*..

Output
NO

Input
6 5
..*..
..*..
*****
..*..
..*..
..*..

Output
YES
3 3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let S be the concatenation of 10^{10} copies of the string 110. (For reference, the concatenation of 3 copies of 110 is 110110110.)
We have a string T of length N.
Find the number of times T occurs in S as a contiguous substring.

-----Constraints-----
 - 1 \leq N \leq 2 \times 10^5
 - T is a string of length N consisting of 0 and 1.

-----Input-----
Input is given from Standard Input in the following format:
N
T

-----Output-----
Print the number of times T occurs in S as a contiguous substring.

-----Sample Input-----
4
1011

-----Sample Output-----
9999999999

S is so long, so let us instead count the number of times 1011 occurs in the concatenation of 3 copies of 110, that is, 110110110. We can see it occurs twice:
 - 1 1011 0110
 - 1101 1011 0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ivan places knights on infinite chessboard. Initially there are $n$ knights. If there is free cell which is under attack of at least $4$ knights then he places new knight in this cell. Ivan repeats this until there are no such free cells. One can prove that this process is finite. One can also prove that position in the end does not depend on the order in which new knights are placed.

Ivan asked you to find initial placement of exactly $n$ knights such that in the end there will be at least $\lfloor \frac{n^{2}}{10} \rfloor$ knights.


-----Input-----

The only line of input contains one integer $n$ ($1 \le n \le 10^{3}$) — number of knights in the initial placement.


-----Output-----

Print $n$ lines. Each line should contain $2$ numbers $x_{i}$ and $y_{i}$ ($-10^{9} \le x_{i}, \,\, y_{i} \le 10^{9}$) — coordinates of $i$-th knight. For all $i \ne j$, $(x_{i}, \,\, y_{i}) \ne (x_{j}, \,\, y_{j})$ should hold. In other words, all knights should be in different cells.

It is guaranteed that the solution exists.


-----Examples-----
Input
4

Output
1 1
3 1
1 5
4 4

Input
7

Output
2 1
1 2
4 1
5 2
2 6
5 7
6 6



-----Note-----

Let's look at second example:

$\left. \begin{array}{|l|l|l|l|l|l|l|l|l|} \hline 7 & {} & {} & {} & {} & {0} & {} & {} \\ \hline 6 & {} & {0} & {} & {} & {} & {0} & {} \\ \hline 5 & {} & {} & {} & {2} & {} & {} & {} \\ \hline 4 & {} & {} & {} & {} & {} & {} & {} \\ \hline 3 & {} & {} & {1} & {} & {} & {} & {} \\ \hline 2 & {0} & {} & {} & {} & {0} & {} & {} \\ \hline 1 & {} & {0} & {} & {0} & {} & {} & {} \\ \hline & {1} & {2} & {3} & {4} & {5} & {6} & {7} \\ \hline \end{array} \right.$

Green zeroes are initial knights. Cell $(3, \,\, 3)$ is under attack of $4$ knights in cells $(1, \,\, 2)$, $(2, \,\, 1)$, $(4, \,\, 1)$ and $(5, \,\, 2)$, therefore Ivan will place a knight in this cell. Cell $(4, \,\, 5)$ is initially attacked by only $3$ knights in cells $(2, \,\, 6)$, $(5, \,\, 7)$ and $(6, \,\, 6)$. But new knight in cell $(3, \,\, 3)$ also attacks cell $(4, \,\, 5)$, now it is attacked by $4$ knights and Ivan will place another knight in this cell. There are no more free cells which are attacked by $4$ or more knights, so the process stops. There are $9$ knights in the end, which is not less than $\lfloor \frac{7^{2}}{10} \rfloor = 4$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
[Æsir - CHAOS](https://soundcloud.com/kivawu/aesir-chaos)

[Æsir - V.](https://soundcloud.com/kivawu/aesir-v)

"Everything has been planned out. No more hidden concerns. The condition of Cytus is also perfect.

The time right now...... 00:01:12......

It's time."

The emotion samples are now sufficient. After almost 3 years, it's time for Ivy to awake her bonded sister, Vanessa.

The system inside A.R.C.'s Library core can be considered as an undirected graph with infinite number of processing nodes, numbered with all positive integers (1, 2, 3, …). The node with a number x (x > 1), is directly connected with a node with number (x)/(f(x)), with f(x) being the lowest prime divisor of x.

Vanessa's mind is divided into n fragments. Due to more than 500 years of coma, the fragments have been scattered: the i-th fragment is now located at the node with a number k_i! (a factorial of k_i).

To maximize the chance of successful awakening, Ivy decides to place the samples in a node P, so that the total length of paths from each fragment to P is smallest possible. If there are multiple fragments located at the same node, the path from that node to P needs to be counted multiple times.

In the world of zeros and ones, such a requirement is very simple for Ivy. Not longer than a second later, she has already figured out such a node.

But for a mere human like you, is this still possible?

For simplicity, please answer the minimal sum of paths' lengths from every fragment to the emotion samples' assembly node P.

Input

The first line contains an integer n (1 ≤ n ≤ 10^6) — number of fragments of Vanessa's mind.

The second line contains n integers: k_1, k_2, …, k_n (0 ≤ k_i ≤ 5000), denoting the nodes where fragments of Vanessa's mind are located: the i-th fragment is at the node with a number k_i!.

Output

Print a single integer, denoting the minimal sum of path from every fragment to the node with the emotion samples (a.k.a. node P).

As a reminder, if there are multiple fragments at the same node, the distance from that node to P needs to be counted multiple times as well.

Examples

Input


3
2 1 4


Output


5


Input


4
3 1 4 4


Output


6


Input


4
3 1 4 1


Output


6


Input


5
3 1 4 1 5


Output


11

Note

Considering the first 24 nodes of the system, the node network will look as follows (the nodes 1!, 2!, 3!, 4! are drawn bold):

<image>

For the first example, Ivy will place the emotion samples at the node 1. From here:

  * The distance from Vanessa's first fragment to the node 1 is 1. 
  * The distance from Vanessa's second fragment to the node 1 is 0. 
  * The distance from Vanessa's third fragment to the node 1 is 4. 



The total length is 5.

For the second example, the assembly node will be 6. From here:

  * The distance from Vanessa's first fragment to the node 6 is 0. 
  * The distance from Vanessa's second fragment to the node 6 is 2. 
  * The distance from Vanessa's third fragment to the node 6 is 2. 
  * The distance from Vanessa's fourth fragment to the node 6 is again 2. 



The total path length is 6.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
MoEngage noticed that some users are not aware of the practice page on CodeChef, and some others are not aware of the rated contests on CodeChef. So, MoEngage wants to send an email to the users depending on which of the following groups they fall into:
1. If the user has never submitted on the practice page then send an email with the text:

https://www.codechef.com/practice
2. If the user has submitted on the practice page, but never participated in a contest then send an email with the text:

https://www.codechef.com/contests
3. If the user has submitted on the practice page as well as participated in a contest then send an email with the text: 

https://discuss.codechef.com

so that they may discuss with other members of the community.

Help MoEngage by writing a program that takes as input two integers A and B where: 
A = 1 if the user has submitted on the practice page and 0 otherwise.
B = 1 if the user has participated in a contest and 0 otherwise.

Output the appropriate link to be displayed in the email.

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

- The input consists of a single line with two space-separated integers A and B.

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

- Print one of the following strings as per the problem statement.
- https://www.codechef.com/practice
- https://www.codechef.com/contests
- https://discuss.codechef.com 

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

$A$ is either $0$ or $1$.
$B$ is either $0$ or $1$.

----- Sample Input 1 ------ 
0 1
----- Sample Output 1 ------ 
https://www.codechef.com/practice
----- explanation 1 ------ 
The user has not submitted on the practice page, so the program must output the link to the practice page.

----- Sample Input 2 ------ 
1 0
----- Sample Output 2 ------ 
https://www.codechef.com/contests
----- explanation 2 ------ 
The user has submitted on the practice page, but has not participated in a contest, so the program must output the link to the contest page.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
As the students are back in hostel after a long time, the gamers have decided to have a LAN gaming competition to find out who has utilized his time in gaming during vacations. They play "Counter ATOD". However, the scoring of this game is weird. There are N players and there are M rounds. Initially, each player has 0 points. The player gets the points only if he has won the round. Points can be negative too(weird).

The winner of the whole contest is the one who has maximum points after any round. However,  it isn't necessary at all that the winner will have maximum points at the end of the game. As the scoring is pretty weird, they  asks for your help.

Input Format :
First line of input will consist of N and M denoting the number of players and rounds respectively.
Next M lines will contain the name of the player who won the round and the points P he earned after that round.
First round will always have positive points.

Output Format: 
The only line of output will contain the name of the winner who got maximum points in the contest at any point of the game.
In case of draw, the winner will be the player who got maximum points earlier.

Constraints :
1 ≤ N ≤ 100
1 ≤ M ≤ 5000
1 ≤ Length of name ≤ 15
-10^6 ≤ P ≤ 10^6

Problem Setter : Swastik Mundra

SAMPLE INPUT
3 5
Murliwala 5
Mithaiwala 4
Mithaiwala 4
Mithaiwala -2
Mirchiwala 8

SAMPLE OUTPUT
Mithaiwala

Explanation

After round 1, Murliwala wins the round and  gains 5 points but as Mirchiwala and Mithaiwala has not won the round, they will not gain any point. 

After round 2, Mithaiwala wins the round and gains 4 points. However Murliwala has still 5 points and Mirchiwala has 0 points.

After round 3, Mithaiwala wins the round and gains 4 points. His total is 8 points now and is maximum. However Murliwala has still 5 points and Mirchiwala has 0 points.

After round 4, Mithaiwala wins again and gains -2 points which brings his total to 6 points.

After round 5, Mirchiwala wins and gains 8 points.

Maximum points throughout the game was 8
but as Murliwala earned 8 points first he is the winner.
However, the total of Mithaiwala at the end was 6.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Nudist Beach is planning a military operation to attack the Life Fibers. In this operation, they will attack and capture several cities which are currently under the control of the Life Fibers.

There are *n* cities, labeled from 1 to *n*, and *m* bidirectional roads between them. Currently, there are Life Fibers in every city. In addition, there are *k* cities that are fortresses of the Life Fibers that cannot be captured under any circumstances. So, the Nudist Beach can capture an arbitrary non-empty subset of cities with no fortresses.

After the operation, Nudist Beach will have to defend the captured cities from counterattack. If they capture a city and it is connected to many Life Fiber controlled cities, it will be easily defeated. So, Nudist Beach would like to capture a set of cities such that for each captured city the ratio of Nudist Beach controlled neighbors among all neighbors of that city is as high as possible. 

More formally, they would like to capture a non-empty set of cities *S* with no fortresses of Life Fibers. The strength of a city  is defined as (number of neighbors of *x* in *S*) / (total number of neighbors of *x*). Here, two cities are called neighbors if they are connnected with a road. The goal is to maximize the strength of the weakest city in *S*.

Given a description of the graph, and the cities with fortresses, find a non-empty subset that maximizes the strength of the weakest city.

Input Specification:
The first line of input contains three integers *n*,<=*m*,<=*k* (2<=<=≤<=<=*n*<=<=≤<=100<=000, 1<=≤<=*m*<=≤<=100<=000, 1<=≤<=*k*<=≤<=*n*<=-<=1).

The second line of input contains *k* integers, representing the cities with fortresses. These cities will all be distinct. 

The next *m* lines contain the roads. The *i*-th of these lines will have 2 integers *a**i*,<=*b**i* (1<=≤<=*a**i*,<=*b**i*<=≤<=*n*, *a**i*<=≠<=*b**i*). Every city will have at least one road adjacent to it.

There is no more than one road between each pair of the cities.

Output Specification:
The first line should contain an integer *r*, denoting the size of an optimum set (1<=≤<=*r*<=≤<=*n*<=-<=*k*). 

The second line should contain *r* integers, denoting the cities in the set. Cities may follow in an arbitrary order. This line should not contain any of the cities with fortresses.

If there are multiple possible answers, print any of them.

Demo Input:
['9 8 4\n3 9 6 8\n1 2\n1 3\n1 4\n1 5\n2 6\n2 7\n2 8\n2 9\n', '10 8 2\n2 9\n1 3\n2 9\n4 5\n5 6\n6 7\n7 8\n8 10\n10 4\n']

Demo Output:
['3\n1 4 5\n', '8\n1 5 4 8 10 6 3 7\n']

Note:
The first example case achieves a strength of 1/2. No other subset is strictly better.

The second example case achieves a strength of 1. Note that the subset doesn't necessarily have to be connected.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Pal loves coding. He solves problems daily on online judges  and participates in college OPCs. He keeps track of time he spents on coding everyday. 

But Pal is inconsistent. Some day he codes for 1000 units of time and other day he may code for 1 unit of time. Now inconsistency in Pal's case is defined as difference of coding times of any two days. Pal wishes to find his minimum inconsistency.

You will be given coding time of Pal for n days. You have to find minimum  inconsistency.

Input:-

First line contains number of test cases t.Each test case begins with number of days n. The next line contains coding times for n days.

Output:-

Print minimum inconsistency per test case.

Constraints:-

t ≤ 20

n ≤ 1000000

coding time for each day ≤ 10000000

SAMPLE INPUT
2
5
2 8 5 9 11
4
3 12 8 5

SAMPLE OUTPUT
1 
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For a dictionary $M$ that stores elements formed by a pair of a string key and an integer value, perform a sequence of the following operations. Note that each key in $M$ must be unique.

* insert($key$, $x$): Insert an element formed by a pair of $key$ and $x$ to $M$.
* get($key$): Print the value with the specified $key$. Print 0 if there is no such element.
* delete($key$): Delete the element with the specified $key$.
* dump($L$, $R$): Print all elements formed by a pair of the key and the value such that the key is greater than or equal to $L$ and less than or equal to $R$ in lexicographic order.

Constraints

* $1 \leq q \leq 200,000$
* $1 \leq x \leq 1,000,000,000$
* $1 \leq $ length of $key$ $ \leq 20$
* $key$ consists of lower-case letters
* $L \leq R$ in lexicographic order
* The total number of elements printed by dump operations does not exceed $1,000,000$

Input

The input is given in the following format.


$q$
$query_1$
$query_2$
:
$query_q$


Each query $query_i$ is given by


0 $key$ $x$


or


1 $key$


or


2 $key$


or


3 $L$ $R$


where the first digits 0, 1, 2 and 3 represent insert, get, delete and dump operations.

Output

For each get operation, print the corresponding value.
For each dump operation, print the corresponding elements formed by a pair of the key and the value. For the dump operation, print the elements (a pair of key and value separated by a space character) in ascending order of the keys.

Example

Input

9
0 blue 4
0 red 1
0 white 5
1 red
1 blue
2 red
1 black
1 red
3 w z


Output

1
4
0
0
white 5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Assume you are creating a webshop and you would like to help the user in the search. You have products with brands, prices and name. You have the history of opened products (the most recently opened being the first item).

Your task is to create a list of brands ordered by popularity, if two brands have the same popularity level then choose the one which was opened last from the two and second the other one.

Product popularity is calculated from the history. If a product is more times in the history than it is more popular.

Your function will have one parameter which will be always an array/list of object.

example product:
{
  name: "Phone",
  price: 25,
  brand: "Fake brand"
}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You went shopping to buy cakes and donuts with X yen (the currency of Japan).

First, you bought one cake for A yen at a cake shop. Then, you bought as many donuts as possible for B yen each, at a donut shop.

How much do you have left after shopping?

Constraints

* 1 \leq A, B \leq 1 000
* A + B \leq X \leq 10 000
* X, A and B are integers.

Input

Input is given from Standard Input in the following format:


X
A
B


Output

Print the amount you have left after shopping.

Examples

Input

1234
150
100


Output

84


Input

1000
108
108


Output

28


Input

579
123
456


Output

0


Input

7477
549
593


Output

405

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Santa Claus has n candies, he dreams to give them as gifts to children.

What is the maximal number of children for whose he can give candies if Santa Claus want each kid should get distinct positive integer number of candies. Santa Class wants to give all n candies he has.


-----Input-----

The only line contains positive integer number n (1 ≤ n ≤ 1000) — number of candies Santa Claus has.


-----Output-----

Print to the first line integer number k — maximal number of kids which can get candies.

Print to the second line k distinct integer numbers: number of candies for each of k kid. The sum of k printed numbers should be exactly n.

If there are many solutions, print any of them.


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

Output
2
2 3

Input
9

Output
3
3 5 1

Input
2

Output
1
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Eighth-grader Vova is on duty today in the class. After classes, he went into the office to wash the board, and found on it the number n. He asked what is this number and the teacher of mathematics Inna Petrovna answered Vova that n is the answer to the arithmetic task for first-graders. In the textbook, a certain positive integer x was given. The task was to add x to the sum of the digits of the number x written in decimal numeral system.

Since the number n on the board was small, Vova quickly guessed which x could be in the textbook. Now he wants to get a program which will search for arbitrary values of the number n for all suitable values of x or determine that such x does not exist. Write such a program for Vova.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^9).


-----Output-----

In the first line print one integer k — number of different values of x satisfying the condition. 

In next k lines print these values in ascending order.


-----Examples-----
Input
21

Output
1
15

Input
20

Output
0



-----Note-----

In the first test case x = 15 there is only one variant: 15 + 1 + 5 = 21.

In the second test case there are no such x.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string s, process q queries, each having one of the following forms:

  * 1 i c — Change the i-th character in the string to c. 
  * 2 l r y — Consider the substring of s starting at position l and ending at position r. Output the number of times y occurs as a substring in it. 

Input

The first line of the input contains the string s (1 ≤ |s| ≤ 105) of lowercase English letters.

The second line contains an integer q (1 ≤ q ≤ 105) — the number of queries to process.

The next q lines describe the queries and may have one of the following forms:

  * 1 i c (1 ≤ i ≤ |s|) 
  * 2 l r y (1 ≤ l ≤ r ≤ |s|) 



c is a lowercase English letter and y is a non-empty string consisting of only lowercase English letters.

The sum of |y| over all queries of second type is at most 105.

It is guaranteed that there is at least one query of second type.

All strings are 1-indexed.

|s| is the length of the string s.

Output

For each query of type 2, output the required answer in a separate line.

Examples

Input

ababababa
3
2 1 7 aba
1 5 c
2 1 7 aba


Output

3
1


Input

abcdcbc
5
2 1 7 bc
1 4 b
2 4 7 bc
1 2 a
2 1 4 aa


Output

2
2
1

Note

Consider the first sample case. Initially, the string aba occurs 3 times in the range [1, 7]. Note that two occurrences may overlap. 

After the update, the string becomes ababcbaba and now aba occurs only once in the range [1, 7].

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