vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Problem

There are $ N $ Amidakuji with 3 vertical lines.
No matter which line you start from, the Amidakuji that ends at the starting line is considered a good Amidakuji.
You can select one or more Amidakuji and connect them vertically in any order.
Output "yes" if you can make a good Amidakuji, otherwise output "no".

There are $ w_i $ horizontal lines in the $ i $ th Amidakuji.
$ a_ {i, j} $ indicates whether the $ j $ th horizontal bar from the top of Amidakuji $ i $ extends from the central vertical line to the left or right.
If $ a_ {i, j} $ is 0, it means that it extends to the left, and if it is 1, it means that it extends to the right.

Constraints

The input satisfies the following conditions.

* $ 1 \ le N \ le 50 $
* $ 0 \ le w_i \ le 100 $
* $ a_ {i, j} $ is 0 or 1

Input

The input is given in the following format.


$ N $
$ w_1 $ $ a_ {1,1} $ $ a_ {1,2} $ ... $ a_ {1, w_1} $
$ w_2 $ $ a_ {2,1} $ $ a_ {2,2} $ ... $ a_ {2, w_2} $
...
$ w_N $ $ a_ {N, 1} $ $ a_ {N, 2} $ ... $ a_ {N, w_N} $


All inputs are given as integers.
$ N $ is given on the first line.
$ W_i $ and $ w_i $ $ a_ {i, j} $ are given on the following $ N $ line, separated by blanks.

Output

If you can make a good Amidakuji, it outputs "yes", otherwise it outputs "no".

Examples

Input

3
2 0 0
1 1
5 1 0 0 1 0


Output

yes


Input

2
1 1
1 0


Output

no

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Egor wants to achieve a rating of 1600 points on the well-known chess portal ChessForces and he needs your help!

Before you start solving the problem, Egor wants to remind you how the chess pieces move. Chess rook moves along straight lines up and down, left and right, as many squares as it wants. And when it wants, it can stop. The queen walks in all directions vertically and diagonally at any distance. You can see the examples below. [Image] 

To reach the goal, Egor should research the next topic:

There is an $N \times N$ board. Each cell of the board has a number from $1$ to $N ^ 2$ in it and numbers in all cells are distinct.

In the beginning, some chess figure stands in the cell with the number $1$. Note that this cell is already considered as visited. After that every move is determined by the following rules:   Among all not visited yet cells to which the figure can get in one move, it goes to the cell that has minimal number. If all accessible cells were already visited and some cells are not yet visited, then the figure is teleported to the not visited cell that has minimal number. If this step happens, the piece pays a fee of $1$ vun. If all cells are already visited, the process is stopped. 

Egor should find an $N \times N$ board on which the rook pays strictly less vuns than the queen during the round with this numbering. Help him to find such $N \times N$ numbered board, or tell that it doesn't exist.


-----Input-----

The only line contains one integer $N$  — the size of the board, $1\le N \le 500$.


-----Output-----

The output should contain $N$ lines.

In $i$-th line output $N$ numbers  — numbers on the $i$-th row of the board. All numbers from $1$ to $N \times N$ must be used exactly once.

On your board rook must pay strictly less vuns than the queen.

If there are no solutions, print $-1$.

If there are several solutions, you can output any of them. 


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

Output
-1
Input
4

Output
4 3 6 12 
7 5 9 15 
14 1 11 10 
13 8 16 2 



-----Note-----

In case we have $1 \times 1$ board, both rook and queen do not have a chance to pay fees.

In second sample rook goes through cells $1 \to 3 \to 4 \to 6 \to 9 \to 5 \to 7 \to 13 \to 2 \to 8 \to 16 \to 11 \to 10 \to 12 \to 15 \to \textbf{(1 vun)} \to 14$. 

Queen goes through $1 \to 3 \to 4 \to 2 \to 5 \to 6 \to 9 \to 7 \to 13 \to 8 \to 11 \to 10 \to 12 \to 15 \to \textbf{(1 vun)} \to 14 \to \textbf{(1 vun)} \to 16$.

