vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
*** Nova polynomial from roots*** 

This kata is from a series on polynomial handling. ( [#1](http://www.codewars.com/kata/nova-polynomial-1-add-1)   [#2](http://www.codewars.com/kata/570eb07e127ad107270005fe)  [#3](http://www.codewars.com/kata/5714041e8807940ff3001140 )   [#4](http://www.codewars.com/kata/571a2e2df24bdfd4e20001f5))

Consider a polynomial in a list where each element in the list element corresponds to the factors. The factor order is the position in the list. The first element is the zero order factor (the constant).

p = [a0, a1, a2, a3] signifies the polynomial a0 + a1x + a2x^2 + a3*x^3

In this kata create the polynomial from a list of roots:

[r0, r1 ,r2, r3 ]

p = (x-r0)(x-r1)(x-r2)(x-r3)

note: no roots should return the identity polynomial.

```python 
poly_from_roots([4]) = [-4, 1]
poly_from_roots([0, 0, 0, 0] ) = [0, 0, 0, 0, 1]
poly_from_roots([]) = [1]
```
The first katas of this series is preloaded in the code and can be used: [poly_add](http://www.codewars.com/kata/570eb07e127ad107270005fe) [poly_multiply](http://www.codewars.com/kata/570eb07e127ad107270005fe)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The principal of a school likes to put challenges to the students related with finding words of certain features.
One day she said: "Dear students, the challenge for today is to find a word that has only one vowel and seven consonants but cannot have the letters "y" and "m". I'll give a special award for the first student that finds it." One of the students used his dictionary and spent all the night without sleeping, trying in vain to find the word. The next day, the word had not been found yet.
This student observed that the principal has a pattern in the features for the wanted words: 

- The word should have **n** vowels, may be repeated, for example: in "engineering", n = 5.

- The word should have **m** consonants, may be repeated also: in "engineering", m = 6.

- The word should not have some forbidden letters (in an array), forbid_letters

You will be provided with a list of words, WORD_LIST(python/crystal), wordList(javascript), wordList (haskell), $word_list(ruby), and you have to create the function, ```wanted_words()```, that receives the three arguments in the order given above, ```wanted_words(n, m, forbid_list)```and output an array with the word or an array, having the words in the order given in the pre-loaded list, in the case of two or more words were found.

Let's see some cases:

```python
wanted_words(1, 7, ["m", "y"]) == ["strength"]
wanted_words(3, 7, ["m", "y"]) == ['afterwards', 'background', 'photograph', 'successful', 'understand']
```

For cases where no words are found the function will output an empty array.

```python
wanted_words(3, 7, ["a", "s" , "m", "y"]) == []
```

Help our student to win this and the next challenges of the school. He needs to sure about a suspect that he has. That many times there are no solutions for what the principal is asking for.
All words have its letters in lowercase format.
Enjoy it!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alice and Barbara played some friendly games of one-on-one basketball after work, and you agreed to help them keep score. The rules of the game were simple:
 - Each successful shot by a player earns them either one or two points;
 - The first player to eleven points wins, with one exception;
 - If the score is tied $10$–$10$, the previous rule is replaced by a “win by 2” rule: the first player to lead the other by at least two points wins.

So for example, $11$–$7$, $9$–$11$, and $14$–$12$ are possible final scores (but not $14$–$13$).

Whenever Alice or Barbara scored points, you jotted down an A or B (indicating a score by Alice or by Barbara) followed by a 1 or 2 (the number of points scored). You have some records of the games Alice and Barbara played in this format, but do not remember who won each game. Can you reconstruct the winner from the game record?

-----Input-----
The input consists of a single line with no more than $200$ characters: the record of one game. The record consists of single letters (either A or B) alternating with single numbers (either 1 or 2), and includes no spaces or other extraneous characters. Each record will be a correct scoring history of a single completed game, played under the rules described above.

-----Output-----
Print a single character, either A or B: the winner of the recorded game.

-----Examples-----
Sample Input:
A2B1A2B2A1A2A2A2
Sample Output:
A

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
To learn as soon as possible the latest news about their favourite fundamentally new operating system, BolgenOS community from Nizhni Tagil decided to develop a scheme. According to this scheme a community member, who is the first to learn the news, calls some other member, the latter, in his turn, calls some third member, and so on; i.e. a person with index i got a person with index fi, to whom he has to call, if he learns the news. With time BolgenOS community members understood that their scheme doesn't work sometimes — there were cases when some members didn't learn the news at all. Now they want to supplement the scheme: they add into the scheme some instructions of type (xi, yi), which mean that person xi has to call person yi as well. What is the minimum amount of instructions that they need to add so, that at the end everyone learns the news, no matter who is the first to learn it?

Input

The first input line contains number n (2 ≤ n ≤ 105) — amount of BolgenOS community members. The second line contains n space-separated integer numbers fi (1 ≤ fi ≤ n, i ≠ fi) — index of a person, to whom calls a person with index i.

Output

In the first line output one number — the minimum amount of instructions to add. Then output one of the possible variants to add these instructions into the scheme, one instruction in each line. If the solution is not unique, output any.

Examples

Input

3
3 3 2


Output

1
3 1


Input

7
2 3 1 3 4 4 1


Output

3
2 5
2 6
3 7

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Tonight, Chef would like to hold a party for his $N$ friends.
All friends are invited and they arrive at the party one by one in an arbitrary order. However, they have certain conditions — for each valid $i$, when the $i$-th friend arrives at the party and sees that at that point, strictly less than $A_i$ other people (excluding Chef) have joined the party, this friend leaves the party; otherwise, this friend joins the party.
Help Chef estimate how successful the party can be — find the maximum number of his friends who could join the party (for an optimal choice of the order of arrivals).

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains a single integer $N$.
- The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.

-----Output-----
For each test case, print a single line containing one integer — the maximum number of Chef's friends who could join the party.

-----Constraints-----
- $1 \le T \le 1,000$
- $1 \le N \le 10^5$
- the sum of $N$ over all test cases does not exceed $10^6$

-----Example Input-----
3
2
0 0
6
3 1 0 0 5 5
3
1 2 3

-----Example Output-----
2
4
0

-----Explanation-----
Example case 1: Chef has two friends. Both of them do not require anyone else to be at the party before they join, so they will both definitely join the party.
Example case 2: At the beginning, friends $3$ and $4$ can arrive and join the party, since they do not require anyone else to be at the party before they join. After that, friend $2$ can arrive; this friend would see that there are two people at the party and therefore also join. Then, friend $1$ will also join, so in the end, there would be $4$ people attending the party.
Example case 3: No one will attend the party because each of Chef's friends will find zero people at the party and leave, regardless of the order in which they arrive.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string. Remove all digits from it. When a character is removed from a string, all characters to the right of it are shifted one position to the left.

Input

The only line of input contains a string between 1 and 100 characters long. Each character of the string has ASCII-code between 33 (exclamation mark) and 126 (tilde), inclusive.

Output

Output the given string with all digits removed from it. If the original string had only digits, output an empty string.

Examples

Input

VK-Cup-2012!


Output

VK-Cup-!


Input

Go,Codeforces!


Output

Go,Codeforces!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mahmoud has n line segments, the i-th of them has length a_{i}. Ehab challenged him to use exactly 3 line segments to form a non-degenerate triangle. Mahmoud doesn't accept challenges unless he is sure he can win, so he asked you to tell him if he should accept the challenge. Given the lengths of the line segments, check if he can choose exactly 3 of them to form a non-degenerate triangle.

Mahmoud should use exactly 3 line segments, he can't concatenate two line segments or change any length. A non-degenerate triangle is a triangle with positive area.


-----Input-----

The first line contains single integer n (3 ≤ n ≤ 10^5) — the number of line segments Mahmoud has.

The second line contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9) — the lengths of line segments Mahmoud has.


-----Output-----

In the only line print "YES" if he can choose exactly three line segments and form a non-degenerate triangle with them, and "NO" otherwise.


-----Examples-----
Input
5
1 5 3 2 4

Output
YES

Input
3
4 1 2

Output
NO



-----Note-----

For the first example, he can use line segments with lengths 2, 4 and 5 to form a non-degenerate triangle.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a binary string S. You are allowed to perform the following operation at most once:
Pick some [substring] of S
Flip all the values in this substring, i.e, convert 0 to 1 and vice versa

For example, if S = 1\underline{00101}011, you can pick the underlined substring and flip it to obtain S = 1\underline{11010}011.

For the substring of S consisting of all the positions from L to R, we define a function f(L, R) to be the number of 1's in this substring. For example, if S = 100101011, then f(2, 5) = 1 and f(4, 9) = 4 (the respective substrings are 0010 and 101011).

If you perform the given operation optimally, find the maximum possible value of

\sum_{L=1}^N \sum_{R=L}^N f(L, R)

that can be obtained. Note that the substring flip operation can be performed at most once.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of single line of input, containing a binary string S.

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

For each test case, output on a new line the maximum possible value of \sum_{L=1}^N \sum_{R=L}^N f(L, R) that can be obtained.

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ |S| ≤ 3\cdot 10^{5}$
- The sum of $|S|$ over all test cases won't exceed $3\cdot 10^{5}$.

----- Sample Input 1 ------ 
3
111
000
00100
----- Sample Output 1 ------ 
10
10
26
----- explanation 1 ------ 
Test case $1$: There is no need to apply the operation since everything is already a $1$. The answer is thus the sum of:
- $f(1, 1) = 1$
- $f(1, 2) = 2$
- $f(1, 3) = 3$
- $f(2, 2) = 1$
- $f(2, 3) = 2$
- $f(3, 3) = 1$

which is $10$.

Test case $2$: Flip the entire string to obtain $111$, whose answer has been computed above.

Test case $3$: Flip the entire string to obtain $11011$. The sum of $f(L, R)$ across all substrings is now $26$, which is the maximum possible.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Ship's Shortest Path

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
You have got a new job, and it's very interesting, you are a ship captain. Your first task is to move your ship from one point to another point, and for sure you want to move it at the minimum cost.

And it's well known that the shortest distance between any 2 points is the length of the line segment between these 2 points. But unfortunately there is an island in the sea, so sometimes you won't be able to move your ship in the line segment between the 2 points.

You can only move to safe points. A point is called safe if it's on the line segment between the start and end points, or if it's on the island's edge.

But you are too lucky, you have got some clever and strong workers and they can help you in your trip, they can help you move the ship in the sea and they will take 1 Egyptian pound for each moving unit in the sea, and they can carry the ship (yes, they are very strong) and walk on the island and they will take 2 Egyptian pounds for each moving unit in the island. The money which you will give to them will be divided between all workers, so the number of workers does not matter here.

You can move your ship on the island edge, and it will be considered moving in the sea.

Now you have a sea map, and you have to decide what is the minimum cost for your trip.

Your starting point is (*xStart*, *yStart*), and the end point is (*xEnd*, *yEnd*), both points will be different.

The island will be a convex polygon and there will be no more than 2 polygon points on the same line, also the starting and the end points won't be inside or on the boundary of the island. The points for the polygon will be given in the anti-clockwise order.

Input Specification:
The first line contains 4 integers, *xStart*, *yStart*, *xEnd* and *yEnd* (<=-<=100<=≤<=*xStart*,<=*yStart*,<=*xEnd*,<=*yEnd*<=≤<=100). The second line contains an integer *n*, which is the number of points in the polygon (3<=≤<=*n*<=≤<=30), followed by a line containing *n* pairs of integers *x* and *y*, which are the coordinates of the points (<=-<=100<=≤<=*x*,<=*y*<=≤<=100), the polygon points will be distinct.

Output Specification:
Print one line which contains the minimum possible cost. The absolute or relative error in the answer should not exceed 10<=-<=6.

Demo Input:
['1 7 6 7\n4\n4 2 4 12 3 12 3 2\n', '-1 0 2 0\n4\n0 0 1 0 1 1 0 1\n']

Demo Output:
['6.000000000\n', '3.000000000\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Note that the only differences between easy and hard versions are the constraints on n and the time limit. You can make hacks only if all versions are solved.

Slime is interested in sequences. He defined good positive integer sequences p of length n as follows:

  * For each k>1 that presents in p, there should be at least one pair of indices i,j, such that 1 ≤ i < j ≤ n, p_i = k - 1 and p_j = k.



For the given integer n, the set of all good sequences of length n is s_n. For the fixed integer k and the sequence p, let f_p(k) be the number of times that k appears in p. For each k from 1 to n, Slime wants to know the following value:

$$$\left(∑_{p∈ s_n} f_p(k)\right)\ mod\ 998 244 353$$$

Input

The first line contains one integer n\ (1≤ n≤ 100 000).

Output

Print n integers, the i-th of them should be equal to \left(∑_{p∈ s_n} f_p(i)\right)\ mod\ 998 244 353.

Examples

Input


2


Output


3 1 


Input


3


Output


10 7 1 


Input


1


Output


1 

Note

In the first example, s=\{[1,1],[1,2]\}.

In the second example, s=\{[1,1,1],[1,1,2],[1,2,1],[1,2,2],[2,1,2],[1,2,3]\}.

In the third example, s=\{[1]\}.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef is frustrated in this lockown. So to overcome this he plans to travel various mountains.
He is very strange so he sets some conditions for $each$ Type 2 query(mentioned below) (i.e. $1$ $i$) : 
- Let Chef has travelled till $ith$ mountain from left to right.
- He does not like to travel the mountain with the height ,of which he has travelled till now. More formally, 
Let the height of peak on which he is standing is $a_{i}$ then he can only go to the peak of height $a_{j}$ 
which is greater than $a_{i}$ and nearest to $ith$ mountain such that there should be no other peak of same height $a_{j}$ till $a_{i}$(height of $ith$ mountain) .

-----Input format:-----
- 
The first line contains an integer $T$ denoting the number of test cases.
- 
The second line of  consist of a integer $N$ and $Q$ .
- 
The third line contains $N$ not necessarily distinct positive integers $a_{0},a_{1}, . . .,a_{n-1}$ denoting the height of 
$N$ mountains.
- 
Then next $Q$ lines follows where each line consisting of $either$ of $2$ types of queries:
Type 1:  $0$ $A$ $B$ i.e. $a_{A} = B$ (where height of $Ath$ mountain will be updated to $B$) 
Type 2:  $1$ $A$ i.e. you have to answer $a_k$ which is greater than $a_{A}$ and nearest to $Ath$ mountain such that there should be no other peak of same height $a_{k}$ till $a_{A}$(height of $Ath$ mountain) .

-----Output format:-----
- For every query of Type 2 there should be an integer $a_{k}$ on next  line for the updated array , If no such $a_{k}$ exists then $a_{k}$= $-1$ , as query of type 1 will have no output . 

-----Constraints:-----
- $1\leq T \leq 10^2$
- $1 \leq N,Q \leq 10^4$
- $0\leq a_{i} \leq 10^6$
- $0\leq B \leq 10^6$
- $0\leq A \leq N-1$

-----Subtasks-----
- 
1 Point :   
$1 \leq T,N,Q \leq 10^2$ 
$0\leq B,a_{i} \leq 10^2$
- 
99 Points : Orginal   Constraints

-----Example:-----

-----Input:-----
1
10 5
1 3 5 4 5 6 7 8  4 5
1 7
1 3
1 1
0 2 7
1 3

-----Output:-----
-1
6
5
5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
=====Problem Statement=====
Given a list of rational numbers,find their product.

Concept
The reduce() function applies a function of two arguments cumulatively on a list of objects in succession from left to right to reduce it to one value. Say you have a list, say [1,2,3] and you have to find its sum.

>>> reduce(lambda x, y : x + y,[1,2,3])
6

You can also define an initial value. If it is specified, the function will assume initial value as the value given, and then reduce. It is equivalent to adding the initial value at the beginning of the list. For example:

>>> reduce(lambda x, y : x + y, [1,2,3], -3)
3

>>> from fractions import gcd
>>> reduce(gcd, [2,4,8], 3)
1

=====Input Format=====
First line contains n, the number of rational numbers.
The ith of next n lines contain two integers each, the numerator (N_i) and denominator (D_i) of the ith rational number in the list.

=====Constraints=====
1≤n≤100
1≤N_i,D_i≤10^9

=====Output Format=====
Print only one line containing the numerator and denominator of the product of the numbers in the list in its simplest form, i.e. numerator and denominator have no common divisor other than 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have an initial power P, an initial score of 0 points, and a bag of tokens.
Each token can be used at most once, has a value token[i], and has potentially two ways to use it.

If we have at least token[i] power, we may play the token face up, losing token[i] power, and gaining 1 point.
If we have at least 1 point, we may play the token face down, gaining token[i] power, and losing 1 point.

Return the largest number of points we can have after playing any number of tokens.
 



Example 1:
Input: tokens = [100], P = 50
Output: 0


Example 2:
Input: tokens = [100,200], P = 150
Output: 1


Example 3:
Input: tokens = [100,200,300,400], P = 200
Output: 2

 
Note:

tokens.length <= 1000
0 <= tokens[i] < 10000
0 <= P < 10000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
How many stars are there in the sky? A young programmer Polycarpus can't get this question out of his head! He took a photo of the starry sky using his digital camera and now he analyzes the resulting monochrome digital picture. The picture is represented by a rectangular matrix consisting of n lines each containing m characters. A character equals '1', if the corresponding photo pixel is white and '0', if it is black.

Polycarpus thinks that he has found a star on the photo if he finds a white pixel surrounded by four side-neighboring pixels that are also white: 
    
    
      
     1   
    111  
     1   
    

a star on the photo

Polycarpus whats to cut out a rectangular area from the photo and give his mom as a present. This area should contain no less than k stars. The stars can intersect, have shared white pixels on the photo. The boy will cut out the rectangular area so that its borders will be parallel to the sides of the photo and the cuts will go straight between the pixel borders.

Now Polycarpus keeps wondering how many ways there are to cut an area out of the photo so that it met the conditions given above. Help Polycarpus find this number.

Input

The first line of the input data contains three integers n, m and k (1 ≤ n, m ≤ 500;1 ≤ k ≤ nm). Then follow n lines, containing the description of the given photo as a sequence of lines. Each line contains m characters '0' or '1'.

Output

Print the required number of areas on the given photo.

Examples

Input

4 6 2
111000
111100
011011
000111


Output

6


Input

5 5 4
11111
11111
11111
11111
11111


Output

9

Note

We'll number the rows and columns below starting from 1, the coordinates (p, q) will denote a cell in row p, column q.

In the first sample Polycarpus should cut out any area containing a rectangle whose opposite corners lie in cells (1, 1) and (3, 4). Only rectangles with opposite corners in (1, 1) and (x, y), where x ≥ 3 and y ≥ 4 fit the conditions.

In the second sample any rectangle whose each side is no less than four, will do. The possible rectangle sizes are 4 × 4, 4 × 5, 5 × 4 and 5 × 5. Such figures can be cut in 4 ways, 2 ways, 2 ways and 1 way correspondingly.

Please do not use the %lld specificator to read or write 64-bit integers in C++. It is preferred to use cin, cout streams or the %I64d specificator.

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