vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
All of us love treasures, right? That's why young Vasya is heading for a Treasure Island.

Treasure Island may be represented as a rectangular table $n \times m$ which is surrounded by the ocean. Let us number rows of the field with consecutive integers from $1$ to $n$ from top to bottom and columns with consecutive integers from $1$ to $m$ from left to right. Denote the cell in $r$-th row and $c$-th column as $(r, c)$. Some of the island cells contain impassable forests, and some cells are free and passable. Treasure is hidden in cell $(n, m)$.

Vasya got off the ship in cell $(1, 1)$. Now he wants to reach the treasure. He is hurrying up, so he can move only from cell to the cell in next row (downwards) or next column (rightwards), i.e. from cell $(x, y)$ he can move only to cells $(x+1, y)$ and $(x, y+1)$. Of course Vasya can't move through cells with impassable forests.

Evil Witch is aware of Vasya's journey and she is going to prevent him from reaching the treasure. Before Vasya's first move she is able to grow using her evil magic impassable forests in previously free cells. Witch is able to grow a forest in any number of any free cells except cells $(1, 1)$ where Vasya got off his ship and $(n, m)$ where the treasure is hidden.

Help Evil Witch by finding out the minimum number of cells she has to turn into impassable forests so that Vasya is no longer able to reach the treasure.


-----Input-----

First line of input contains two positive integers $n$, $m$ ($3 \le n \cdot m \le 1\,000\,000$), sizes of the island.

Following $n$ lines contains strings $s_i$ of length $m$ describing the island, $j$-th character of string $s_i$ equals "#" if cell $(i, j)$ contains an impassable forest and "." if the cell is free and passable. Let us remind you that Vasya gets of his ship at the cell $(1, 1)$, i.e. the first cell of the first row, and he wants to reach cell $(n, m)$, i.e. the last cell of the last row.

It's guaranteed, that cells $(1, 1)$ and $(n, m)$ are empty.


-----Output-----

Print the only integer $k$, which is the minimum number of cells Evil Witch has to turn into impassable forest in order to prevent Vasya from reaching the treasure.


-----Examples-----
Input
2 2
..
..

Output
2

Input
4 4
....
#.#.
....
.#..

Output
1

Input
3 4
....
.##.
....

Output
2



-----Note-----

The following picture illustrates the island in the third example. Blue arrows show possible paths Vasya may use to go from $(1, 1)$ to $(n, m)$. Red illustrates one possible set of cells for the Witch to turn into impassable forest to make Vasya's trip from $(1, 1)$ to $(n, m)$ impossible. [Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Anmol gained a lot of weight last semester. So this semester, he decided to run everyday. There is a very long straight road starting at his hostel. There are N poles on the road - P1, P2, P3,..., PN on the road. All the poles lie on the same side of his hostel. The distance between Pi and his hostel is Di.
For 1 ≤ i, j ≤ N, i < j implies Di < Dj
Everyday, Anmol chooses a pole Pi to start running from. He keeps on running until he reaches Pi+K. Whenever he reaches a pole (other than the starting pole), he records the distance traveled since the last pole.

You are given the distances recorded by him today. Your task is to find the number of distinct values of i such that i + K ≤ N and if he starts at Pi and end at Pi+K, he would end up having exactly the same record of distances (in the same order).

-----Input-----
- The first line of the input contains an integer T denoting the number of test cases.
- The first line of each test case contains two space separated integers N and K.
- The next line contains N space separated integers D1, D2,..., DN.
- The next line contains K space separated integers representing the distances recorded by Anmol in the same order.
.

-----Output-----
- For each test case, output a single line containing the answer for that test case.

-----Constraints-----
- 1 ≤ T ≤ 10
- 2 ≤ N ≤ 5 x 104
- 1 ≤ K < N
- 1 ≤ Di ≤ 106

-----Subtasks-----

-----Subtask #1 (20 points)-----
- 1 ≤ N ≤ 1000

-----Subtask #2 (80 points)-----
- Original constraints

-----Example-----
Input:
3
5 1
1 5 10 12 14
5
5 2
5 8 13 16 21
3 5
5 3
2 6 8 11 16
2 3 5

Output:
1
2
1

