meetforever/GRPO_CL huggingface dataset:
user: The preferred way to generate user login in Polygon is to concatenate a prefix of the user's first name and a prefix of their last name, in that order. Each prefix must be non-empty, and any of the prefixes can be the full name. Typically there are multiple possible logins for each person.

You are given the first and the last name of a user. Return the alphabetically earliest login they can get (regardless of other potential Polygon users).

As a reminder, a prefix of a string s is its substring which occurs at the beginning of s: "a", "ab", "abc" etc. are prefixes of string "{abcdef}" but "b" and 'bc" are not. A string a is alphabetically earlier than a string b, if a is a prefix of b, or a and b coincide up to some position, and then a has a letter that is alphabetically earlier than the corresponding letter in b: "a" and "ab" are alphabetically earlier than "ac" but "b" and "ba" are alphabetically later than "ac".


-----Input-----

The input consists of a single line containing two space-separated strings: the first and the last names. Each character of each string is a lowercase English letter. The length of each string is between 1 and 10, inclusive. 


-----Output-----

Output a single string — alphabetically earliest possible login formed from these names. The output should be given in lowercase as well.


-----Examples-----
Input
harry potter

Output
hap

Input
tom riddle

Output
tomr
user: A sequence of square brackets is regular if by inserting symbols "+" and "1" into it, you can get a regular mathematical expression from it. For example, sequences "[[]][]", "[]" and "[[][[]]]" — are regular, at the same time "][", "[[]" and "[[]]][" — are irregular. 

Draw the given sequence using a minimalistic pseudographics in the strip of the lowest possible height — use symbols '+', '-' and '|'. For example, the sequence "[[][]][]" should be represented as: 

+-        -++- -+    

|+- -++- -+||   |

||   ||   |||   |

|+- -++- -+||   |

+-        -++- -+



Each bracket should be represented with the hepl of one or more symbols '|' (the vertical part) and symbols '+' and '-' as on the example which is given above.

Brackets should be drawn without spaces one by one, only dividing pairs of consecutive pairwise brackets with a single-space bar (so that the two brackets do not visually merge into one symbol). The image should have the minimum possible height. 

The enclosed bracket is always smaller than the surrounding bracket, but each bracket separately strives to maximize the height of the image. So the pair of final brackets in the example above occupies the entire height of the image.

Study carefully the examples below, they adequately explain the condition of the problem. Pay attention that in this problem the answer (the image) is unique. 


-----Input-----

The first line contains an even integer n (2 ≤ n ≤ 100) — the length of the sequence of brackets.

The second line contains the sequence of brackets — these are n symbols "[" and "]". It is guaranteed that the given sequence of brackets is regular. 


-----Output-----

Print the drawn bracket sequence in the format which is given in the condition. Don't print extra (unnecessary) spaces. 


-----Examples-----
Input
8
[[][]][]

Output
+-        -++- -+
|+- -++- -+||   |
||   ||   |||   |
|+- -++- -+||   |
+-        -++- -+

Input
6
[[[]]]

Output
+-     -+
|+-   -+|
||+- -+||
|||   |||
||+- -+||
|+-   -+|
+-     -+

Input
6
[[][]]

Output
+-        -+
|+- -++- -+|
||   ||   ||
|+- -++- -+|
+-        -+

Input
2
[]

Output
+- -+
|   |
+- -+

Input
4
[][]

Output
+- -++- -+
|   ||   |
+- -++- -+
user: Piegirl got bored with binary, decimal and other integer based counting systems. Recently she discovered some interesting properties about number $q = \frac{\sqrt{5} + 1}{2}$, in particular that q^2 = q + 1, and she thinks it would make a good base for her new unique system. She called it "golden system". In golden system the number is a non-empty string containing 0's and 1's as digits. The decimal value of expression a_0a_1...a_{n} equals to $\sum_{i = 0}^{n} a_{i} \cdot q^{n - i}$.

Soon Piegirl found out that this system doesn't have same properties that integer base systems do and some operations can not be performed on it. She wasn't able to come up with a fast way of comparing two numbers. She is asking for your help.

Given two numbers written in golden system notation, determine which of them has larger decimal value.


-----Input-----

Input consists of two lines — one for each number. Each line contains non-empty string consisting of '0' and '1' characters. The length of each string does not exceed 100000.


-----Output-----

Print ">" if the first number is larger, "<" if it is smaller and "=" if they are equal.