As a result rook pays 1 vun and queen pays 2 vuns.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In 2028 and after a continuous growth, AtCoder Inc. finally built an empire with six cities (City 1, 2, 3, 4, 5, 6)!
There are five means of transport in this empire:
 - Train: travels from City 1 to 2 in one minute. A train can occupy at most A people.
 - Bus: travels from City 2 to 3 in one minute. A bus can occupy at most B people.
 - Taxi: travels from City 3 to 4 in one minute. A taxi can occupy at most C people.
 - Airplane: travels from City 4 to 5 in one minute. An airplane can occupy at most D people.
 - Ship: travels from City 5 to 6 in one minute. A ship can occupy at most E people.
For each of them, one vehicle leaves the city at each integer time (time 0, 1, 2, ...).
There is a group of N people at City 1, and they all want to go to City 6.

At least how long does it take for all of them to reach there? 
You can ignore the time needed to transfer.  

-----Constraints-----
 - 1 \leq N, A, B, C, D, E \leq 10^{15}
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N
A
B
C
D
E

-----Output-----
Print the minimum time required for all of the people to reach City 6, in minutes.

-----Sample Input-----
5
3
2
4
3
5

-----Sample Output-----
7

One possible way to travel is as follows.
First, there are N = 5 people at City 1, as shown in the following image:

In the first minute, three people travels from City 1 to City 2 by train. Note that a train can only occupy at most three people.

In the second minute, the remaining two people travels from City 1 to City 2 by train, and two of the three people who were already at City 2 travels to City 3 by bus. Note that a bus can only occupy at most two people.

In the third minute, two people travels from City 2 to City 3 by train, and another two people travels from City 3 to City 4 by taxi.

From then on, if they continue traveling without stopping until they reach City 6, all of them can reach there in seven minutes.

There is no way for them to reach City 6 in 6 minutes or less.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Task
 Smartphones software security has become a growing concern related to mobile telephony. It is particularly important as it relates to the security of available personal information.
 
 For this reason, Ahmed decided to encrypt phone numbers of contacts in such a way that nobody can decrypt them. At first he tried encryption algorithms very complex, but the decryption process is tedious, especially when he needed to dial a speed dial.

 He eventually found the algorithm following: instead of writing the number itself, Ahmed multiplied by 10, then adds the result to the original number.
 
 For example, if the phone number is `123`, after the transformation, it becomes `1353`. Ahmed truncates the result (from the left), so it has as many digits as the original phone number. In this example Ahmed wrote `353` instead of `123` in his smart phone.

 Ahmed needs a program to recover the original phone number from number stored on his phone. The program return "impossible" if the initial number can not be calculated.
 
 Note: There is no left leading zero in either the input or the output; Input `s` is given by string format, because it may be very huge ;-)

# Example

 For `s="353"`, the result should be `"123"`
 
 ```
    1230
  +  123
  .......
  = 1353  
  
  truncates the result to 3 digit -->"353"
  
  So the initial number is "123"
 ```
 For `s="123456"`, the result should be `"738496"`
 
 ```
    7384960
  +  738496
  .........
  = 8123456
  
  truncates the result to 6 digit -->"123456"
  
  So the initial number is "738496"
 ```
 For `s="4334"`, the result should be `"impossible"`
 
 Because no such a number can be encrypted to `"4334"`.

# Input/Output


 - `[input]` string `s`

  string presentation of n with `1 <= n <= 10^100`


 - `[output]` a string

  The original phone number before encryption, or `"impossible"` if the initial number can not be calculated.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Thor is getting used to the Earth. As a gift Loki gave him a smartphone. There are n applications on this phone. Thor is fascinated by this phone. He has only one minor issue: he can't count the number of unread notifications generated by those applications (maybe Loki put a curse on it so he can't).

q events are about to happen (in chronological order). They are of three types:  Application x generates a notification (this new notification is unread).  Thor reads all notifications generated so far by application x (he may re-read some notifications).  Thor reads the first t notifications generated by phone applications (notifications generated in first t events of the first type). It's guaranteed that there were at least t events of the first type before this event. Please note that he doesn't read first t unread notifications, he just reads the very first t notifications generated on his phone and he may re-read some of them in this operation. 