-----Explanation-----
Example case 1. If he runs from P2 to P3, he will record (5)
Example case 2. He can start at P1 or P3
Example case 3. He can start at P2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
“Arrange” is a planetary popular Flash game. In “Arrange” the player is given a permutation of numbers $1$ to $N$ and a list of allowed swaps. He then has to perform a sequence of swaps that transforms the initial permutation back to the ordered sequence $1,2,3,4,5, \ldots , N$.

In order to break the high score list, you need to perform the minimum amount of swaps possible. You can’t do that, but you can write a program that does it for you!

-----Input-----
The first line of input contains two integers, $N$ ($2 \le N \le 11$), the length of the initial sequence and $M$ ($1 \le M \le N(N – 1) / 2$), the number of allowed swaps.

The second line of input contains a permutation of the numbers $1$ to $N$.

The next $M$ lines contain descriptions of allowed swaps. Each such line contains two distinct numbers $1 \le A < B \le N$, indicating that you are allowed to swap the $A$-th number in the sequence with the $B$-th number. The input never contains two identical swaps.

You may assume that the input is such that a solution exists.

-----Output-----
Output the minimum possible number of swaps to transform the permutation to $1, 2, \ldots , N$.

-----Examples-----
Sample Input 1:
2 1
2 1
1 2
Sample Output 1:
1

Sample Input 2:
3 2
2 1 3
1 3
2 3
Sample Output 2:
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
While Omar was studying for Math lectures, he found the following problem.  
Given 3 Integers N_1, N_2, N_3, count the number of common divisors which divide all of them. 

Can you please help Omar in solving this problem, because he usually sleeps in lectures. 

Input:

Given an integer T, which indicates the number of test cases.
For each test case: given 3 separated integers N_1, N_2, N_3.  

Output:

For each test case: print the number of common divisors which divide N_1, N_2, N_3. Print each case in a separate line. 

** Constraints:**  

1 ≤ T ≤ 50  
1 ≤ minimum\; (N_1, N_2 , N_3) ≤ 10 ^ {12}  
1 ≤ maximum\; (N_1, N_2 , N_3) ≤ 10 ^ {18}   

SAMPLE INPUT
1
2 4 6

SAMPLE OUTPUT
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are involved in the development of a certain game. The game is for players to explore randomly generated dungeons. As a specification of the game, I want to show the player the danger level of the dungeon in advance and select whether to search for the generated dungeon or to regenerate a new dungeon.

There are n rooms in the dungeon generated by this game, and they are numbered from 0 to n-1. The rooms are connected by a passage. There are a total of n-1 passages connecting rooms. The passage can go in either direction. In addition, a distance is set between the rooms. In the generated dungeon, it is possible to go from one room to all other rooms via several passages. Then, when the player plays the game, two different rooms are selected as the start point and the goal point.

You decide to decide how to evaluate the risk in order to evaluate the dungeon. First, the risk level when moving from one room to another is set to the value of the most costly passage among the passages used to move between rooms in the shortest time. Then, we decided to set the risk level of the dungeon as the sum of the risk levels when moving between a pair of rooms where i <j.

A randomly generated dungeon is given as input. First, calculate the risk of moving for all room pairs where i <j. Then output the sum as the answer to the problem.



Input

The input is given in the following format.


n
a1 b1 c1
..
..
..
an-1 bn-1 cn-1


ai bi ci means that the distance of the passage connecting the rooms ai and bi is ci.

Input meets the following constraints
2 ≤ n ≤ 200,000
0 ≤ ai, bi <n
0 ≤ ci ≤ 100,000

Output

Print the answer value on one line

Examples

Input

4
0 1 3
1 2 5
1 3 2


Output

23


Input

6
0 2 5
2 1 1
2 3 10
3 5 4
3 4 2


Output

111

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Define two functions: `hex_to_bin` and `bin_to_hex` (or `hexToBin` and `binToHex`)


# hex_to_bin

Takes a hexadecimal string as an argument .

**Note:** This string can contain upper or lower case characters and start with any amount of zeros.

Returns the binary representation (without leading zeros) of the numerical value of the hexadecimal string.

Examples:

```
"00F"    -->  "1111"
"5"      -->  "101"
"00000"  -->  "0"
"04D2"   -->  "10011010010"
```

# bin_to_hex

Takes a binary string (with or without leading zeros) as an argument .

