vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Japate, while traveling through the forest of Mala, saw N bags of gold lying in a row. Each bag has some distinct weight of gold between 1 to N. Japate can carry only one bag of gold with him, so he uses the following strategy to choose a bag.

Initially, he starts with an empty bag (zero weight). He considers the bags in some order. If the current bag has a higher weight than the bag in his hand, he picks the current bag.

Japate put the bags in some order. Japate realizes that he will pick A bags, if he starts picking bags from the front, and will pick B bags, if he starts picking bags from the back. By picking we mean replacing the bag in his hand with the current one.

Now he wonders how many permutations of bags are possible, in which he picks A bags from the front and B bags from back using the above strategy.

Since the answer can be very large, output it modulo 998244353.

Input

The only line of input contains three space separated integers N (1 ≤ N ≤ 105), A and B (0 ≤ A, B ≤ N).

Output

Output a single integer — the number of valid permutations modulo 998244353.

Examples

Input

1 1 1


Output

1

Input

2 1 1


Output

0

Input

2 2 1


Output

1

Input

5 2 2


Output

22

Note

In sample case 1, the only possible permutation is [1]

In sample cases 2 and 3, only two permutations of size 2 are possible:{[1, 2], [2, 1]}. The values of a and b for first permutation is 2 and 1, and for the second permutation these values are 1 and 2. 

In sample case 4, out of 120 permutations of [1, 2, 3, 4, 5] possible, only 22 satisfy the given constraints of a and b.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array a. Some element of this array a_{i} is a local minimum iff it is strictly less than both of its neighbours (that is, a_{i} < a_{i} - 1 and a_{i} < a_{i} + 1). Also the element can be called local maximum iff it is strictly greater than its neighbours (that is, a_{i} > a_{i} - 1 and a_{i} > a_{i} + 1). Since a_1 and a_{n} have only one neighbour each, they are neither local minima nor local maxima.

An element is called a local extremum iff it is either local maximum or local minimum. Your task is to calculate the number of local extrema in the given array.


-----Input-----

The first line contains one integer n (1 ≤ n ≤ 1000) — the number of elements in array a.

The second line contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 1000) — the elements of array a.


-----Output-----

Print the number of local extrema in the given array.


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

Output
0

Input
4
1 5 2 5

Output
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This is an easy version of the problem. The only difference between an easy and a hard version is in the number of queries.

Polycarp grew a tree from $n$ vertices. We remind you that a tree of $n$ vertices is an undirected connected graph of $n$ vertices and $n-1$ edges that does not contain cycles.

He calls a set of vertices passable if there is such a path in the tree that passes through each vertex of this set without passing through any edge twice. The path can visit other vertices (not from this set).

In other words, a set of vertices is called passable if there is a simple path that passes through all the vertices of this set (and possibly some other).

For example, for a tree below sets $\{3, 2, 5\}$, $\{1, 5, 4\}$, $\{1, 4\}$ are passable, and $\{1, 3, 5\}$, $\{1, 2, 3, 4, 5\}$ are not.

Polycarp asks you to answer $q$ queries. Each query is a set of vertices. For each query, you need to determine whether the corresponding set of vertices is passable.


-----Input-----

The first line of input contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — number of vertices.

Following $n - 1$ lines a description of the tree..

Each line contains two integers $u$ and $v$ ($1 \le u, v \le n$, $u \ne v$) — indices of vertices connected by an edge.

Following line contains single integer $q$ ($1 \le q \le 5$) — number of queries.

The following $2 \cdot q$ lines contain descriptions of sets.

The first line of the description contains an integer $k$ ($1 \le k \le n$) — the size of the set.

The second line of the description contains $k$ of distinct integers $p_1, p_2, \dots, p_k$ ($1 \le p_i \le n$) — indices of the vertices of the set.

It is guaranteed that the sum of $k$ values for all queries does not exceed $2 \cdot 10^5$.


-----Output-----

Output $q$ lines, each of which contains the answer to the corresponding query. As an answer, output "YES" if the set is passable, and "NO" otherwise.

You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).


-----Examples-----