Please help Thor and tell him the number of unread notifications after each event. You may assume that initially there are no notifications in the phone.


-----Input-----

The first line of input contains two integers n and q (1 ≤ n, q ≤ 300 000) — the number of applications and the number of events to happen.

The next q lines contain the events. The i-th of these lines starts with an integer type_{i} — type of the i-th event. If type_{i} = 1 or type_{i} = 2 then it is followed by an integer x_{i}. Otherwise it is followed by an integer t_{i} (1 ≤ type_{i} ≤ 3, 1 ≤ x_{i} ≤ n, 1 ≤ t_{i} ≤ q).


-----Output-----

Print the number of unread notifications after each event.


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

Output
1
2
3
2

Input
4 6
1 2
1 4
1 2
3 3
1 3
1 3

Output
1
2
3
0
1
2



-----Note-----

In the first sample:  Application 3 generates a notification (there is 1 unread notification).  Application 1 generates a notification (there are 2 unread notifications).  Application 2 generates a notification (there are 3 unread notifications).  Thor reads the notification generated by application 3, there are 2 unread notifications left. 

In the second sample test:  Application 2 generates a notification (there is 1 unread notification).  Application 4 generates a notification (there are 2 unread notifications).  Application 2 generates a notification (there are 3 unread notifications).  Thor reads first three notifications and since there are only three of them so far, there will be no unread notification left.  Application 3 generates a notification (there is 1 unread notification).  Application 3 generates a notification (there are 2 unread notifications).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write a program that reads numbers until -1 is not given.
The program finds how many of the given numbers are more than 30, $N$.
It also finds the average weighted sum of even numbers, $A$.
The weight of the $i$th number is defined as the position of the number (1 based indexing) times the number. To find the average weighted sum, you need to add all these weights for the even numbers, then divide the sum by the sum of the positions of the numbers.

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- Each testcase contains some numbers, terminated by -1

-----Output:-----
For each testcase, output in a single line the count of numbers that are greater than 30, $N$, and the average weighted sum of the even numbers, $A$, separated by a space. Make sure to set the precision of the average weighted sum to 2 places after the decimal point.

-----Constraints-----
- $1 \leq T \leq 1000$
- $2 \leq N \leq 1000$

-----Sample Input:-----
1
33 100 77 42 12 -1

-----Sample Output:-----
4 38.91

-----EXPLANATION:-----
In the series of numbers 33 100 77 42 12 -1, the count of numbers greater than 30 is 4
The average weighted sum of the even numbers is given by:
((2 * 100) + (4 * 42) + (5 * 12)) / (2 + 4 + 5)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array A of n positive numbers. The task is to find the first Equilibrium Point in an array. 
Equilibrium Point in an array is a position such that the sum of elements before it is equal to the sum of elements after it.
Note: Retun the index of Equilibrium point. (1-based index)
Example 1:
Input: 
n = 5 
A[] = {1,3,5,2,2} 
Output: 3 
Explanation:  
equilibrium point is at position 3 
as elements before it (1+3) = 
elements after it (2+2). 
 
Example 2:
Input:
n = 1
A[] = {1}
Output: 1
Explanation:
Since its the only element hence
its the only equilibrium point.
 
Your Task:
The task is to complete the function equilibriumPoint() which takes the array and n as input parameters and returns the point of equilibrium. Return -1 if no such point exists. 
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)
Constraints:
1 <= n <= 10^{6}
1 <= A[i] <= 10^{8}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Initially on a notepad only one character 'A' is present. You can perform two operations on this notepad for each step: 

Copy All: You can copy all the characters present on the notepad (partial copy is not allowed).
Paste: You can paste the characters which are copied last time.




Given a number n. You have to get exactly n 'A' on the notepad by performing the minimum number of steps permitted. Output the minimum number of steps to get n 'A'. 


Example 1:

Input: 3
Output: 3
Explanation:
Intitally, we have one character 'A'.
In step 1, we use Copy All operation.
In step 2, we use Paste operation to get 'AA'.
In step 3, we use Paste operation to get 'AAA'.




Note:

The n will be in the range [1, 1000].

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Your task is to write function which takes string and list of delimiters as an input and returns list of strings/characters after splitting given string.

Example:
```python
multiple_split('Hi, how are you?', [' ']) => ['Hi,', 'how', 'are', 'you?']
multiple_split('1+2-3', ['+', '-']) => ['1', '2', '3']
```

List of delimiters is optional and can be empty, so take that into account.

Important note: Result cannot contain empty string.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This is a harder version of the problem. In this version $n \le 500\,000$

The outskirts of the capital are being actively built up in Berland. The company "Kernel Panic" manages the construction of a residential complex of skyscrapers in New Berlskva. All skyscrapers are built along the highway. It is known that the company has already bought $n$ plots along the highway and is preparing to build $n$ skyscrapers, one skyscraper per plot.

Architects must consider several requirements when planning a skyscraper. Firstly, since the land on each plot has different properties, each skyscraper has a limit on the largest number of floors it can have. Secondly, according to the design code of the city, it is unacceptable for a skyscraper to simultaneously have higher skyscrapers both to the left and to the right of it.

Formally, let's number the plots from $1$ to $n$. Then if the skyscraper on the $i$-th plot has $a_i$ floors, it must hold that $a_i$ is at most $m_i$ ($1 \le a_i \le m_i$). Also there mustn't be integers $j$ and $k$ such that $j < i < k$ and $a_j > a_i < a_k$. Plots $j$ and $k$ are not required to be adjacent to $i$.

The company wants the total number of floors in the built skyscrapers to be as large as possible. Help it to choose the number of floors for each skyscraper in an optimal way, i.e. in such a way that all requirements are fulfilled, and among all such construction plans choose any plan with the maximum possible total number of floors.


-----Input-----

The first line contains a single integer $n$ ($1 \leq n \leq 500\,000$) — the number of plots.

The second line contains the integers $m_1, m_2, \ldots, m_n$ ($1 \leq m_i \leq 10^9$) — the limit on the number of floors for every possible number of floors for a skyscraper on each plot.


-----Output-----

Print $n$ integers $a_i$ — the number of floors in the plan for each skyscraper, such that all requirements are met, and the total number of floors in all skyscrapers is the maximum possible.

If there are multiple answers possible, print any of them.


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

Output
1 2 3 2 1 

Input
3
10 6 8

Output
10 6 6 



-----Note-----

In the first example, you can build all skyscrapers with the highest possible height.

In the second test example, you cannot give the maximum height to all skyscrapers as this violates the design code restriction. The answer $[10, 6, 6]$ is optimal. Note that the answer of $[6, 6, 8]$ also satisfies all restrictions, but is not optimal.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a binary string s of length n. You have to perform binary addition of the string with '1'.
 
Example 1:
Input: 
n = 4
s = 1010
Output: 1011
Explaination: 
The decimal equivalent of given s is 10, 
Adding 1 gives 11, its binary representation
is 1011.
 
Example 2:
Input: 
n = 3
s = 111
Output: 1000
Explaination: The given number is 7. 
Now 7+1 = 8, whose binary representation 
is 1000.
 
Your Task:
You do not need to read input or print anyhthing. Your task is to complete the function binaryAdd() which takes n and s as input parameters and returns the resultant binary string after adding 1 with s.
 
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)
 
Constraints:
1 ≤ n ≤ 10000

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

AOR Ika is at the $ S $ th bus stop at time $ 0 $ and wants to go from there to the $ G $ th bus stop. The number of bus stops $ N $ and $ M $ routes (*) connecting different bus stops are given. The bus stops are numbered $ 1, \ dots, and N $, respectively. Each route consists of $ 4 $ values: origin $ u $, destination $ v $, departure time $ t $, and travel time $ c $. You can catch the bus if you are at the departure $ u $ at the time $ t $ and arrive at the destination $ v $ at the time $ t + c $. While not on the bus, AOR Ika gets wet in the rain. When heading to the $ G $ th bus stop through the route that minimizes the time of getting wet in the rain, output the total time of getting wet in the rain from the time $ 0 $ to the arrival at the $ G $ th bus stop.