-----Examples-----
Input
1000
111

Output
<

Input
00100
11

Output
=

Input
110
101

Output
>



-----Note-----

In the first example first number equals to $((\sqrt{5} + 1) / 2)^{3} \approx 1.618033988^{3} \approx 4.236$, while second number is approximately 1.618033988^2 + 1.618033988 + 1 ≈ 5.236, which is clearly a bigger number.

In the second example numbers are equal. Each of them is  ≈ 2.618.
user: You took a peek on Thanos wearing Infinity Gauntlet. In the Gauntlet there is a place for six Infinity Gems:  the Power Gem of purple color,  the Time Gem of green color,  the Space Gem of blue color,  the Soul Gem of orange color,  the Reality Gem of red color,  the Mind Gem of yellow color. 

Using colors of Gems you saw in the Gauntlet determine the names of absent Gems.


-----Input-----

In the first line of input there is one integer $n$ ($0 \le n \le 6$) — the number of Gems in Infinity Gauntlet.

In next $n$ lines there are colors of Gems you saw. Words used for colors are: purple, green, blue, orange, red, yellow. It is guaranteed that all the colors are distinct. All colors are given in lowercase English letters.


-----Output-----

In the first line output one integer $m$ ($0 \le m \le 6$) — the number of absent Gems.

Then in $m$ lines print the names of absent Gems, each on its own line. Words used for names are: Power, Time, Space, Soul, Reality, Mind. Names can be printed in any order. Keep the first letter uppercase, others lowercase.


-----Examples-----
Input
4
red
purple
yellow
orange

Output
2
Space
Time

Input
0

Output
6
Time
Mind
Soul
Power
Reality
Space



-----Note-----

In the first sample Thanos already has Reality, Power, Mind and Soul Gems, so he needs two more: Time and Space.

In the second sample Thanos doesn't have any Gems, so he needs all six.
user: The last stage of Football World Cup is played using the play-off system.

There are n teams left in this stage, they are enumerated from 1 to n. Several rounds are held, in each round the remaining teams are sorted in the order of their ids, then the first in this order plays with the second, the third — with the fourth, the fifth — with the sixth, and so on. It is guaranteed that in each round there is even number of teams. The winner of each game advances to the next round, the loser is eliminated from the tournament, there are no draws. In the last round there is the only game with two remaining teams: the round is called the Final, the winner is called the champion, and the tournament is over.

Arkady wants his two favorite teams to play in the Final. Unfortunately, the team ids are already determined, and it may happen that it is impossible for teams to meet in the Final, because they are to meet in some earlier stage, if they are strong enough. Determine, in which round the teams with ids a and b can meet.


-----Input-----

The only line contains three integers n, a and b (2 ≤ n ≤ 256, 1 ≤ a, b ≤ n) — the total number of teams, and the ids of the teams that Arkady is interested in. 

It is guaranteed that n is such that in each round an even number of team advance, and that a and b are not equal.


-----Output-----

In the only line print "Final!" (without quotes), if teams a and b can meet in the Final.

Otherwise, print a single integer — the number of the round in which teams a and b can meet. The round are enumerated from 1.


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

Output
1

Input
8 2 6

Output
Final!

Input
8 7 5

Output
2



-----Note-----

In the first example teams 1 and 2 meet in the first round.

In the second example teams 2 and 6 can only meet in the third round, which is the Final, if they win all their opponents in earlier rounds.

In the third example the teams with ids 7 and 5 can meet in the second round, if they win their opponents in the first round.
user: Pavel cooks barbecue. There are n skewers, they lay on a brazier in a row, each on one of n positions. Pavel wants each skewer to be cooked some time in every of n positions in two directions: in the one it was directed originally and in the reversed direction.

Pavel has a plan: a permutation p and a sequence b_1, b_2, ..., b_{n}, consisting of zeros and ones. Each second Pavel move skewer on position i to position p_{i}, and if b_{i} equals 1 then he reverses it. So he hope that every skewer will visit every position in both directions.

Unfortunately, not every pair of permutation p and sequence b suits Pavel. What is the minimum total number of elements in the given permutation p and the given sequence b he needs to change so that every skewer will visit each of 2n placements? Note that after changing the permutation should remain a permutation as well.

There is no problem for Pavel, if some skewer visits some of the placements several times before he ends to cook. In other words, a permutation p and a sequence b suit him if there is an integer k (k ≥ 2n), so that after k seconds each skewer visits each of the 2n placements.

