vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Kate likes to count words in text blocks. By words she means continuous sequences of English alphabetic characters (from a to z ). Here are examples:

`Hello there, little user5453 374 ())$. I’d been using my sphere as a stool. Slow-moving target 839342 was hit by OMGd-63 or K4mp.` contains "words" `['Hello', 'there', 'little', 'user', 'I', 'd', 'been', 'using', 'my','sphere', 'as', 'a', 'stool', 'Slow', 'moving', 'target', 'was', 'hit', 'by', 'OMGd', 'or', 'K', 'mp']`

Kate doesn't like some of words and doesn't count them. Words to be excluded are "a", "the", "on", "at", "of", "upon", "in" and "as", case-insensitive.

Today Kate's too lazy and have decided to teach her computer to count "words" for her.


Example Input 1
-------------
Hello there, little user5453 374 ())$.

Example Output 1
-------------
4

Example Input 2
-------------

  I’d been using my sphere as a stool. I traced counterclockwise circles on it with my fingertips and it shrank until I could palm it. My bolt had shifted while I’d been sitting. I pulled it up and yanked the pleats straight as I careered around tables, chairs, globes, and slow-moving fraas. I passed under a stone arch into the Scriptorium. The place smelled richly of ink. Maybe it was because an ancient fraa and his two fids were copying out books there. But I wondered how long it would take to stop smelling that way if no one ever used it at all; a lot of ink had been spent there, and the wet smell of it must be deep into everything.

Example Output 2
--------------

112

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a list of preferences for n friends, where n is always even.
For each person i, preferences[i] contains a list of friends sorted in the order of preference. In other words, a friend earlier in the list is more preferred than a friend later in the list. Friends in each list are denoted by integers from 0 to n-1.
All the friends are divided into pairs. The pairings are given in a list pairs, where pairs[i] = [xi, yi] denotes xi is paired with yi and yi is paired with xi.
However, this pairing may cause some of the friends to be unhappy. A friend x is unhappy if x is paired with y and there exists a friend u who is paired with v but:

x prefers u over y, and
u prefers x over v.

Return the number of unhappy friends.
 
Example 1:
Input: n = 4, preferences = [[1, 2, 3], [3, 2, 0], [3, 1, 0], [1, 2, 0]], pairs = [[0, 1], [2, 3]]
Output: 2
Explanation:
Friend 1 is unhappy because:
- 1 is paired with 0 but prefers 3 over 0, and
- 3 prefers 1 over 2.
Friend 3 is unhappy because:
- 3 is paired with 2 but prefers 1 over 2, and
- 1 prefers 3 over 0.
Friends 0 and 2 are happy.

Example 2:
Input: n = 2, preferences = [[1], [0]], pairs = [[1, 0]]
Output: 0
Explanation: Both friends 0 and 1 are happy.

Example 3:
Input: n = 4, preferences = [[1, 3, 2], [2, 3, 0], [1, 3, 0], [0, 2, 1]], pairs = [[1, 3], [0, 2]]
Output: 4

 
Constraints:

2 <= n <= 500
n is even.
preferences.length == n
preferences[i].length == n - 1
0 <= preferences[i][j] <= n - 1
preferences[i] does not contain i.
All values in preferences[i] are unique.
pairs.length == n/2
pairs[i].length == 2
xi != yi
0 <= xi, yi <= n - 1
Each person is contained in exactly one pair.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The grand museum has just announced a large exhibit on jewelry from around the world. In the hopes of his potential future prosperity, the world-renowned thief and master criminal Edward Terrenando has decided to attempt the magnum opus of his career in thievery.

Edward is hoping to purloin a large number of jewels from the exhibit at the grand museum. But alas! He must be careful with which jewels to appropriate in order to maximize the total value of jewels stolen.

Edward has $k$ knapsacks of size $1$, $2$, $3$, up to $k$, and would like to know for each the maximum sum of values of jewels that can be stolen. This way he can properly weigh risk vs. reward when choosing how many jewels to steal. A knapsack of size $s$ can hold items if the sum of sizes of those items is less than or equal to $s$. If you can figure out the best total value of jewels for each size of knapsack, you can help Edward pull off the heist of the century!

