meetforever/GRPO_CL huggingface dataset:
user: Bandits appeared in the city! One of them is trying to catch as many citizens as he can.

The city consists of $n$ squares connected by $n-1$ roads in such a way that it is possible to reach any square from any other square. The square number $1$ is the main square.

After Sunday walk all the roads were changed to one-way roads in such a way that it is possible to reach any square from the main square.

At the moment when the bandit appeared on the main square there were $a_i$ citizens on the $i$-th square. Now the following process will begin. First, each citizen that is currently on a square with some outgoing one-way roads chooses one of such roads and moves along it to another square. Then the bandit chooses one of the one-way roads outgoing from the square he is located and moves along it. The process is repeated until the bandit is located on a square with no outgoing roads. The bandit catches all the citizens on that square.

The bandit wants to catch as many citizens as possible; the citizens want to minimize the number of caught people. The bandit and the citizens know positions of all citizens at any time, the citizens can cooperate. If both sides act optimally, how many citizens will be caught?


-----Input-----

The first line contains a single integer $n$ — the number of squares in the city ($2 \le n \le 2\cdot10^5$).

The second line contains $n-1$ integers $p_2, p_3 \dots p_n$ meaning that there is a one-way road from the square $p_i$ to the square $i$ ($1 \le p_i < i$). 

The third line contains $n$ integers $a_1, a_2, \dots, a_n$ — the number of citizens on each square initially ($0 \le a_i \le 10^9$).


-----Output-----

Print a single integer — the number of citizens the bandit will catch if both sides act optimally.


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

Output
3

Input
3
1 1
3 1 3

Output
4



-----Note-----

In the first example the citizens on the square $1$ can split into two groups $2 + 1$, so that the second and on the third squares will have $3$ citizens each.

In the second example no matter how citizens act the bandit can catch at least $4$ citizens.
user: Analyzing the mistakes people make while typing search queries is a complex and an interesting work. As there is no guaranteed way to determine what the user originally meant by typing some query, we have to use different sorts of heuristics.

Polycarp needed to write a code that could, given two words, check whether they could have been obtained from the same word as a result of typos. Polycarpus suggested that the most common typo is skipping exactly one letter as you type a word.

Implement a program that can, given two distinct words S and T of the same length n determine how many words W of length n + 1 are there with such property that you can transform W into both S, and T by deleting exactly one character. Words S and T consist of lowercase English letters. Word W also should consist of lowercase English letters.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 100 000) — the length of words S and T.

The second line contains word S.

The third line contains word T.

Words S and T consist of lowercase English letters. It is guaranteed that S and T are distinct words.


-----Output-----

Print a single integer — the number of distinct words W that can be transformed to S and T due to a typo.


-----Examples-----
Input
7
reading
trading

Output
1

Input
5
sweet
sheep

Output
0

Input
3
toy
try

Output
2



-----Note-----

In the first sample test the two given words could be obtained only from word "treading" (the deleted letters are marked in bold).

In the second sample test the two given words couldn't be obtained from the same word by removing one letter.

In the third sample test the two given words could be obtained from either word "tory" or word "troy".
user: Although Inzane successfully found his beloved bone, Zane, his owner, has yet to return. To search for Zane, he would need a lot of money, of which he sadly has none. To deal with the problem, he has decided to hack the banks. [Image] 

There are n banks, numbered from 1 to n. There are also n - 1 wires connecting the banks. All banks are initially online. Each bank also has its initial strength: bank i has initial strength a_{i}.

Let us define some keywords before we proceed. Bank i and bank j are neighboring if and only if there exists a wire directly connecting them. Bank i and bank j are semi-neighboring if and only if there exists an online bank k such that bank i and bank k are neighboring and bank k and bank j are neighboring.

When a bank is hacked, it becomes offline (and no longer online), and other banks that are neighboring or semi-neighboring to it have their strengths increased by 1.

To start his plan, Inzane will choose a bank to hack first. Indeed, the strength of such bank must not exceed the strength of his computer. After this, he will repeatedly choose some bank to hack next until all the banks are hacked, but he can continue to hack bank x if and only if all these conditions are met:  Bank x is online. That is, bank x is not hacked yet.  Bank x is neighboring to some offline bank.  The strength of bank x is less than or equal to the strength of Inzane's computer. 