It can be shown that some suitable pair of permutation p and sequence b exists for any n.


-----Input-----

The first line contain the integer n (1 ≤ n ≤ 2·10^5) — the number of skewers.

The second line contains a sequence of integers p_1, p_2, ..., p_{n} (1 ≤ p_{i} ≤ n) — the permutation, according to which Pavel wants to move the skewers.

The third line contains a sequence b_1, b_2, ..., b_{n} consisting of zeros and ones, according to which Pavel wants to reverse the skewers.


-----Output-----

Print single integer — the minimum total number of elements in the given permutation p and the given sequence b he needs to change so that every skewer will visit each of 2n placements.


-----Examples-----
Input
4
4 3 2 1
0 1 1 1

Output
2

Input
3
2 3 1
0 0 0

Output
1



-----Note-----

In the first example Pavel can change the permutation to 4, 3, 1, 2.

In the second example Pavel can change any element of b to 1.
user: The on-board computer on Polycarp's car measured that the car speed at the beginning of some section of the path equals v_1 meters per second, and in the end it is v_2 meters per second. We know that this section of the route took exactly t seconds to pass.

Assuming that at each of the seconds the speed is constant, and between seconds the speed can change at most by d meters per second in absolute value (i.e., the difference in the speed of any two adjacent seconds does not exceed d in absolute value), find the maximum possible length of the path section in meters.


-----Input-----

The first line contains two integers v_1 and v_2 (1 ≤ v_1, v_2 ≤ 100) — the speeds in meters per second at the beginning of the segment and at the end of the segment, respectively.

The second line contains two integers t (2 ≤ t ≤ 100) — the time when the car moves along the segment in seconds, d (0 ≤ d ≤ 10) — the maximum value of the speed change between adjacent seconds.

It is guaranteed that there is a way to complete the segment so that:  the speed in the first second equals v_1,  the speed in the last second equals v_2,  the absolute value of difference of speeds between any two adjacent seconds doesn't exceed d. 


-----Output-----

Print the maximum possible length of the path segment in meters. 


-----Examples-----
Input
5 6
4 2

Output
26
Input
10 10
10 0

Output
100


-----Note-----

In the first sample the sequence of speeds of Polycarpus' car can look as follows: 5, 7, 8, 6. Thus, the total path is 5 + 7 + 8 + 6 = 26 meters.

In the second sample, as d = 0, the car covers the whole segment at constant speed v = 10. In t = 10 seconds it covers the distance of 100 meters.
user: There are N camels numbered 1 through N.
The weight of Camel i is w_i.
You will arrange the camels in a line and make them cross a bridge consisting of M parts.
Before they cross the bridge, you can choose their order in the line - it does not have to be Camel 1, 2, \ldots, N from front to back - and specify the distance between each adjacent pair of camels to be any non-negative real number.
The camels will keep the specified distances between them while crossing the bridge.
The i-th part of the bridge has length l_i and weight capacity v_i.
If the sum of the weights of camels inside a part (excluding the endpoints) exceeds v_i, the bridge will collapse.
Determine whether it is possible to make the camels cross the bridge without it collapsing. If it is possible, find the minimum possible distance between the first and last camels in the line in such a case.
It can be proved that the answer is always an integer, so print an integer.

-----Constraints-----
 - All values in input are integers.
 - 2 \leq N \leq 8
 - 1 \leq M \leq 10^5
 - 1 \leq w_i,l_i,v_i \leq 10^8

-----Input-----
Input is given from Standard Input in the following format:
N M
w_1 w_2 \cdots w_N
l_1 v_1
\vdots
l_M v_M

-----Output-----
If the bridge will unavoidably collapse when the camels cross the bridge, print -1.
Otherwise, print the minimum possible distance between the first and last camels in the line when the camels cross the bridge without it collapsing.

-----Sample Input-----
3 2
1 4 2
10 4
2 6

-----Sample Output-----
10

 - It is possible to make the camels cross the bridge without it collapsing by, for example, arranging them in the order 1, 3, 2 from front to back, and setting the distances between them to be 0, 10.
 - For Part 1 of the bridge, there are moments when only Camel 1 and 3 are inside the part and moments when only Camel 2 is inside the part. In both cases, the sum of the weights of camels does not exceed 4 - the weight capacity of Part 1 - so there is no collapse.
 - For Part 2 of the bridge, there are moments when only Camel 1 and 3 are inside the part and moments when only Camel 2 is inside the part. In both cases, the sum of the weights of camels does not exceed 6 - the weight capacity of Part 2 - so there is no collapse.
 - Note that the distance between two camels may be 0 and that camels on endpoints of a part are not considered to be inside the part.