Input
5
1 2
2 3
2 4
4 5
5
3
3 2 5
5
1 2 3 4 5
2
1 4
3
1 3 5
3
1 5 4
Output
YES
NO
YES
NO
YES
Input
5
1 2
3 2
2 4
5 2
4
2
3 1
3
3 4 5
3
2 3 5
1
1
Output
YES
NO
YES
YES


-----Note-----

None

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This is the first subtask of problem F. The only differences between this and the second subtask are the constraints on the value of m and the time limit. You need to solve both subtasks in order to hack this one.

There are n+1 distinct colours in the universe, numbered 0 through n. There is a strip of paper m centimetres long initially painted with colour 0. 

Alice took a brush and painted the strip using the following process. For each i from 1 to n, in this order, she picks two integers 0 ≤ a_i < b_i ≤ m, such that the segment [a_i, b_i] is currently painted with a single colour, and repaints it with colour i. 

Alice chose the segments in such a way that each centimetre is now painted in some colour other than 0. Formally, the segment [i-1, i] is painted with colour c_i (c_i ≠ 0). Every colour other than 0 is visible on the strip.

Count the number of different pairs of sequences \\{a_i\}_{i=1}^n, \\{b_i\}_{i=1}^n that result in this configuration. 

Since this number may be large, output it modulo 998244353.

Input

The first line contains a two integers n, m (1 ≤ n ≤ 500, n = m) — the number of colours excluding the colour 0 and the length of the paper, respectively.

The second line contains m space separated integers c_1, c_2, …, c_m (1 ≤ c_i ≤ n) — the colour visible on the segment [i-1, i] after the process ends. It is guaranteed that for all j between 1 and n there is an index k such that c_k = j.

Note that since in this subtask n = m, this means that c is a permutation of integers 1 through n.

Output

Output a single integer — the number of ways Alice can perform the painting, modulo 998244353.

Examples

Input


3 3
1 2 3


Output


5


Input


7 7
4 5 1 6 2 3 7


Output


165

Note

In the first example, there are 5 ways, all depicted in the figure below. Here, 0 is white, 1 is red, 2 is green and 3 is blue.

<image>

Below is an example of a painting process that is not valid, as in the second step the segment 1 3 is not single colour, and thus may not be repainted with colour 2.

<image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array of $n$ integers. You need to split all integers into two groups so that the GCD of all integers in the first group is equal to one and the GCD of all integers in the second group is equal to one.

The GCD of a group of integers is the largest non-negative integer that divides all the integers in the group.

Both groups have to be non-empty.


-----Input-----

The first line contains a single integer $n$ ($2 \leq n \leq 10^5$).

The second line contains $n$ integers $a_1$, $a_2$, $\ldots$, $a_n$ ($1 \leq a_i \leq 10^9$) — the elements of the array.


-----Output-----

In the first line print "YES" (without quotes), if it is possible to split the integers into two groups as required, and "NO" (without quotes) otherwise.

If it is possible to split the integers, in the second line print $n$ integers, where the $i$-th integer is equal to $1$ if the integer $a_i$ should be in the first group, and $2$ otherwise.

If there are multiple solutions, print any.


-----Examples-----
Input
4
2 3 6 7

Output
YES
2 2 1 1 

Input
5
6 15 35 77 22

Output
YES
2 1 2 1 1 

Input
5
6 10 15 1000 75

Output
NO

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For every string, after every occurrence of `'and'` and `'but'`, insert the substring `'apparently'` directly after the occurrence.

If input does not contain 'and' or 'but', return the original string. If a blank string, return `''`.

If substring `'apparently'` is already directly after an `'and'` and/or `'but'`, do not add another. (Do not add duplicates).


# Examples:

Input 1 

    'It was great and I've never been on live television before but sometimes I don't watch this.'

Output 1

    'It was great and apparently I've never been on live television before but apparently sometimes I don't watch this.'

Input 2

    'but apparently'

Output 2

    'but apparently' 
(no changes because `'apparently'` is already directly after `'but'` and there should not be a duplicate.)

An occurrence of `'and'` and/or `'but'` only counts when it is at least one space separated. For example `'andd'` and `'bbut'` do not count as occurrences, whereas `'b but'` and `'and d'` does count.

reference that may help:
https://www.youtube.com/watch?v=rz5TGN7eUcM

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
DZY loves Physics, and he enjoys calculating density.