-----Input-----
Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. The first line of input will consist of two space-separated integers $n$ and $k$, where $n$ ($1 \le n \le 1000000$) is the number of jewels in the exhibit, and $k$ ($1 \le k \le 100000$) is the maximum size of knapsack available to Edward. The next $n$ lines each will describe a jewel. Each line will consist of two space-separated integers $s$ and $v$, where $s$ ($1 \le s \le 300$) is the size of the jewel, and $v$ ($1 \le v \le 10^9$) is its value. Each jewel can only be taken once per knapsack, but each knapsack is an independent problem.

-----Output-----
Output $k$ integers separated by whitespace. The first integer should be the maximum value of jewels that will fit in a knapsack of size $1$. The second should be the maximum value of jewels in a knapsack of size $2$, and so on.

-----Examples-----
Sample Input 1:
4 9
2 8
1 1
3 4
5 100
Sample Output 1:
1 8 9 9 100 101 108 109 109

Sample Input 2:
5 7
2 2
3 8
2 7
2 4
3 8
Sample Output 2:
0 7 8 11 15 16 19

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
A team of students from the city S is sent to the All-Berland Olympiad in Informatics. Traditionally, they go on the train. All students have bought tickets in one carriage, consisting of *n* compartments (each compartment has exactly four people). We know that if one compartment contain one or two students, then they get bored, and if one compartment contain three or four students, then the compartment has fun throughout the entire trip.

The students want to swap with other people, so that no compartment with students had bored students. To swap places with another person, you need to convince him that it is really necessary. The students can not independently find the necessary arguments, so they asked a sympathetic conductor for help. The conductor can use her life experience to persuade any passenger to switch places with some student.

However, the conductor does not want to waste time persuading the wrong people, so she wants to know what is the minimum number of people necessary to persuade her to change places with the students. Your task is to find the number. 

After all the swaps each compartment should either have no student left, or have a company of three or four students.

Input Specification:
The first line contains integer *n* (1<=≤<=*n*<=≤<=106) — the number of compartments in the carriage. The second line contains *n* integers *a*1,<=*a*2,<=...,<=*a**n* showing how many students ride in each compartment (0<=≤<=*a**i*<=≤<=4). It is guaranteed that at least one student is riding in the train.

Output Specification:
If no sequence of swapping seats with other people leads to the desired result, print number "-1" (without the quotes). In another case, print the smallest number of people you need to persuade to swap places.

Demo Input:
['5\n1 2 2 4 3\n', '3\n4 1 1\n', '4\n0 3 0 4\n']