Returns the hexadecimal representation of the numerical value of the binary string.

**Note:** Any non-numerical characters should be lower case


Examples:

```
"1111"         -->  "f"
"000101"       -->  "5"
"10011010010"  -->  "4d2"
```

**Note:** You can assume all arguments are valid so there is no need for error checking.

Oh, and I've disabled a few things.


Any feedback would be much appreciated

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef is playing a game with two of his friends. In this game, each player chooses an integer between $1$ and $P$ inclusive. Let's denote the integers chosen by Chef, friend 1 and friend 2 by $i$, $j$ and $k$ respectively; then,  Chef's score is
(((Nmodi)modj)modk)modN.(((Nmodi)modj)modk)modN.(((N\,\mathrm{mod}\,i)\,\mathrm{mod}\,j)\,\mathrm{mod}\,k)\,\mathrm{mod}\,N\,.

Chef wants to obtain the maximum possible score. Let's denote this maximum score by $M$. Find the number of ways to choose the triple $(i,j,k)$ so that Chef's score is equal to $M$.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first and only line of each test case contains two space-separated integers $N$ and $P$.

-----Output-----
For each test case, print a single line containing one integer — the number of ways to obtain the maximum score.

-----Constraints-----
- $1 \le T \le 10^6$
- $1 \le N \le P \le 10^6$

-----Subtasks-----
Subtask #1 (10 points):
- $1 \le T \le 100$
- $1 \le N \le P \le 100$
Subtask #2 (90 points): original constraints

-----Example Input-----
2
4 4
3 4

-----Example Output-----
9
13

-----Explanation-----
Example case 1: Chef's maximum possible score is $M = 1$. All possible values of $(i, j, k)$ such that the score is $1$ are
$(3, 2, 2)$,
$(3, 2, 3)$,
$(3, 2, 4)$,
$(3, 3, 2)$,
$(3, 3, 3)$,
$(3, 3, 4)$,
$(3, 4, 2)$,
$(3, 4, 3)$,
$(3, 4, 4)$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Brain Network (easy)

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
One particularly well-known fact about zombies is that they move and think terribly slowly. While we still don't know why their movements are so sluggish, the problem of laggy thinking has been recently resolved. It turns out that the reason is not (as previously suspected) any kind of brain defect – it's the opposite! Independent researchers confirmed that the nervous system of a zombie is highly complicated – it consists of *n* brains (much like a cow has several stomachs). They are interconnected by brain connectors, which are veins capable of transmitting thoughts between brains. There are two important properties such a brain network should have to function properly: 
 1.  It should be possible to exchange thoughts between any two pairs of brains (perhaps indirectly, through other brains). 1.  There should be no redundant brain connectors, that is, removing any brain connector would make property 1 false. 
If both properties are satisfied, we say that the nervous system is valid. Unfortunately (?), if the system is not valid, the zombie stops thinking and becomes (even more) dead. Your task is to analyze a given nervous system of a zombie and find out whether it is valid.

Input Specification:
The first line of the input contains two space-separated integers *n* and *m* (1<=≤<=*n*,<=*m*<=≤<=1000) denoting the number of brains (which are conveniently numbered from 1 to *n*) and the number of brain connectors in the nervous system, respectively. In the next *m* lines, descriptions of brain connectors follow. Every connector is given as a pair of brains *a* *b* it connects (1<=≤<=*a*,<=*b*<=≤<=*n*, *a*<=≠<=*b*).

Output Specification:
The output consists of one line, containing either yes or no depending on whether the nervous system is valid.

Demo Input:
['4 4\n1 2\n2 3\n3 1\n4 1\n', '6 5\n1 2\n2 3\n3 4\n4 5\n3 6\n']