Determine the minimum strength of the computer Inzane needs to hack all the banks.


-----Input-----

The first line contains one integer n (1 ≤ n ≤ 3·10^5) — the total number of banks.

The second line contains n integers a_1, a_2, ..., a_{n} ( - 10^9 ≤ a_{i} ≤ 10^9) — the strengths of the banks.

Each of the next n - 1 lines contains two integers u_{i} and v_{i} (1 ≤ u_{i}, v_{i} ≤ n, u_{i} ≠ v_{i}) — meaning that there is a wire directly connecting banks u_{i} and v_{i}.

It is guaranteed that the wires connect the banks in such a way that Inzane can somehow hack all the banks using a computer with appropriate strength.


-----Output-----

Print one integer — the minimum strength of the computer Inzane needs to accomplish the goal.


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

Output
5
Input
7
38 -29 87 93 39 28 -55
1 2
2 5
3 2
2 4
1 7
7 6

Output
93
Input
5
1 2 7 6 7
1 5
5 3
3 4
2 4

Output
8


-----Note-----

In the first sample, Inzane can hack all banks using a computer with strength 5. Here is how:  Initially, strengths of the banks are [1, 2, 3, 4, 5].  He hacks bank 5, then strengths of the banks become [1, 2, 4, 5,  - ].  He hacks bank 4, then strengths of the banks become [1, 3, 5,  - ,  - ].  He hacks bank 3, then strengths of the banks become [2, 4,  - ,  - ,  - ].  He hacks bank 2, then strengths of the banks become [3,  - ,  - ,  - ,  - ].  He completes his goal by hacking bank 1. 

In the second sample, Inzane can hack banks 4, 2, 3, 1, 5, 7, and 6, in this order. This way, he can hack all banks using a computer with strength 93.
user: The three friends, Kuro, Shiro, and Katie, met up again! It's time for a party...

What the cats do when they unite? Right, they have a party. Since they wanted to have as much fun as possible, they invited all their friends. Now $n$ cats are at the party, sitting in a circle and eating soup. The rules are simple: anyone having finished their soup leaves the circle.

Katie suddenly notices that whenever a cat leaves, the place where she was sitting becomes an empty space, which means the circle is divided into smaller continuous groups of cats sitting next to each other. At the moment Katie observes, there are $m$ cats who left the circle. This raises a question for Katie: what is the maximum possible number of groups the circle is divided into at the moment?

Could you help her with this curiosity?

You can see the examples and their descriptions with pictures in the "Note" section.


-----Input-----

The only line contains two integers $n$ and $m$ ($2 \leq n \leq 1000$, $0 \leq m \leq n$) — the initial number of cats at the party and the number of cats who left the circle at the moment Katie observes, respectively.


-----Output-----

Print a single integer — the maximum number of groups of cats at the moment Katie observes.


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

Output
3

Input
6 2

Output
2

Input
3 0

Output
1

Input
2 2

Output
0



-----Note-----

In the first example, originally there are $7$ cats sitting as shown below, creating a single group: [Image] 

At the observed moment, $4$ cats have left the table. Suppose the cats $2$, $3$, $5$ and $7$ have left, then there are $3$ groups remaining. It is possible to show that it is the maximum possible number of groups remaining. [Image] 

In the second example, there are $6$ cats sitting as shown below: [Image] 

At the observed moment, $2$ cats have left the table. Suppose the cats numbered $3$ and $6$ left, then there will be $2$ groups remaining ($\{1, 2\}$ and $\{4, 5\}$). It is impossible to have more than $2$ groups of cats remaining. [Image] 

In the third example, no cats have left, so there is $1$ group consisting of all cats.

In the fourth example, all cats have left the circle, so there are $0$ groups.
user: Polycarp urgently needs a shovel! He comes to the shop and chooses an appropriate one. The shovel that Policarp chooses is sold for k burles. Assume that there is an unlimited number of such shovels in the shop.

In his pocket Polycarp has an unlimited number of "10-burle coins" and exactly one coin of r burles (1 ≤ r ≤ 9).