user: Even if the world is full of counterfeits, I still regard it as wonderful.

Pile up herbs and incense, and arise again from the flames and ashes of its predecessor — as is known to many, the phoenix does it like this.

The phoenix has a rather long lifespan, and reincarnates itself once every a! years. Here a! denotes the factorial of integer a, that is, a! = 1 × 2 × ... × a. Specifically, 0! = 1.

Koyomi doesn't care much about this, but before he gets into another mess with oddities, he is interested in the number of times the phoenix will reincarnate in a timespan of b! years, that is, [Image]. Note that when b ≥ a this value is always integer.

As the answer can be quite large, it would be enough for Koyomi just to know the last digit of the answer in decimal representation. And you're here to provide Koyomi with this knowledge.


-----Input-----

The first and only line of input contains two space-separated integers a and b (0 ≤ a ≤ b ≤ 10^18).


-----Output-----

Output one line containing a single decimal digit — the last digit of the value that interests Koyomi.


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

Output
2

Input
0 10

Output
0

Input
107 109

Output
2



-----Note-----

In the first example, the last digit of $\frac{4 !}{2 !} = 12$ is 2;

In the second example, the last digit of $\frac{10 !}{0 !} = 3628800$ is 0;

In the third example, the last digit of $\frac{109 !}{107 !} = 11772$ is 2.
user: A frog lives on the axis Ox and needs to reach home which is in the point n. She starts from the point 1. The frog can jump to the right at a distance not more than d. So, after she jumped from the point x she can reach the point x + a, where a is an integer from 1 to d.

For each point from 1 to n is known if there is a lily flower in it. The frog can jump only in points with a lilies. Guaranteed that there are lilies in the points 1 and n.

Determine the minimal number of jumps that the frog needs to reach home which is in the point n from the point 1. Consider that initially the frog is in the point 1. If the frog can not reach home, print -1.


-----Input-----

The first line contains two integers n and d (2 ≤ n ≤ 100, 1 ≤ d ≤ n - 1) — the point, which the frog wants to reach, and the maximal length of the frog jump.

The second line contains a string s of length n, consisting of zeros and ones. If a character of the string s equals to zero, then in the corresponding point there is no lily flower. In the other case, in the corresponding point there is a lily flower. Guaranteed that the first and the last characters of the string s equal to one.


-----Output-----

If the frog can not reach the home, print -1.

In the other case, print the minimal number of jumps that the frog needs to reach the home which is in the point n from the point 1.


-----Examples-----
Input
8 4
10010101

Output
2

Input
4 2
1001

Output
-1

Input
8 4
11100101

Output
3

Input
12 3
101111100101

Output
4



-----Note-----

In the first example the from can reach home in two jumps: the first jump from the point 1 to the point 4 (the length of the jump is three), and the second jump from the point 4 to the point 8 (the length of the jump is four).

In the second example the frog can not reach home, because to make it she need to jump on a distance three, but the maximum length of her jump equals to two.
user: PolandBall is a young, clever Ball. He is interested in prime numbers. He has stated a following hypothesis: "There exists such a positive integer n that for each positive integer m number n·m + 1 is a prime number".

Unfortunately, PolandBall is not experienced yet and doesn't know that his hypothesis is incorrect. Could you prove it wrong? Write a program that finds a counterexample for any n.


-----Input-----

The only number in the input is n (1 ≤ n ≤ 1000) — number from the PolandBall's hypothesis. 


-----Output-----

Output such m that n·m + 1 is not a prime number. Your answer will be considered correct if you output any suitable m such that 1 ≤ m ≤ 10^3. It is guaranteed the the answer exists.


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

Output
1
Input
4

Output
2


-----Note-----

A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself.

For the first sample testcase, 3·1 + 1 = 4. We can output 1.

In the second sample testcase, 4·1 + 1 = 5. We cannot output 1 because 5 is prime. However, m = 2 is okay since 4·2 + 1 = 9, which is not a prime number.
user: Kolya is developing an economy simulator game. His most favourite part of the development process is in-game testing. Once he was entertained by the testing so much, that he found out his game-coin score become equal to 0.