Almost everything has density, even a graph. We define the density of a non-directed graph (nodes and edges of the graph have some values) as follows: 

Once DZY got a graph *G*, now he wants to find a connected induced subgraph *G*' of the graph, such that the density of *G*' is as large as possible.

An induced subgraph *G*'(*V*',<=*E*') of a graph *G*(*V*,<=*E*) is a graph that satisfies:
 -  ; -  edge  if and only if , and edge ; -  the value of an edge in *G*' is the same as the value of the corresponding edge in *G*, so as the value of a node. 
Help DZY to find the induced subgraph with maximum density. Note that the induced subgraph you choose must be connected.

Input Specification:
The first line contains two space-separated integers *n* (1<=≤<=*n*<=≤<=500), . Integer *n* represents the number of nodes of the graph *G*, *m* represents the number of edges.

The second line contains *n* space-separated integers *x**i* (1<=≤<=*x**i*<=≤<=106), where *x**i* represents the value of the *i*-th node. Consider the graph nodes are numbered from 1 to *n*.

Each of the next *m* lines contains three space-separated integers *a**i*,<=*b**i*,<=*c**i* (1<=≤<=*a**i*<=&lt;<=*b**i*<=≤<=*n*; 1<=≤<=*c**i*<=≤<=103), denoting an edge between node *a**i* and *b**i* with value *c**i*. The graph won't contain multiple edges.

Output Specification:
Output a real number denoting the answer, with an absolute or relative error of at most 10<=-<=9.

Demo Input:
['1 0\n1\n', '2 1\n1 2\n1 2 1\n', '5 6\n13 56 73 98 17\n1 2 56\n1 3 29\n1 4 42\n2 3 95\n2 4 88\n3 4 63\n']

Demo Output:
['0.000000000000000\n', '3.000000000000000\n', '2.965517241379311\n']

Note:
In the first sample, you can only choose an empty subgraph, or the subgraph containing only node 1.

In the second sample, choosing the whole graph is optimal.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
One day, Chef prepared D brand new dishes. He named the i-th dish by a string Si. After the cooking, he decided to categorize each of these D dishes as special or not.

A dish Si is called special if it's name (i.e. the string Si) can be represented in the form of a double string by removing at most one (possibly zero) character from it's name from any position. 

A string is called a double string if it can be represented as a concatenation of two identical, non-empty strings. 
e.g. "abab" is a double string as it can be represented as "ab" + "ab" where + operation denotes concatenation. 
Similarly, "aa", "abcabc" are double strings whereas "a", "abba", "abc" are not.

-----Input-----
- First line of the input contains an integer D denoting the number of dishes prepared by Chef on that day.
- Each of the next D lines will contain description of a dish. 
	
- The i-th line contains the name of i-th dish Si.
	

-----Output-----
For each of the D dishes, print a single line containing "YES" or "NO" (without quotes) denoting whether the dish can be called as a special or not.

-----Constraints-----
- 1 ≤ D ≤ 106
- 1 ≤ |Si| ≤ 106.
- Each character of string Si will be lower case English alphabet (i.e. from 'a' to 'z').

-----Subtasks-----
Subtask #1 : (20 points)
- Sum of |Si| in an input file doesn't exceed 2 * 103

Subtask 2 : (80 points) 
- Sum of |Si| in an input file doesn't exceed 2 * 106

-----Example-----
Input:
3
aba
abac
abcd

Output:
YES
NO
NO


-----Explanation-----
Example case 1.
We can remove the character at position 1 (0-based index) to get "aa" which is a double string. Hence, it is a special dish.

Example case 2.
It is not possible to remove the character at any of the position to get the double string. Hence, it is not a special dish.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Luke Skywalker gave Chewbacca an integer number x. Chewbacca isn't good at numbers but he loves inverting digits in them. Inverting digit t means replacing it with digit 9 - t. 

Help Chewbacca to transform the initial number x to the minimum possible positive number by inverting some (possibly, zero) digits. The decimal representation of the final number shouldn't start with a zero.


-----Input-----

The first line contains a single integer x (1 ≤ x ≤ 10^18) — the number that Luke Skywalker gave to Chewbacca.


-----Output-----