What is the minimum number of shovels Polycarp has to buy so that he can pay for the purchase without any change? It is obvious that he can pay for 10 shovels without any change (by paying the requied amount of 10-burle coins and not using the coin of r burles). But perhaps he can buy fewer shovels and pay without any change. Note that Polycarp should buy at least one shovel.


-----Input-----

The single line of input contains two integers k and r (1 ≤ k ≤ 1000, 1 ≤ r ≤ 9) — the price of one shovel and the denomination of the coin in Polycarp's pocket that is different from "10-burle coins". 

Remember that he has an unlimited number of coins in the denomination of 10, that is, Polycarp has enough money to buy any number of shovels.


-----Output-----

Print the required minimum number of shovels Polycarp has to buy so that he can pay for them without any change. 


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

Output
9

Input
237 7

Output
1

Input
15 2

Output
2



-----Note-----

In the first example Polycarp can buy 9 shovels and pay 9·117 = 1053 burles. Indeed, he can pay this sum by using 10-burle coins and one 3-burle coin. He can't buy fewer shovels without any change.

In the second example it is enough for Polycarp to buy one shovel.

In the third example Polycarp should buy two shovels and pay 2·15 = 30 burles. It is obvious that he can pay this sum without any change.
user: Hongcow likes solving puzzles.

One day, Hongcow finds two identical puzzle pieces, with the instructions "make a rectangle" next to them. The pieces can be described by an n by m grid of characters, where the character 'X' denotes a part of the puzzle and '.' denotes an empty part of the grid. It is guaranteed that the puzzle pieces are one 4-connected piece. See the input format and samples for the exact details on how a jigsaw piece will be specified.

The puzzle pieces are very heavy, so Hongcow cannot rotate or flip the puzzle pieces. However, he is allowed to move them in any directions. The puzzle pieces also cannot overlap.

You are given as input the description of one of the pieces. Determine if it is possible to make a rectangle from two identical copies of the given input. The rectangle should be solid, i.e. there should be no empty holes inside it or on its border. Keep in mind that Hongcow is not allowed to flip or rotate pieces and they cannot overlap, i.e. no two 'X' from different pieces can share the same position.


-----Input-----

The first line of input will contain two integers n and m (1 ≤ n, m ≤ 500), the dimensions of the puzzle piece.

The next n lines will describe the jigsaw piece. Each line will have length m and will consist of characters '.' and 'X' only. 'X' corresponds to a part of the puzzle piece, '.' is an empty space.

It is guaranteed there is at least one 'X' character in the input and that the 'X' characters form a 4-connected region.


-----Output-----

Output "YES" if it is possible for Hongcow to make a rectangle. Output "NO" otherwise.


-----Examples-----
Input
2 3
XXX
XXX

Output
YES

Input
2 2
.X
XX

Output
NO

Input
5 5
.....
..X..
.....
.....
.....

Output
YES



-----Note-----

For the first sample, one example of a rectangle we can form is as follows 

111222

111222



For the second sample, it is impossible to put two of those pieces without rotating or flipping to form a rectangle.

In the third sample, we can shift the first tile by one to the right, and then compose the following rectangle: 

.....

..XX.

.....

.....

.....
user: There are three points marked on the coordinate plane. The goal is to make a simple polyline, without self-intersections and self-touches, such that it passes through all these points. Also, the polyline must consist of only segments parallel to the coordinate axes. You are to find the minimum number of segments this polyline may consist of.


-----Input-----

Each of the three lines of the input contains two integers. The i-th line contains integers x_{i} and y_{i} ( - 10^9 ≤ x_{i}, y_{i} ≤ 10^9) — the coordinates of the i-th point. It is guaranteed that all points are distinct.


-----Output-----

Print a single number — the minimum possible number of segments of the polyline.


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

Output
1

Input
-1 -1
-1 3
4 3

Output
2

Input
1 1
2 3
3 2

Output
3



-----Note-----

The variant of the polyline in the first sample: [Image] The variant of the polyline in the second sample: $1$ The variant of the polyline in the third sample: $\because$
user: An undirected graph is called k-regular, if the degrees of all its vertices are equal k. An edge of a connected graph is called a bridge, if after removing it the graph is being split into two connected components.

Build a connected undirected k-regular graph containing at least one bridge, or else state that such graph doesn't exist.