Demo Output:
['2\n', '2\n', '0\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Fox Jiro is one of the staffs of the ACM-ICPC 2018 Asia Yokohama Regional Contest and is responsible for designing the network for the venue of the contest. His network consists of $N$ computers, which are connected by $M$ cables. The $i$-th cable connects the $a_i$-th computer and the $b_i$-th computer, and it carries data in both directions. Your team will use the $S$-th computer in the contest, and a judge server is the $T$-th computer.

He decided to adjust the routing algorithm of the network to maximize the performance of the contestants through the magical power of prime numbers. In this algorithm, a packet (a unit of data carried by the network) is sent from your computer to the judge server passing through the cables a prime number of times if possible. If it is impossible, the contestants cannot benefit by the magical power of prime numbers. To accomplish this target, a packet is allowed to pass through the same cable multiple times.

You decided to write a program to calculate the minimum number of times a packet from $S$ to $T$ needed to pass through the cables. If the number of times a packet passes through the cables cannot be a prime number, print $-1$.



Input

The input consists of a single test case, formatted as follows.


$N$ $M$ $S$ $T$
$a_1$ $b_1$
$\vdots$
$a_M$ $b_M$


The first line consists of four integers $N, M, S,$ and $T$ ($2 \leq N \leq 10^5, 1 \leq M \leq 10^5, 1 \leq S, T \leq N, S \ne T$). The $i$-th line of the following $M$ lines consists of two integers $a_i$ and $b_i$ ($1 \leq a_i < b_i \leq N$), which means the $i$-th cables connects the $a_i$-th computer and the $b_i$-th computer in the network. You can assume that the network satisfies the following conditions.

* The network has no multi-edge, i.e.,$(a_i, b_i) \ne (a_j, b_j)$ for all $i,j$ ($1 \leq i < j \leq M$).
* The packets from $N$ computers are reachable to $T$ by passing through some number of cables. The number is not necessarily a prime.

Output

If there are ways such that the number of times a packet sent from $S$ to $T$ passes through the cables is a prime number, print the minimum prime number of times in one line. Otherwise, print $-1$.

Examples

Input

5 5 1 5
1 2
1 4
2 3
3 4
3 5


Output

3


Input

5 4 1 5
1 2
2 3
3 4
4 5


Output

-1


Input

2 1 1 2
1 2


Output

3


Input

3 3 1 2
1 2
1 3
2 3


Output

2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
It’s Christmas time and JW’s $1$-dimensional shop is selling Christmas trees. However, the demand for trees is much higher than the number of trees available. Hence, JW has come up with a special strategy to help decide who gets what tree: a game of Musical Trees!

Musical Trees is much like the game Musical Chairs. There’s a set of trees lined up in a straight ($1$-dimensional) line. At first, everyone starts by wandering around the store while the music is playing. When the music stops, everyone runs to the nearest tree (the tree the smallest distance away) and whoever reaches a tree first gets to the claim that tree. Since people are lazy, they will only ever try to run to the closest tree to them, and hence multiple people may try to get the same tree. Note this means some trees may be unclaimed if they are closest to no one. Also, like in Musical Chairs, no tree can be claimed by more than one person.

The music has just stopped in Musical Trees and as everyone is running to the closest tree, you want to figure out the number of people who won’t get any tree.

-----Input-----
The first line consists the number of people $n$ ($1\le n\le 100$) and the number of trees $m$ ($1 \le m \le 100$). The next line contains $n$ integers $p_1,p_2,\ldots ,p_ n$, the positions of all the people when the music stops ($1 \le p_ i \le 1000$). The last line contains $m$ integers $t_1,t_2,\ldots ,t_ m$, the positions of all the trees ($1 \le t_ i \le 1000$). No two people or two trees will have the same position. Some people may try to cheat though, and will already be at the same position as a tree when the music stops. Note that if a person has more than one closest tree to them, they will always go for the one with the smallest $t_ i$.

-----Output-----
Output the number of people who won’t get a tree.

-----Examples-----
Sample Input 1:
2 3
1 4
2 4 5
Sample Output 1:
0

Sample Input 2:
3 2
1 5 10
4 6
Sample Output 2:
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You will be given a list of 32 bit unsigned integers. Flip all the bits ($1\rightarrow0$ and $\textbf{0}\rightarrow1$) and return the result as an unsigned integer.  

Example 

$n=9_{10}$   

$\textbf{9}_{10}=1\textbf{001}_{2}$.  We're working with 32 bits, so:  

$00000000000000000000000000001001_2=9_{10}$ 

$11111111111111111111111111110110_2=4294967286_{10}$  

Return $4294967286$.

Function Description

Complete the flippingBits function in the editor below.  

flippingBits has the following parameter(s):

int n: an integer   

Returns   

int: the unsigned decimal integer result

Input Format

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

Each of the next $\textit{q}$ lines contain an integer, $n$, to process.  

Constraints

$1\leq q\leq100$ 

$0\leq n<2^{32}$

Sample Input 0
3
2147483647
1
0

Sample Output 0
2147483648
4294967294
4294967295

Explanation 0

$01111111111111111111111111111111_{2}=2147483647_{10}$ 

$10000000000000000000000000000000_2=2147483648_{10}$  

$00000000000000000000000000000001_2=1_{10}$ 

$11111111111111111111111111111110_2=4294967294_{10}$  

$00000000000000000000000000000000_{2}=0_{10}$ 

$11111111111111111111111111111111_2=4294967295_{10}$  

Sample Input 1
2
4
123456

Sample Output 1
4294967291
4294843839

Explanation 1

$00000000000000000000000000000100_{2}=4_{10}$ 

$11111111111111111111111111111011_2=4294967291_{10}$  

$000000000000000111001001000000_2=123456_{10}$ 

$11111111111111100001110110111111_{2}=4294843839_{10}$  

Sample Input 2
3
0
802743475
35601423

Sample Output 2
4294967295
3492223820
4259365872

Explanation 2

$00000000000000000000000000000000_{2}=0_{10}$ 

$11111111111111111111111111111111_2=4294967295_{10}$  

$00101111110110001110010010110011_2=802743475_{10}$ 

$11010000001001110001101101001100_2=3492223820_{10}$  

$00000010000111110011110000001111_2=35601423_{10}$ 

$11111101111000001100001111110000_2=425965872_{10}$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Example 1:


Input: [2,4,1], k = 2
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.


Example 2:


Input: [3,2,6,5,0,3], k = 2
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4.
             Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The only difference between easy and hard versions is constraints.

There are $n$ kids, each of them is reading a unique book. At the end of any day, the $i$-th kid will give his book to the $p_i$-th kid (in case of $i = p_i$ the kid will give his book to himself). It is guaranteed that all values of $p_i$ are distinct integers from $1$ to $n$ (i.e. $p$ is a permutation). The sequence $p$ doesn't change from day to day, it is fixed.

For example, if $n=6$ and $p=[4, 6, 1, 3, 5, 2]$ then at the end of the first day the book of the $1$-st kid will belong to the $4$-th kid, the $2$-nd kid will belong to the $6$-th kid and so on. At the end of the second day the book of the $1$-st kid will belong to the $3$-th kid, the $2$-nd kid will belong to the $2$-th kid and so on.

Your task is to determine the number of the day the book of the $i$-th child is returned back to him for the first time for every $i$ from $1$ to $n$.

Consider the following example: $p = [5, 1, 2, 4, 3]$. The book of the $1$-st kid will be passed to the following kids:  after the $1$-st day it will belong to the $5$-th kid,  after the $2$-nd day it will belong to the $3$-rd kid,  after the $3$-rd day it will belong to the $2$-nd kid,  after the $4$-th day it will belong to the $1$-st kid. 

So after the fourth day, the book of the first kid will return to its owner. The book of the fourth kid will return to him for the first time after exactly one day.

You have to answer $q$ independent queries.


-----Input-----

The first line of the input contains one integer $q$ ($1 \le q \le 200$) — the number of queries. Then $q$ queries follow.

The first line of the query contains one integer $n$ ($1 \le n \le 200$) — the number of kids in the query. The second line of the query contains $n$ integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$, all $p_i$ are distinct, i.e. $p$ is a permutation), where $p_i$ is the kid which will get the book of the $i$-th kid.