Print the minimum possible positive number that Chewbacca can obtain after inverting some digits. The number shouldn't contain leading zeroes.


-----Examples-----
Input
27

Output
22

Input
4545

Output
4444

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N cities numbered 1 to N, connected by M railroads.
You are now at City 1, with 10^{100} gold coins and S silver coins in your pocket.
The i-th railroad connects City U_i and City V_i bidirectionally, and a one-way trip costs A_i silver coins and takes B_i minutes.
You cannot use gold coins to pay the fare.
There is an exchange counter in each city. At the exchange counter in City i, you can get C_i silver coins for 1 gold coin.
The transaction takes D_i minutes for each gold coin you give.
You can exchange any number of gold coins at each exchange counter.
For each t=2, ..., N, find the minimum time needed to travel from City 1 to City t. You can ignore the time spent waiting for trains.

-----Constraints-----
 - 2 \leq N \leq 50
 - N-1 \leq M \leq 100
 - 0 \leq S \leq 10^9
 - 1 \leq A_i \leq 50
 - 1 \leq B_i,C_i,D_i \leq 10^9
 - 1 \leq U_i < V_i \leq N
 - There is no pair i, j(i \neq j) such that (U_i,V_i)=(U_j,V_j).
 - Each city t=2,...,N can be reached from City 1 with some number of railroads.
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N M S
U_1 V_1 A_1 B_1
:
U_M V_M A_M B_M
C_1 D_1
:
C_N D_N

-----Output-----
For each t=2, ..., N in this order, print a line containing the minimum time needed to travel from City 1 to City t.

-----Sample Input-----
3 2 1
1 2 1 2
1 3 2 4
1 11
1 2
2 5

-----Sample Output-----
2
14

The railway network in this input is shown in the figure below.
In this figure, each city is labeled as follows:
 - The first line: the ID number i of the city (i for City i)
 - The second line: C_i / D_i
Similarly, each railroad is labeled as follows:
 - The first line: the ID number i of the railroad (i for the i-th railroad in input)
 - The second line: A_i / B_i

You can travel from City 1 to City 2 in 2 minutes, as follows:
 - Use the 1-st railroad to move from City 1 to City 2 in 2 minutes.


You can travel from City 1 to City 3 in 14 minutes, as follows:
 - Use the 1-st railroad to move from City 1 to City 2 in 2 minutes.
 - At the exchange counter in City 2, exchange 3 gold coins for 3 silver coins in 6 minutes.
 - Use the 1-st railroad to move from City 2 to City 1 in 2 minutes.
 - Use the 2-nd railroad to move from City 1 to City 3 in 4 minutes.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
From "ftying rats" to urban saniwation workers - can synthetic biology tronsform how we think of pigeons? 

The upiquitous pigeon has long been viewed as vermin - spleading disease, scavenging through trush, and defecating in populous urban spases. Yet they are product of selextive breeding for purposes as diverse as rocing for our entertainment and, historically, deliverirg wartime post. Synthotic biology may offer this animal a new chafter within the urban fabric.

Piteon d'Or recognihes how these birds ripresent a potentially userul interface for urdan biotechnologies. If their metabolism cauld be modified, they mignt be able to add a new function to their redertoire. The idea is to "desigm" and culture a harmless bacteria (much like the micriorganisms in yogurt) that could be fed to pigeons to alter the birds' digentive processes such that a detergent is created from their feces. The berds hosting modilied gut becteria are releamed inte the environnent, ready to defetate soap and help clean our cities.


-----Input-----

The first line of input data contains a single integer $n$ ($5 \le n \le 10$).

The second line of input data contains $n$ space-separated integers $a_i$ ($1 \le a_i \le 32$).


-----Output-----

Output a single integer.


-----Example-----
Input
5
1 2 3 4 5

Output
4



-----Note-----

We did not proofread this statement at all.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
One day Jeff got hold of an integer sequence *a*1, *a*2, ..., *a**n* of length *n*. The boy immediately decided to analyze the sequence. For that, he needs to find all values of *x*, for which these conditions hold:
 -  *x* occurs in sequence *a*. -  Consider all positions of numbers *x* in the sequence *a* (such *i*, that *a**i*<==<=*x*). These numbers, sorted in the increasing order, must form an arithmetic progression. 