Demo Output:
['no\n', 'yes\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Every one is now a days playing games on their smartphones for passing free time. Because of which there are number of game developing companies growing in the market. Not only that, each company is now flooding the market with a lot of games. With such a huge number of games in the market, for each company, with millions of users, keeping track of all the data and maintaining good user experience is now a big problem for them.

One of the very important aspect of building these games is the ability to maintain all the information about the user. 
This is a very important step in maintaining the user experience. No user would want to restart from the beginning of the game every time he/she restarts it. They would just then switch to a competitive game developer and that is not good for business.
Most of the games now have a similar structure and some of the game companies follows the logic below in their games to handle this problem:
The game has N different parameters on which a user's strength in the game is calculated. The game has a total of M different levels of play.
    And hence each parameter also gets these M levels of granularity, i.e. for each parameter itself a user can be on any one of those M levels.
For each parameter, the following is done:
    
User's strength on the parameter is calculated.
Each of the M levels have some strength value associated with them such that the strength value grows when you move from a lower level to the higher level. It may happen that any two consecutive levels have same required strength.
If a user's strength is more than or equal to the strength value associated with a level, he/she is said to be fit to be on that level of the game
        for this parameter.
The level for this parameter is the maximum level for which a user satisfies the above criteria.
The level of the game a user is on, is decided from its level in all of the N parameters of the game as follows:
    
For each parameter, the level user is on for that parameter is computed as described above.
The level of game at which a user is the minimum of all the levels in each of the N parameters.

You are now interested in building a game for the smartphone user's as well. But before that, you would need to solve this problem effeciently.
Given the strength of user's for each parameter, print the level they are on.

Input:
The first line of the input contains three space separated integers, N, M and Q. (N is the number of parameters, M is the number of levels, and Q is the 
number of queries that you have to answer.) 
Next N line contains M space separated integers, the i^th line contains the M strength values for the M levels of the i^th
level.

Next Q lines, each contains N space separated integers, the strength of a user in each of the N parameters.

Output:
Print Q lines, one for each query. For each query, print the level on which that user is.

Constraints:
1 ≤ N ≤ 100 
1 ≤ M ≤ 5000 
1 ≤ Q ≤ 5000  
Every input will fit in an integer.

SAMPLE INPUT
2 3 3
10 20 30
7 14 100
11 7
35 13
100 1002

SAMPLE OUTPUT
1
1
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
### Combine strings function
```if:coffeescript,haskell,javascript
Create a function named `combineNames` that accepts two parameters (first and last name). The function should return the full name.
```
```if:python,ruby
Create a function named (`combine_names`) that accepts two parameters (first and last name). The function should return the full name.
```
```if:csharp
Create a function named (`Combine_names`) that accepts two parameters (first and last name). The function should return the full name.
```

Example: 
```python
combine_names('James', 'Stevens')
```
returns:
```python
'James Stevens'
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A number of regional Internet Service Providers (ISPs), both big and small have recently been forced into a merger by the government, in an effort to improve service for all. Of course this has been decided without consulting you, the chief network infrastructure officer, and a deadline for when the ISPs should be merged have already been set.

You have a set of $n$ servers, each with a limited number of network sockets that can be used for connecting physically to other servers. Some servers are already linked up in the existing network architecture, and if server 0 is linked to server 2, then 2 is also linked to server 0 (as you use full duplex ethernet Cat6 cables). No server is directly connected to itself, and no two servers are directly linked with more than one connection.

You want to connect the servers to form a single network, such that all servers can reach each other through some sequence of connections. To make the set deadline, you have estimated that you only have time to make $k$ edits to the existing network infrastructure. An edit is either to remove an existing connection between two servers, or to add a new connection between two servers.

Can you connect all the servers to the same network using at most $k$ edits, within the limitations on the number of network sockets in each server?

-----Input-----
The first line of the input is three space separated integers $n$ ($1 \leq n \leq 100000$), the number of servers, $m$ ($0 \leq m \leq 200000$), the number of existing connections and $k$ ($0 \leq k \leq 50000$), the number of edits you have time to make. Then follows a line with $n$ integers $c_0, c_1, \ldots , c_ i, \ldots , c_{n-1}$, with the $i$’th number giving the number of network sockets for the $i$’th server (for all $i$ the capacity is bounded by $1 \leq c_ i < n$). Then $m$ lines follow, with two integers $u_ j$ and $v_ j$ each, giving the id’s of two servers that are connected in the old network architecture. Servers are $0$-indexed, i.e. for every $j$, it holds that $0 \leq u_ j, v_ j < n$. A server will never be connected to more servers than it has connection sockets.

-----Output-----
Output “yes” on a single line if the servers can be connected to one network by making $k$ or less edits, and “no” if it is not possible.

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

Sample Input 2:
5 4 4
1 1 2 2 2
0 1
2 3
3 4
4 2
Sample Output 2:
yes

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
ZS the Coder has drawn an undirected graph of n vertices numbered from 0 to n - 1 and m edges between them. Each edge of the graph is weighted, each weight is a positive integer.

The next day, ZS the Coder realized that some of the weights were erased! So he wants to reassign positive integer weight to each of the edges which weights were erased, so that the length of the shortest path between vertices s and t in the resulting graph is exactly L. Can you help him?

Input

The first line contains five integers n, m, L, s, t (2 ≤ n ≤ 1000, 1 ≤ m ≤ 10 000, 1 ≤ L ≤ 109, 0 ≤ s, t ≤ n - 1, s ≠ t) — the number of vertices, number of edges, the desired length of shortest path, starting vertex and ending vertex respectively.

Then, m lines describing the edges of the graph follow. i-th of them contains three integers, ui, vi, wi (0 ≤ ui, vi ≤ n - 1, ui ≠ vi, 0 ≤ wi ≤ 109). ui and vi denote the endpoints of the edge and wi denotes its weight. If wi is equal to 0 then the weight of the corresponding edge was erased.

It is guaranteed that there is at most one edge between any pair of vertices.

Output

Print "NO" (without quotes) in the only line if it's not possible to assign the weights in a required way.

Otherwise, print "YES" in the first line. Next m lines should contain the edges of the resulting graph, with weights assigned to edges which weights were erased. i-th of them should contain three integers ui, vi and wi, denoting an edge between vertices ui and vi of weight wi. The edges of the new graph must coincide with the ones in the graph from the input. The weights that were not erased must remain unchanged whereas the new weights can be any positive integer not exceeding 1018. 

The order of the edges in the output doesn't matter. The length of the shortest path between s and t must be equal to L.

If there are multiple solutions, print any of them.

Examples

Input

5 5 13 0 4
0 1 5
2 1 2
3 2 3
1 4 0
4 3 4


Output

YES
0 1 5
2 1 2
3 2 3
1 4 8
4 3 4


Input

2 1 123456789 0 1
0 1 0


Output

YES
0 1 123456789


Input

2 1 999999999 1 0
0 1 1000000000


Output

NO

Note

Here's how the graph in the first sample case looks like :

<image>

In the first sample case, there is only one missing edge weight. Placing the weight of 8 gives a shortest path from 0 to 4 of length 13.

In the second sample case, there is only a single edge. Clearly, the only way is to replace the missing weight with 123456789.

In the last sample case, there is no weights to assign but the length of the shortest path doesn't match the required value, so the answer is "NO".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The itertools module standardizes a core set of fast, memory efficient tools that are useful by themselves or in combination. Together, they form an iterator algebra making it possible to construct specialized tools succinctly and efficiently in pure Python. 

To read more about the functions in this module, check out their documentation here. 

You are given a list of $N$ lowercase English letters. For a given integer $\mbox{K}$, you can select any $\mbox{K}$ indices (assume $\mbox{I}$-based indexing) with a uniform probability from the list.  

Find the probability that at least one of the $\mbox{K}$ indices selected will contain the letter: '$\boldsymbol{\alpha}$'.  

Input Format

The input consists of three lines. The first line contains the integer $N$, denoting the length of the list. The next line consists of $N$ space-separated lowercase English letters, denoting the elements of the list. 

The third and the last line of input contains the integer $\mbox{K}$, denoting the number of
indices to be selected. 

Output Format

Output a single line consisting of the probability that at least one of the $\mbox{K}$ indices selected contains the letter:'$\boldsymbol{\alpha}$'. 

Note: The answer must be correct up to 3 decimal places. 

Constraints

$1\leq N\leq10$

$1\leq K\leq N$

All the letters in the list are lowercase English letters.

Sample Input

4 
a a c d
2

Sample Output

0.8333

Explanation

All possible unordered tuples of length $2$ comprising of indices from $\mbox{I}$ to $\begin{array}{c}A\end{array}$ are:

$(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)$ 

Out of these $\boldsymbol{6}$ combinations, $5$ of them contain either index $\mbox{I}$ or index $2$ which are the indices that contain the letter '$\boldsymbol{\alpha}$'. 

Hence, the answer is $\frac{5}{6}$.

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