-----Input-----

The single line of the input contains integer k (1 ≤ k ≤ 100) — the required degree of the vertices of the regular graph.


-----Output-----

Print "NO" (without quotes), if such graph doesn't exist. 

Otherwise, print "YES" in the first line and the description of any suitable graph in the next lines.

The description of the made graph must start with numbers n and m — the number of vertices and edges respectively. 

Each of the next m lines must contain two integers, a and b (1 ≤ a, b ≤ n, a ≠ b), that mean that there is an edge connecting the vertices a and b. A graph shouldn't contain multiple edges and edges that lead from a vertex to itself. A graph must be connected, the degrees of all vertices of the graph must be equal k. At least one edge of the graph must be a bridge. You can print the edges of the graph in any order. You can print the ends of each edge in any order.

The constructed graph must contain at most 10^6 vertices and 10^6 edges (it is guaranteed that if at least one graph that meets the requirements exists, then there also exists the graph with at most 10^6 vertices and at most 10^6 edges). 


-----Examples-----
Input
1

Output
YES
2 1
1 2



-----Note-----

In the sample from the statement there is a suitable graph consisting of two vertices, connected by a single edge.
user: You are given two strings $s$ and $t$, both consisting only of lowercase Latin letters.

The substring $s[l..r]$ is the string which is obtained by taking characters $s_l, s_{l + 1}, \dots, s_r$ without changing the order.

Each of the occurrences of string $a$ in a string $b$ is a position $i$ ($1 \le i \le |b| - |a| + 1$) such that $b[i..i + |a| - 1] = a$ ($|a|$ is the length of string $a$).

You are asked $q$ queries: for the $i$-th query you are required to calculate the number of occurrences of string $t$ in a substring $s[l_i..r_i]$.


-----Input-----

The first line contains three integer numbers $n$, $m$ and $q$ ($1 \le n, m \le 10^3$, $1 \le q \le 10^5$) — the length of string $s$, the length of string $t$ and the number of queries, respectively.

The second line is a string $s$ ($|s| = n$), consisting only of lowercase Latin letters.

The third line is a string $t$ ($|t| = m$), consisting only of lowercase Latin letters.

Each of the next $q$ lines contains two integer numbers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$) — the arguments for the $i$-th query.


-----Output-----

Print $q$ lines — the $i$-th line should contain the answer to the $i$-th query, that is the number of occurrences of string $t$ in a substring $s[l_i..r_i]$.


-----Examples-----
Input
10 3 4
codeforces
for
1 3
3 10
5 6
5 7

Output
0
1
0
1

Input
15 2 3
abacabadabacaba
ba
1 15
3 4
2 14

Output
4
0
3

Input
3 5 2
aaa
baaab
1 3
1 1

Output
0
0



-----Note-----

In the first example the queries are substrings: "cod", "deforces", "fo" and "for", respectively.
user: Quite recently a creative student Lesha had a lecture on trees. After the lecture Lesha was inspired and came up with the tree of his own which he called a k-tree.

A k-tree is an infinite rooted tree where:

  each vertex has exactly k children;  each edge has some weight;  if we look at the edges that goes from some vertex to its children (exactly k edges), then their weights will equal 1, 2, 3, ..., k. 

The picture below shows a part of a 3-tree.

 

 [Image]

    As soon as Dima, a good friend of Lesha, found out about the tree, he immediately wondered: "How many paths of total weight n (the sum of all weights of the edges in the path) are there, starting from the root of a k-tree and also containing at least one edge of weight at least d?".

Help Dima find an answer to his question. As the number of ways can be rather large, print it modulo 1000000007 (10^9 + 7). 


-----Input-----

A single line contains three space-separated integers: n, k and d (1 ≤ n, k ≤ 100; 1 ≤ d ≤ k).


-----Output-----

Print a single integer — the answer to the problem modulo 1000000007 (10^9 + 7). 


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

Output
3

Input
3 3 3

Output
1

Input
4 3 2

Output
6

Input
4 5 2