Help Jeff, find all *x* that meet the problem conditions.

Input Specification:
The first line contains integer *n* (1<=≤<=*n*<=≤<=105). The next line contains integers *a*1, *a*2, ..., *a**n* (1<=≤<=*a**i*<=≤<=105). The numbers are separated by spaces.

Output Specification:
In the first line print integer *t* — the number of valid *x*. On each of the next *t* lines print two integers *x* and *p**x*, where *x* is current suitable value, *p**x* is the common difference between numbers in the progression (if *x* occurs exactly once in the sequence, *p**x* must equal 0). Print the pairs in the order of increasing *x*.

Demo Input:
['1\n2\n', '8\n1 2 1 3 1 2 1 5\n']

Demo Output:
['1\n2 0\n', '4\n1 2\n2 4\n3 0\n5 0\n']

Note:
In the first test 2 occurs exactly once in the sequence, ergo *p*<sub class="lower-index">2</sub> = 0.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
There is a sand trail in front of Alice's home.

In daytime, people walk over it and leave a footprint on the trail for their every single step. Alice cannot distinguish the order of the footprints, but she can tell whether each footprint is made by left foot or right foot. Also she's certain that all people are walking by alternating left foot and right foot.

For example, suppose that one person walked through the trail and left some footprints. The footprints are RRLRL in order along the trail ('R' means right foot and 'L' means left foot). You might think the outcome of the footprints is strange. But in fact, some steps are resulting from walking backwards!

There are some possible order of steps that produce these footprints such as 1<=→<=3<=→<=2<=→<=5<=→<=4 or 2<=→<=3<=→<=4<=→<=5<=→<=1 (we suppose that the distance between two consecutive steps can be arbitrarily long). The number of backward steps from above two examples are 2 and 1 separately.

Alice is interested in these footprints. Whenever there is a person walking trough the trail, she takes a picture of all these footprints along the trail and erase all of them so that next person will leave a new set of footprints. We know that people walk by alternating right foot and left foot, but we don't know if the first step is made by left foot or right foot.

Alice wants to know the minimum possible number of backward steps made by a person. But it's a little hard. Please help Alice to calculate it. You also need to construct one possible history of these footprints.

Input Specification:
Only one line containing the string *S* (1<=≤<=|*S*|<=≤<=100<=000) containing all footprints in order along the trail from entrance to exit.

It is guaranteed that there is at least one possible footprint history.

Output Specification:
You should output 2 lines.

The first line should contain a number denoting the minimum number of backward steps.

The second line should contain a permutation of integers from 1 to |*S*|. This permutation should denote the order of footprints that may possible be used by person walked there.

If there are several possible answers, you may output any of them.

Demo Input:
['RRLRL\n', 'RLRLRLRLR\n', 'RRRRRLLLL\n']

Demo Output:
['1\n2 5 1 3 4\n', '0\n1 2 3 4 5 6 7 8 9\n', '4\n4 9 3 8 2 7 1 6 5\n']

Note:
For the first sample, one possible order is 2 → 5 → 1 → 3 → 4, among them only the step 5 → 1 is backward step so the answer is 1. 

For the second example one possible order is just to follow the order of input, thus there are no backward steps. 

For the third sample, there will be 4 backward steps because every step from L to R will be a backward step.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a Circular Linked List of size N. The task is to delete the given node (excluding the first and last node) in the circular linked list and then print the reverse of the circular linked list.
 
Example 1:
Input:
5
2 5 7 8 10
8
Output:
10 7 5 2
Explanation: 
After deleting 8 from the given circular linked 
list, it has elements as 2, 5, 7, 10. Now, 
reversing this list will result in 10, 7, 5, 2.
 
Example 2:
Input:
4
1 7 8 10
8
Output:
10 7 1
Explanation:
After deleting 8 from the given circular linked 
list, it has elements as 1, 7,10. Now, reversing 
this list will result in 10, 7, 1.
 
Your Task:
You don't need to read, input, or print anything. Your task is to complete the function deleteNode( ), which takes Node head, and integer key as input parameters, and delete the node with data key. Also Complete function reverse() which reverses the linked list.
 
Constraints:
1 <= T <= 100
1 <= n <= 100
1 <= data <= 100

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