-----Output-----

For each query, print the answer on it: $n$ integers $a_1, a_2, \dots, a_n$, where $a_i$ is the number of the day the book of the $i$-th child is returned back to him for the first time in this query.


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

Output
1 1 1 1 1 
3 3 3 
2 3 3 2 1 3 
1 
2 2 2 2 
4 4 4 1 4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Petya has a polygon consisting of n vertices. All sides of the Petya's polygon are parallel to the coordinate axes, and each two adjacent sides of the Petya's polygon are perpendicular. It is guaranteed that the polygon is simple, that is, it doesn't have self-intersections and self-touches. All internal area of the polygon (borders are not included) was painted in black color by Petya.

Also, Petya has a rectangular window, defined by its coordinates, through which he looks at the polygon. A rectangular window can not be moved. The sides of the rectangular window are parallel to the coordinate axes.

<image> Blue color represents the border of a polygon, red color is the Petya's window. The answer in this case is 2.

Determine the number of black connected areas of Petya's polygon, which can be seen through the rectangular window.

Input

The first line contain four integers x_1, y_1, x_2, y_2 (x_1 < x_2, y_2 < y_1) — the coordinates of top-left and bottom-right corners of the rectangular window. 

The second line contains a single integer n (4 ≤ n ≤ 15 000) — the number of vertices in Petya's polygon.

Each of the following n lines contains two integers — the coordinates of vertices of the Petya's polygon in counterclockwise order. Guaranteed, that the given polygon satisfies the conditions described in the statement.

All coordinates of the rectangular window and all coordinates of the vertices of the polygon are non-negative and do not exceed 15 000.

Output

Print the number of black connected areas of Petya's polygon, which can be seen through the rectangular window.

Example

Input

5 7 16 3
16
0 0
18 0
18 6
16 6
16 1
10 1
10 4
7 4
7 2
2 2
2 6
12 6
12 12
10 12
10 8
0 8


Output

2

Note