(*) In graph theory terms, a path is a sequence of vertices and edges, but please note that it is used here to mean edges.



input

Input is given from standard input in the following format.

$ N \ M \ S \ G $
$ u_1 \ v_1 \ t_1 \ c_1 $
$ \ vdots $
$ u_M \ v_M \ t_M \ c_M $

output

Print the minimum amount of time you get wet in one line. Also, output a line break at the end.

Example

Input

2 2 1 2
1 2 10 100
1 2 5 500


Output

5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For the given integer $n$ ($n > 2$) let's write down all the strings of length $n$ which contain $n-2$ letters 'a' and two letters 'b' in lexicographical (alphabetical) order.

Recall that the string $s$ of length $n$ is lexicographically less than string $t$ of length $n$, if there exists such $i$ ($1 \le i \le n$), that $s_i < t_i$, and for any $j$ ($1 \le j < i$) $s_j = t_j$. The lexicographic comparison of strings is implemented by the operator < in modern programming languages.

For example, if $n=5$ the strings are (the order does matter):  aaabb  aabab  aabba  abaab  ababa  abbaa  baaab  baaba  babaa  bbaaa 

It is easy to show that such a list of strings will contain exactly $\frac{n \cdot (n-1)}{2}$ strings.

You are given $n$ ($n > 2$) and $k$ ($1 \le k \le \frac{n \cdot (n-1)}{2}$). Print the $k$-th string from the list.


-----Input-----

The input contains one or more test cases.

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

Each test case is written on the the separate line containing two integers $n$ and $k$ ($3 \le n \le 10^5, 1 \le k \le \min(2\cdot10^9, \frac{n \cdot (n-1)}{2})$.

The sum of values $n$ over all test cases in the test doesn't exceed $10^5$.


-----Output-----

For each test case print the $k$-th string from the list of all described above strings of length $n$. Strings in the list are sorted lexicographically (alphabetically).


-----Example-----
Input
7
5 1
5 2
5 8
5 10
3 1
3 2
20 100

Output
aaabb
aabab
baaba
bbaaa
abb
bab
aaaaabaaaaabaaaaaaaa

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Takahashi has decided to make a Christmas Tree for the Christmas party in AtCoder, Inc.

A Christmas Tree is a tree with N vertices numbered 1 through N and N-1 edges, whose i-th edge (1\leq i\leq N-1) connects Vertex a_i and b_i.

He would like to make one as follows:

* Specify two non-negative integers A and B.
* Prepare A Christmas Paths whose lengths are at most B. Here, a Christmas Path of length X is a graph with X+1 vertices and X edges such that, if we properly number the vertices 1 through X+1, the i-th edge (1\leq i\leq X) will connect Vertex i and i+1.
* Repeat the following operation until he has one connected tree:
* Select two vertices x and y that belong to different connected components. Combine x and y into one vertex. More precisely, for each edge (p,y) incident to the vertex y, add the edge (p,x). Then, delete the vertex y and all the edges incident to y.
* Properly number the vertices in the tree.



Takahashi would like to find the lexicographically smallest pair (A,B) such that he can make a Christmas Tree, that is, find the smallest A, and find the smallest B under the condition that A is minimized.

Solve this problem for him.

Constraints

* 2 \leq N \leq 10^5
* 1 \leq a_i,b_i \leq N
* The given graph is a tree.

Input

Input is given from Standard Input in the following format:


N
a_1 b_1
:
a_{N-1} b_{N-1}


Output

For the lexicographically smallest (A,B), print A and B with a space in between.

Examples

Input

7
1 2
2 3
2 4
4 5
4 6
6 7


Output

3 2


Input

8
1 2
2 3
3 4
4 5
5 6
5 7
5 8


Output

2 5


Input

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


Output

3 4

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