Output
7
user: Recently Adaltik discovered japanese crosswords. Japanese crossword is a picture, represented as a table sized a × b squares, and each square is colored white or black. There are integers to the left of the rows and to the top of the columns, encrypting the corresponding row or column. The number of integers represents how many groups of black squares there are in corresponding row or column, and the integers themselves represents the number of consecutive black squares in corresponding group (you can find more detailed explanation in Wikipedia https://en.wikipedia.org/wiki/Japanese_crossword).

Adaltik decided that the general case of japanese crossword is too complicated and drew a row consisting of n squares (e.g. japanese crossword sized 1 × n), which he wants to encrypt in the same way as in japanese crossword. [Image] The example of encrypting of a single row of japanese crossword. 

Help Adaltik find the numbers encrypting the row he drew.


-----Input-----

The first line of the input contains a single integer n (1 ≤ n ≤ 100) — the length of the row. The second line of the input contains a single string consisting of n characters 'B' or 'W', ('B' corresponds to black square, 'W' — to white square in the row that Adaltik drew).


-----Output-----

The first line should contain a single integer k — the number of integers encrypting the row, e.g. the number of groups of black squares in the row.

The second line should contain k integers, encrypting the row, e.g. corresponding to sizes of groups of consecutive black squares in the order from left to right.


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

Output
1
2 
Input
5
BWBWB

Output
3
1 1 1 
Input
4
WWWW

Output
0

Input
4
BBBB

Output
1
4 
Input
13
WBBBBWWBWBBBW

Output
3
4 1 3 


-----Note-----

The last sample case correspond to the picture in the statement.
user: A TV show called "Guess a number!" is gathering popularity. The whole Berland, the old and the young, are watching the show.

The rules are simple. The host thinks of an integer y and the participants guess it by asking questions to the host. There are four types of acceptable questions:  Is it true that y is strictly larger than number x?  Is it true that y is strictly smaller than number x?  Is it true that y is larger than or equal to number x?  Is it true that y is smaller than or equal to number x? 

On each question the host answers truthfully, "yes" or "no".

Given the sequence of questions and answers, find any integer value of y that meets the criteria of all answers. If there isn't such value, print "Impossible".


-----Input-----

The first line of the input contains a single integer n (1 ≤ n ≤ 10000) — the number of questions (and answers). Next n lines each contain one question and one answer to it. The format of each line is like that: "sign x answer", where the sign is:  ">" (for the first type queries),  "<" (for the second type queries),  ">=" (for the third type queries),  "<=" (for the fourth type queries). 

All values of x are integer and meet the inequation  - 10^9 ≤ x ≤ 10^9. The answer is an English letter "Y" (for "yes") or "N" (for "no").

Consequtive elements in lines are separated by a single space.


-----Output-----

Print any of such integers y, that the answers to all the queries are correct. The printed number y must meet the inequation  - 2·10^9 ≤ y ≤ 2·10^9. If there are many answers, print any of them. If such value doesn't exist, print word "Impossible" (without the quotes).


-----Examples-----
Input
4
>= 1 Y
< 3 N
<= -3 N
> 55 N

Output
17

Input
2
> 100 Y
< -100 Y

Output
Impossible
user: You are given $a$ uppercase Latin letters 'A' and $b$ letters 'B'.

The period of the string is the smallest such positive integer $k$ that $s_i = s_{i~mod~k}$ ($0$-indexed) for each $i$. Note that this implies that $k$ won't always divide $a+b = |s|$.

For example, the period of string "ABAABAA" is $3$, the period of "AAAA" is $1$, and the period of "AABBB" is $5$.

Find the number of different periods over all possible strings with $a$ letters 'A' and $b$ letters 'B'.


-----Input-----

The first line contains two integers $a$ and $b$ ($1 \le a, b \le 10^9$) — the number of letters 'A' and 'B', respectively.


-----Output-----

Print the number of different periods over all possible strings with $a$ letters 'A' and $b$ letters 'B'.


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

Output
4

Input
5 3

Output
5



-----Note-----

All the possible periods for the first example:   $3$ "BBABBA"  $4$ "BBAABB"  $5$ "BBBAAB"  $6$ "AABBBB" 

All the possible periods for the second example:   $3$ "BAABAABA"  $5$ "BAABABAA"  $6$ "BABAAABA"  $7$ "BAABAAAB"  $8$ "AAAAABBB" 

Note that these are not the only possible strings for the given periods.