The example corresponds to the picture above.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an integer N, find the base -2 representation of N.
Here, S is the base -2 representation of N when the following are all satisfied:
 - S is a string consisting of 0 and 1.
 - Unless S = 0, the initial character of S is 1.
 - Let S = S_k S_{k-1} ... S_0, then S_0 \times (-2)^0 + S_1 \times (-2)^1 + ... + S_k \times (-2)^k = N.
It can be proved that, for any integer M, the base -2 representation of M is uniquely determined.

-----Constraints-----
 - Every value in input is integer.
 - -10^9 \leq N \leq 10^9

-----Input-----
Input is given from Standard Input in the following format:
N

-----Output-----
Print the base -2 representation of N.

-----Sample Input-----
-9

-----Sample Output-----
1011

As (-2)^0 + (-2)^1 + (-2)^3 = 1 + (-2) + (-8) = -9, 1011 is the base -2 representation of -9.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a weighted undirected connected graph consisting of n vertices and m edges. It is guaranteed that there are no self-loops or multiple edges in the given graph.

Let's define the weight of the path consisting of k edges with indices e_1, e_2, ..., e_k as ∑_{i=1}^{k}{w_{e_i}} - max_{i=1}^{k}{w_{e_i}} + min_{i=1}^{k}{w_{e_i}}, where w_i — weight of the i-th edge in the graph.

Your task is to find the minimum weight of the path from the 1-st vertex to the i-th vertex for each i (2 ≤ i ≤ n).

Input

The first line contains two integers n and m (2 ≤ n ≤ 2 ⋅ 10^5; 1 ≤ m ≤ 2 ⋅ 10^5) — the number of vertices and the number of edges in the graph.

Following m lines contains three integers v_i, u_i, w_i (1 ≤ v_i, u_i ≤ n; 1 ≤ w_i ≤ 10^9; v_i ≠ u_i) — endpoints of the i-th edge and its weight respectively.

Output

Print n-1 integers — the minimum weight of the path from 1-st vertex to the i-th vertex for each i (2 ≤ i ≤ n).

Examples

Input


5 4
5 3 4
2 1 1
3 2 2
2 4 2


Output


1 2 2 4 


Input


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


Output


2 1 4 3 1 


Input


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


Output


3 4 2 7 7 3 

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

In this kata you are required to, given a string, replace every letter with its position in the alphabet.

If anything in the text isn't a letter, ignore it and don't return it.

`"a" = 1`, `"b" = 2`, etc.

## Example

```python
alphabet_position("The sunset sets at twelve o' clock.")
```
Should return `"20 8 5 19 21 14 19 5 20 19 5 20 19 1 20 20 23 5 12 22 5 15 3 12 15 3 11"` (as a string)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Aklank is fond of numbers which are divisible by either P1 or P2. He termed those numbers as Bakku numbers. Recently his best friend gave him a range of numbers. Now he is wondering what is the probability of finding Bakku numbers from that range of numbers.

Input
First line of input contains two integers P1 and P2 (2 ≤ P1 ≤ 10000, 2 ≤ P2 ≤ 10000) — both P1 and P2 are prime numbers.

Second line of the input contains an integer T  (1 ≤ T ≤ 100000) — the number of test cases.

Each of the next T lines contains two integers - L and R (1 ≤ L ≤ R ≤ 100,00,00,000) - the starting number and ending number of each range from where he will search for Bakku numbers (inclusive).

Output
Print T lines for each test case.

In each line print answer with up to 6 digits after decimal point.

SAMPLE INPUT
3 5
2
1 10
20 34

SAMPLE OUTPUT
0.500000
0.466667

Explanation

First Case : Numbers divisible by 3 or 5 are 3, 5, 6, 9, 10

Second Case : Numbers divisible by 3 or 5 are 20, 21, 24, 25, 27, 30, 33

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Complete the solution so that it strips all text that follows any of a set of comment markers passed in. Any whitespace at the end of the line should also be stripped out. 

**Example:**

Given an input string of:
```
apples, pears # and bananas
grapes
bananas !apples
```

The output expected would be:
```
apples, pears
grapes
bananas
```

The code would be called like so:

```python
result = solution("apples, pears # and bananas\ngrapes\nbananas !apples", ["#", "!"])
# result should == "apples, pears\ngrapes\nbananas"

```

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