vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
There are n employees working in company "X" (let's number them from 1 to n for convenience). Initially the employees didn't have any relationships among each other. On each of m next days one of the following events took place:  either employee y became the boss of employee x (at that, employee x didn't have a boss before);  or employee x gets a packet of documents and signs them; then he gives the packet to his boss. The boss signs the documents and gives them to his boss and so on (the last person to sign the documents sends them to the archive);  or comes a request of type "determine whether employee x signs certain documents". 

Your task is to write a program that will, given the events, answer the queries of the described type. At that, it is guaranteed that throughout the whole working time the company didn't have cyclic dependencies.


-----Input-----

The first line contains two integers n and m (1 ≤ n, m ≤ 10^5) — the number of employees and the number of events. 

Each of the next m lines contains the description of one event (the events are given in the chronological order). The first number of the line determines the type of event t (1 ≤ t ≤ 3).   If t = 1, then next follow two integers x and y (1 ≤ x, y ≤ n) — numbers of the company employees. It is guaranteed that employee x doesn't have the boss currently.  If t = 2, then next follow integer x (1 ≤ x ≤ n) — the number of the employee who got a document packet.  If t = 3, then next follow two integers x and i (1 ≤ x ≤ n; 1 ≤ i ≤ [number of packets that have already been given]) — the employee and the number of the document packet for which you need to find out information. The document packets are numbered started from 1 in the chronological order. 

It is guaranteed that the input has at least one query of the third type.


-----Output-----

For each query of the third type print "YES" if the employee signed the document package and "NO" otherwise. Print all the words without the quotes.


-----Examples-----
Input
4 9
1 4 3
2 4
3 3 1
1 2 3
2 2
3 1 2
1 3 1
2 2
3 1 3

Output
YES
NO
YES

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Your car is old, it breaks easily. The shock absorbers are gone and you think it can handle about 15 more bumps before it dies totally.

Unfortunately for you, your drive is very bumpy! Given a string showing either flat road ("\_") or bumps ("n"), work out if you make it home safely. 15 bumps or under, return "Woohoo!", over 15 bumps return "Car Dead".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You can perform the following operations on the string, $a$:  

Capitalize zero or more of $a$'s lowercase letters.
Delete all of the remaining lowercase letters in $a$.

Given two strings, $a$ and $\boldsymbol{b}$, determine if it's possible to make $a$ equal to $\boldsymbol{b}$ as described. If so, print YES on a new line.  Otherwise, print NO.

For example, given $a=\textbf{AbcDE}$ and $b=\textbf{ABDE}$, in $a$ we can convert $\mbox{b}$ and delete $\textbf{C}$ to match $\boldsymbol{b}$.  If $a=\textbf{AbcDE}$ and $b=\textbf{AFDE}$, matching is not possible because letters may only be capitalized or discarded, not changed.

Function Description

Complete the function $abbreviation$ in the editor below.  It must return either $YES$ or $\mathrm{NO}$.

abbreviation has the following parameter(s):

a: the string to modify  
b: the string to match  

Input Format

The first line contains a single integer $\textit{q}$, the number of queries. 

Each of the next $\textit{q}$ pairs of lines is as follows: 

- The first line of each query contains a single string, $a$. 

- The second line of each query contains a single string, $\boldsymbol{b}$.  

Constraints

$1\leq q\leq10$  
$1\le|a|,|b|\le1000$
String $a$ consists only of uppercase and lowercase English letters, ascii[A-Za-z].
String $\boldsymbol{b}$ consists only of uppercase English letters, ascii[A-Z].

Output Format

For each query, print YES on a new line if it's possible to make string $a$ equal to string $\boldsymbol{b}$.  Otherwise, print NO.

Sample Input
1
daBcd
ABC

Sample Output
YES

Explanation

We have $\boldsymbol{a}=$ daBcd and $b=$ ABC. We perform the following operation:

Capitalize the letters a and c in $\boldsymbol{\alpha}$ so that $\boldsymbol{a}=$ dABCd. 
Delete all the remaining lowercase letters in $a$ so that $\boldsymbol{a}=$ ABC. 

Because we were able to successfully convert $a$ to $\boldsymbol{b}$, we print YES on a new line.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string s, return the maximum number of ocurrences of any substring under the following rules:

The number of unique characters in the substring must be less than or equal to maxLetters.
The substring size must be between minSize and maxSize inclusive.

 
Example 1:
Input: s = "aababcaab", maxLetters = 2, minSize = 3, maxSize = 4
Output: 2
Explanation: Substring "aab" has 2 ocurrences in the original string.
It satisfies the conditions, 2 unique letters and size 3 (between minSize and maxSize).

Example 2:
Input: s = "aaaa", maxLetters = 1, minSize = 3, maxSize = 3
Output: 2
Explanation: Substring "aaa" occur 2 times in the string. It can overlap.

Example 3:
Input: s = "aabcabcab", maxLetters = 2, minSize = 2, maxSize = 3
Output: 3

Example 4:
Input: s = "abcde", maxLetters = 2, minSize = 3, maxSize = 3
Output: 0

 
Constraints:

1 <= s.length <= 10^5
1 <= maxLetters <= 26
1 <= minSize <= maxSize <= min(26, s.length)
s only contains lowercase English letters.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ivan is developing his own computer game. Now he tries to create some levels for his game. But firstly for each level he needs to draw a graph representing the structure of the level.

Ivan decided that there should be exactly n_{i} vertices in the graph representing level i, and the edges have to be bidirectional. When constructing the graph, Ivan is interested in special edges called bridges. An edge between two vertices u and v is called a bridge if this edge belongs to every path between u and v (and these vertices will belong to different connected components if we delete this edge). For each level Ivan wants to construct a graph where at least half of the edges are bridges. He also wants to maximize the number of edges in each constructed graph.

So the task Ivan gave you is: given q numbers n_1, n_2, ..., n_{q}, for each i tell the maximum number of edges in a graph with n_{i} vertices, if at least half of the edges are bridges. Note that the graphs cannot contain multiple edges or self-loops.


-----Input-----

The first line of input file contains a positive integer q (1 ≤ q ≤ 100 000) — the number of graphs Ivan needs to construct.

Then q lines follow, i-th line contains one positive integer n_{i} (1 ≤ n_{i} ≤ 2·10^9) — the number of vertices in i-th graph.

Note that in hacks you have to use q = 1.


-----Output-----

Output q numbers, i-th of them must be equal to the maximum number of edges in i-th graph.


-----Example-----
Input
3
3
4
6

Output
2
3
6



-----Note-----

In the first example it is possible to construct these graphs:  1 - 2, 1 - 3;  1 - 2, 1 - 3, 2 - 4;  1 - 2, 1 - 3, 2 - 3, 1 - 4, 2 - 5, 3 - 6.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Lee was cleaning his house for the party when he found a messy string under the carpets. Now he'd like to make it clean accurately and in a stylish way...

The string $s$ he found is a binary string of length $n$ (i. e. string consists only of 0-s and 1-s).

In one move he can choose two consecutive characters $s_i$ and $s_{i+1}$, and if $s_i$ is 1 and $s_{i + 1}$ is 0, he can erase exactly one of them (he can choose which one to erase but he can't erase both characters simultaneously). The string shrinks after erasing.

Lee can make an arbitrary number of moves (possibly zero) and he'd like to make the string $s$ as clean as possible. He thinks for two different strings $x$ and $y$, the shorter string is cleaner, and if they are the same length, then the lexicographically smaller string is cleaner.

Now you should answer $t$ test cases: for the $i$-th test case, print the cleanest possible string that Lee can get by doing some number of moves.

Small reminder: if we have two strings $x$ and $y$ of the same length then $x$ is lexicographically smaller than $y$ if there is a position $i$ such that $x_1 = y_1$, $x_2 = y_2$,..., $x_{i - 1} = y_{i - 1}$ and $x_i < y_i$.


-----Input-----

The first line contains the integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 

Next $2t$ lines contain test cases — one per two lines.

The first line of each test case contains the integer $n$ ($1 \le n \le 10^5$) — the length of the string $s$.

The second line contains the binary string $s$. The string $s$ is a string of length $n$ which consists only of zeroes and ones.

It's guaranteed that sum of $n$ over test cases doesn't exceed $10^5$.


-----Output-----

Print $t$ answers — one per test case.

The answer to the $i$-th test case is the cleanest string Lee can get after doing some number of moves (possibly zero).


-----Example-----
Input
5
10
0001111111
4
0101
8
11001101
10
1110000000
1
1

Output
0001111111
001
01
0
1



-----Note-----

In the first test case, Lee can't perform any moves.

In the second test case, Lee should erase $s_2$.

In the third test case, Lee can make moves, for example, in the following order: 11001101 $\rightarrow$ 1100101 $\rightarrow$ 110101 $\rightarrow$ 10101 $\rightarrow$ 1101 $\rightarrow$ 101 $\rightarrow$ 01.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Famil Door wants to celebrate his birthday with his friends from Far Far Away. He has n friends and each of them can come to the party in a specific range of days of the year from a_{i} to b_{i}. Of course, Famil Door wants to have as many friends celebrating together with him as possible.

Far cars are as weird as Far Far Away citizens, so they can only carry two people of opposite gender, that is exactly one male and one female. However, Far is so far from here that no other transportation may be used to get to the party.

Famil Door should select some day of the year and invite some of his friends, such that they all are available at this moment and the number of male friends invited is equal to the number of female friends invited. Find the maximum number of friends that may present at the party.


-----Input-----

The first line of the input contains a single integer n (1 ≤ n ≤ 5000) — then number of Famil Door's friends.

Then follow n lines, that describe the friends. Each line starts with a capital letter 'F' for female friends and with a capital letter 'M' for male friends. Then follow two integers a_{i} and b_{i} (1 ≤ a_{i} ≤ b_{i} ≤ 366), providing that the i-th friend can come to the party from day a_{i} to day b_{i} inclusive.


-----Output-----

Print the maximum number of people that may come to Famil Door's party.


-----Examples-----
Input
4
M 151 307
F 343 352
F 117 145
M 24 128

Output
2

Input
6
M 128 130
F 128 131
F 131 140
F 131 141
M 131 200
M 140 200

Output
4



-----Note-----

In the first sample, friends 3 and 4 can come on any day in range [117, 128].

In the second sample, friends with indices 3, 4, 5 and 6 can come on day 140.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A simple recommendation system would recommend a user things liked by a certain number of their friends. In this problem you will implement part of such a system.

You are given user's friends' opinions about a list of items. You are also given a threshold T — the minimal number of "likes" necessary for an item to be recommended to the user.

Output the number of items in the list liked by at least T of user's friends.


-----Input-----

The first line of the input will contain three space-separated integers: the number of friends F (1 ≤ F ≤ 10), the number of items I (1 ≤ I ≤ 10) and the threshold T (1 ≤ T ≤ F).

The following F lines of input contain user's friends' opinions. j-th character of i-th line is 'Y' if i-th friend likes j-th item, and 'N' otherwise.


-----Output-----

Output an integer — the number of items liked by at least T of user's friends.


-----Examples-----
Input
3 3 2
YYY
NNN
YNY

Output
2

Input
4 4 1
NNNY
NNYN
NYNN
YNNN

Output
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
When a warrior wants to talk with another one about peace or war he uses a smartphone.  In one distinct  country warriors who spent all time in training kata not always have enough money. So if they call some number they want to know which operator serves  this number. 

Write a function which **accepts number and return name of operator or string "no info"**, if operator can't be defined. number always looks like 8yyyxxxxxxx, where yyy corresponds to operator.

Here is short list of operators:

* 039 xxx xx xx - Golden Telecom
* 050 xxx xx xx - MTS
* 063 xxx xx xx - Life:)
* 066 xxx xx xx - MTS
* 067 xxx xx xx - Kyivstar
* 068 xxx xx xx - Beeline
* 093 xxx xx xx - Life:)
* 095 xxx xx xx - MTS
* 096 xxx xx xx - Kyivstar
* 097 xxx xx xx - Kyivstar
* 098 xxx xx xx - Kyivstar
* 099 xxx xx xx - MTS Test [Just return "MTS"]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A convex polygon consisting of N vertices is given. The coordinates of each vertex are represented counterclockwise by (X1, Y1), (X2, Y2), ……, (XN, YN). No matter what straight line passes through the point P, find the coordinates of the point P so that the areas of the two convex polygons obtained after cutting are equal.

Constraints

* All inputs are integers

* 3 ≤ N ≤ 50

* 0 ≤ | Xi |, | Yi | ≤ 1000000

* The input polygon is a simple convex polygon.

* The output must satisfy max (| X-cX |, | Y-cY |) ≤ 0.0001 when the output coordinates are (X, Y) and the exact solution is (cX, cY).

Input

The input is given in the following format.

> N
> X1 Y1
> X2 Y2
> ……
> XN YN
>

Output

If there is a point that satisfies the condition of the problem statement, the coordinates of that point

> X Y
>

Output in the format of. If the point does not exist, output "NA" on one line.

Examples

Input

4
100 100
0 100
0 0
100 0


Output

50.00000 50.00000


Input

3
100 100
0 100
0 0


Output

NA

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Isaac has to buy a new HackerPhone for his girlfriend Amy. He is exploring the shops in the town to compare the prices whereupon he finds a shop located on the first floor of a building, that has a unique pricing policy. There are N steps leading to the shop. A numbered ball is placed on each of the steps. 

The shopkeeper gives Isaac a fair coin and asks him to toss the coin before climbing each step. If the result of the toss is a 'Heads', Isaac should pick up the ball, else leave it and proceed to the next step.

The shopkeeper then asks Isaac to find the sum of all the numbers he has picked up (let's say S). The price of the HackerPhone is then the expected value of S. Help Isaac find the price of the HackerPhone.

Input Format 

The first line of the input contains an integer N, the number of steps.
N lines follow, which are the numbers written on the ball on each step.  

Output Format 

A single line containing expected value. 

Note : Expected value must be printed as a decimal number having exactly one digit after decimal. It is guaranteed that the correct answer will have at most one digit after decimal.

Constraints 

1 <= N <= 40 

1 <= number on any ball <=10^{9}

Sample Input #00:

3
1 
1
2

Sample Output #00:

2.0

Sample Input #01:

4
1 
2
2
2

Sample Output #01:

3.5

Explanation 

In the first case there can be 8 different ways depending on the ball choice. So, we can multiply sum for each way by its probability to occur i.e. 1/8 and sum up to get the expected value as 2. 

Similarly in the second case we have 4 items , there can be 16 ways and following the expected value one gets is 3.5.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Finally Fox Ciel arrived in front of her castle!

She have to type a password to enter her castle. An input device attached to her castle is a bit unusual.

The input device is a 1 × n rectangle divided into n square panels. They are numbered 1 to n from left to right. Each panel has a state either ON or OFF. Initially all panels are in the OFF state. She can enter her castle if and only if x1-th, x2-th, ..., xk-th panels are in the ON state and other panels are in the OFF state.

She is given an array a1, ..., al. In each move, she can perform the following operation: choose an index i (1 ≤ i ≤ l), choose consecutive ai panels, and flip the states of those panels (i.e. ON → OFF, OFF → ON).

Unfortunately she forgets how to type the password with only above operations. Determine the minimal number of operations required to enter her castle.

Input

The first line contains three integers n, k and l (1 ≤ n ≤ 10000, 1 ≤ k ≤ 10, 1 ≤ l ≤ 100), separated by single spaces.

The second line contains k integers x1, ..., xk (1 ≤ x1 < x2 < ... < xk ≤ n), separated by single spaces.

The third line contains l integers a1, ..., al (1 ≤ ai ≤ n), separated by single spaces. It is possible that some elements of the array ai are equal value.

Output

Print the minimal number of moves required to type the password. If it's impossible, print -1.

Examples

Input

10 8 2
1 2 3 5 6 7 8 9
3 5


Output

2


Input

3 2 1
1 2
3


Output

-1

Note

One possible way to type the password in the first example is following: In the first move, choose 1st, 2nd, 3rd panels and flip those panels. In the second move, choose 5th, 6th, 7th, 8th, 9th panels and flip those panels.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chubby Trung and skinny Hanh are best friend. They are smart and lovely kids, and they are both very good at math and programming. One day, chubby Trung set a puzzle to challenge skinny Hanh. Trung gives a list of $n$ distinct points on a Cartesian coordinate plane to Hanh and asks Hanh to draw a single loop connecting all these points with some conditions:
 - The loop consists of exactly $n$ segments that are parallel to the axes.
 - Each segment’s two ends must be $2$ of the given points. Other than these $2$ points, the segment must not go through any other points from the list.
 - Two consecutive segments in the loop must be perpendicular (i.e. they must form a $90$ degree angle), and they must have exactly one intersection (which is at their common end).
 - The loop must go through all $n$ points. The first and last point of the loop must be the same.
 - The loop must not self-intersect.

In the following examples, the first figure shows a valid loop. The second figure shows an invalid loop because there are segments’ ends at $(2,2)$ which is not in the list. The third one is also invalid because it does not go through all $n$ points. And the last figure is also invalid because there exists $2$ consecutive segments that are not perpendicular.

Your task is to help skinny Hanh determine whether it is possible to create such loop.

-----Input-----
The input starts with an positive integer $t$ – the number of test cases. Then $t$ test cases follow, each has the following format:
 - The first line consists of an integer $n$ – the number of points in the list ($1 \leq n \leq 2 \cdot 10^5$). The sum of $n$ in all test cases does not exceed $10^6$.
 - The $i$-th line of the next $n$ lines contains $2$ integers $x_ i$, $y_ i$ describing the $i$-th point ($0 \leq \lvert x_ i \rvert ,\lvert y_ i \rvert \leq 10^9$). It is guaranteed that no two points have the same coordinates.

-----Output-----
For each test case, if it is possible to draw the loop, print ‘YES’; otherwise, print ‘NO’.

-----Examples-----
Sample Input:
2
6
1 1
1 3
2 2
2 3
3 1
3 2
3
1 1
1 2
2 1
Sample Output:
YES
NO

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Tokitsukaze is one of the characters in the game "Kantai Collection". In this game, every character has a common attribute — health points, shortened to HP.

In general, different values of HP are grouped into $4$ categories:  Category $A$ if HP is in the form of $(4 n + 1)$, that is, when divided by $4$, the remainder is $1$;  Category $B$ if HP is in the form of $(4 n + 3)$, that is, when divided by $4$, the remainder is $3$;  Category $C$ if HP is in the form of $(4 n + 2)$, that is, when divided by $4$, the remainder is $2$;  Category $D$ if HP is in the form of $4 n$, that is, when divided by $4$, the remainder is $0$. 

The above-mentioned $n$ can be any integer.

These $4$ categories ordered from highest to lowest as $A > B > C > D$, which means category $A$ is the highest and category $D$ is the lowest.

While playing the game, players can increase the HP of the character. Now, Tokitsukaze wants you to increase her HP by at most $2$ (that is, either by $0$, $1$ or $2$). How much should she increase her HP so that it has the highest possible category?


-----Input-----

The only line contains a single integer $x$ ($30 \leq x \leq 100$) — the value Tokitsukaze's HP currently.


-----Output-----

Print an integer $a$ ($0 \leq a \leq 2$) and an uppercase letter $b$ ($b \in \lbrace A, B, C, D \rbrace$), representing that the best way is to increase her HP by $a$, and then the category becomes $b$.

Note that the output characters are case-sensitive.


-----Examples-----
Input
33

Output
0 A

Input
98

Output
1 B



-----Note-----

For the first example, the category of Tokitsukaze's HP is already $A$, so you don't need to enhance her ability.

For the second example:  If you don't increase her HP, its value is still $98$, which equals to $(4 \times 24 + 2)$, and its category is $C$.  If you increase her HP by $1$, its value becomes $99$, which equals to $(4 \times 24 + 3)$, and its category becomes $B$.  If you increase her HP by $2$, its value becomes $100$, which equals to $(4 \times 25)$, and its category becomes $D$. 

Therefore, the best way is to increase her HP by $1$ so that the category of her HP becomes $B$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N bikes and M cars on the road.

Each bike has 2 tyres.
Each car has 4 tyres.

Find the total number of tyres on the road.

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

- The first line will contain T - the number of test cases. Then the test cases follow.
- The first and only line of each test case contains two integers N, M.

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

For each test case, output in a single line,  the total number of tyres on the road.

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

$1 ≤ T ≤ 1000$
$0 ≤ N, M ≤ 100$

----- Sample Input 1 ------ 
2
2 1
3 0

----- Sample Output 1 ------ 
8
6

----- explanation 1 ------ 
Test Case $1$: There are $2$ bikes and $1$ car. Each bike has $2$ tyres, so there are $2\cdot 2 = 4$ bike tyres. Similarly, each car has $4$ tyres, so there are $1\cdot 4 = 4$ car tyres. Adding the tyres of all vehicles, we get $4+4=8$ tyres in total.

Test Case $2$: There are $3$ bikes and $0$ cars. Each bike has $2$ tyres, so there are $3\cdot 2 = 6$ bike tyres. There are no cars, so there are $0\cdot 4 = 0$ car tyres. Adding the tyres of all vehicles, we get $6+0=6$ tyres in total.

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