Kolya remembers that at the beginning of the game his game-coin score was equal to n and that he have bought only some houses (for 1 234 567 game-coins each), cars (for 123 456 game-coins each) and computers (for 1 234 game-coins each).

Kolya is now interested, whether he could have spent all of his initial n game-coins buying only houses, cars and computers or there is a bug in the game. Formally, is there a triple of non-negative integers a, b and c such that a × 1 234 567 + b × 123 456 + c × 1 234 = n?

Please help Kolya answer this question.


-----Input-----

The first line of the input contains a single integer n (1 ≤ n ≤ 10^9) — Kolya's initial game-coin score.


-----Output-----

Print "YES" (without quotes) if it's possible that Kolya spent all of his initial n coins buying only houses, cars and computers. Otherwise print "NO" (without quotes).


-----Examples-----
Input
1359257

Output
YES
Input
17851817

Output
NO


-----Note-----

In the first sample, one of the possible solutions is to buy one house, one car and one computer, spending 1 234 567 + 123 456 + 1234 = 1 359 257 game-coins in total.
user: The teacher gave Anton a large geometry homework, but he didn't do it (as usual) as he participated in a regular round on Codeforces. In the task he was given a set of n lines defined by the equations y = k_{i}·x + b_{i}. It was necessary to determine whether there is at least one point of intersection of two of these lines, that lays strictly inside the strip between x_1 < x_2. In other words, is it true that there are 1 ≤ i < j ≤ n and x', y', such that:   y' = k_{i} * x' + b_{i}, that is, point (x', y') belongs to the line number i;  y' = k_{j} * x' + b_{j}, that is, point (x', y') belongs to the line number j;  x_1 < x' < x_2, that is, point (x', y') lies inside the strip bounded by x_1 < x_2. 

You can't leave Anton in trouble, can you? Write a program that solves the given task.


-----Input-----

The first line of the input contains an integer n (2 ≤ n ≤ 100 000) — the number of lines in the task given to Anton. The second line contains integers x_1 and x_2 ( - 1 000 000 ≤ x_1 < x_2 ≤ 1 000 000) defining the strip inside which you need to find a point of intersection of at least two lines.

The following n lines contain integers k_{i}, b_{i} ( - 1 000 000 ≤ k_{i}, b_{i} ≤ 1 000 000) — the descriptions of the lines. It is guaranteed that all lines are pairwise distinct, that is, for any two i ≠ j it is true that either k_{i} ≠ k_{j}, or b_{i} ≠ b_{j}.


-----Output-----

Print "Yes" (without quotes), if there is at least one intersection of two distinct lines, located strictly inside the strip. Otherwise print "No" (without quotes).


-----Examples-----
Input
4
1 2
1 2
1 0
0 1
0 2

Output
NO
Input
2
1 3
1 0
-1 3

Output
YES
Input
2
1 3
1 0
0 2

Output
YES
Input
2
1 3
1 0
0 3

Output
NO


-----Note-----

In the first sample there are intersections located on the border of the strip, but there are no intersections located strictly inside it. [Image]
user: Let's define a split of $n$ as a nonincreasing sequence of positive integers, the sum of which is $n$. 

For example, the following sequences are splits of $8$: $[4, 4]$, $[3, 3, 2]$, $[2, 2, 1, 1, 1, 1]$, $[5, 2, 1]$.

The following sequences aren't splits of $8$: $[1, 7]$, $[5, 4]$, $[11, -3]$, $[1, 1, 4, 1, 1]$.

The weight of a split is the number of elements in the split that are equal to the first element. For example, the weight of the split $[1, 1, 1, 1, 1]$ is $5$, the weight of the split $[5, 5, 3, 3, 3]$ is $2$ and the weight of the split $[9]$ equals $1$.

For a given $n$, find out the number of different weights of its splits.


-----Input-----

The first line contains one integer $n$ ($1 \leq n \leq 10^9$).


-----Output-----

Output one integer — the answer to the problem.


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

Output
4

Input
8

Output
5

Input
9

Output
5



-----Note-----

In the first sample, there are following possible weights of splits of $7$:

Weight 1: [$\textbf 7$] 

Weight 2: [$\textbf 3$, $\textbf 3$, 1] 

Weight 3: [$\textbf 2$, $\textbf 2$, $\textbf 2$, 1] 

Weight 7: [$\textbf 1$, $\textbf 1$, $\textbf 1$, $\textbf 1$, $\textbf 1$, $\textbf 1$, $\textbf 1$]