vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Keyboard Layouts

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
There are two popular keyboard layouts in Berland, they differ only in letters positions. All the other keys are the same. In Berland they use alphabet with 26 letters which coincides with English alphabet.

You are given two strings consisting of 26 distinct letters each: all keys of the first and the second layouts in the same order. 

You are also given some text consisting of small and capital English letters and digits. It is known that it was typed in the first layout, but the writer intended to type it in the second layout. Print the text if the same keys were pressed in the second layout.

Since all keys but letters are the same in both layouts, the capitalization of the letters should remain the same, as well as all other characters.

Input Specification:
The first line contains a string of length 26 consisting of distinct lowercase English letters. This is the first layout.

The second line contains a string of length 26 consisting of distinct lowercase English letters. This is the second layout.

The third line contains a non-empty string *s* consisting of lowercase and uppercase English letters and digits. This is the text typed in the first layout. The length of *s* does not exceed 1000.

Output Specification:
Print the text if the same keys were pressed in the second layout.

Demo Input:
['qwertyuiopasdfghjklzxcvbnm\nveamhjsgqocnrbfxdtwkylupzi\nTwccpQZAvb2017\n', 'mnbvcxzlkjhgfdsapoiuytrewq\nasdfghjklqwertyuiopzxcvbnm\n7abaCABAABAcaba7\n']

Demo Output:
['HelloVKCup2017\n', '7uduGUDUUDUgudu7\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Read problems statements in Mandarin Chinese  and Russian  

Eugene has a sequence of upper hemispheres and another of lower hemispheres. The first set consists of N upper hemispheres indexed 1 to N and the second has M lower hemispheres indexed 1 to M. The hemispheres in any sequence can have different radii.
He is now set out on building spheres using them. To build a sphere of radius R, he must take one upper half of the radius R and one lower half of the radius R. Also, he can put a sphere into a bigger one and create a sequence of nested concentric spheres. But he can't put two or more spheres directly into another one.
Examples: 

If there is a sequence of (D+1) nested spheres, we can call this sequence as a D-sequence.

Eugene has to find out how many different X-sequence are possible (1 ≤ X ≤ C). An X sequence is different from another if the index of any of the hemisphere used in one X-sequence is different from the other. Eugene doesn't know how to do it, so Chef agreed to help him. Of course, Chef is too busy now and he asks you to help him.

------ Input ------ 

The first line contains a three integers: N denoting the number of upper sphere halves, M denoting the number of lower sphere halves and C.
The second line contains N space-separated integers U_{1}, U_{2}, ..., U_{N} denoting the radii of upper hemispheres.
The third line contains M space-separated integers L_{1}, L_{2}, ..., L_{M} denoting the radii of lower hemispheres.

------ Output ------ 

Output a single line containing C space-separated integers D_{1}, D_{2}, ..., D_{C}, where D_{i} is the number of ways there are to build i-sequence in modulo 10^{9}+7.

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

$1 ≤ N ≤ 10^{5}$
$1 ≤ M ≤ 10^{5}$
$1 ≤ C ≤ 10^{3}$
$1 ≤ U_{i} ≤ C$
$1 ≤ L_{i} ≤ C$

------ Subtasks ------ 

$Subtask 1:  1 ≤ N, M, C ≤ 10 - 15 points$
$Subtask 2: 1 ≤ N, M, C ≤ 100 - 25 points$
$Subtask 3: Original constraints - 60 points$

----- Sample Input 1 ------ 
3 4 3
1 2 3
1 1 3 2
----- Sample Output 1 ------ 
5 2 0
----- explanation 1 ------ 

We can build spheres with such radii:
R=1 and there are 2 ways to do it. (We can choose any of 2 lower hemispheres with R=1)
R=2 and there is 1 way to do it.
R=3 and there is 1 way to do it.

We can build these 1-sequences:
1->2 and there are 2 ways to do it. ( sphere with radius 1 is inside sphere with radius 2, we can choose any of 2 ways of building sphere with radius 1)
1->3 and there are 2 ways to do it.
2->3 and there is 1 way to do it.

2 + 2 + 1 = 5

We can build these 2-sequences:
1->2->3 and there are 2 ways to do it.

We can't build 3-sequences, because we don't have 4 spheres of different radii.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Božo is a strange little boy. Every day he tires his friends with strange questions. Today’s question is: how many integers in the interval $[A, B]$ are there such that the sum of their digits is $S$, and which is the smallest such number?

Write a program that answers Božo’s question so that he can get some sleep.

-----Input-----
The input contains three integers $A$, $B$ and $S$ ($1 \le A \le B < 10^{15}$, $1 \le S \le 135$).

-----Output-----
The first line should contain the number of integers in the interval with the digit sum equal to $S$.

The second line should contain the smallest such integer.

The input data will guarantee that the first number is at least $1$.

-----Examples-----
Sample Input 1:
1 9 5
Sample Output 1:
1
5

Sample Input 2:
1 100 10
Sample Output 2:
9
19

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array of $n$ integers: $a_1, a_2, \ldots, a_n$. Your task is to find some non-zero integer $d$ ($-10^3 \leq d \leq 10^3$) such that, after each number in the array is divided by $d$, the number of positive numbers that are presented in the array is greater than or equal to half of the array size (i.e., at least $\lceil\frac{n}{2}\rceil$). Note that those positive numbers do not need to be an integer (e.g., a $2.5$ counts as a positive number). If there are multiple values of $d$ that satisfy the condition, you may print any of them. In case that there is no such $d$, print a single integer $0$.

Recall that $\lceil x \rceil$ represents the smallest integer that is not less than $x$ and that zero ($0$) is neither positive nor negative.


-----Input-----

The first line contains one integer $n$ ($1 \le n \le 100$) — the number of elements in the array.

The second line contains $n$ space-separated integers $a_1, a_2, \ldots, a_n$ ($-10^3 \le a_i \le 10^3$).


-----Output-----

Print one integer $d$ ($-10^3 \leq d \leq 10^3$ and $d \neq 0$) that satisfies the given condition. If there are multiple values of $d$ that satisfy the condition, you may print any of them. In case that there is no such $d$, print a single integer $0$.


-----Examples-----
Input
5
10 0 -7 2 6
Output
4
Input
7
0 0 1 -1 0 0 2

Output
0


-----Note-----

In the first sample, $n = 5$, so we need at least $\lceil\frac{5}{2}\rceil = 3$ positive numbers after division. If $d = 4$, the array after division is $[2.5, 0, -1.75, 0.5, 1.5]$, in which there are $3$ positive numbers (namely: $2.5$, $0.5$, and $1.5$).

In the second sample, there is no valid $d$, so $0$ should be printed.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The lockdown hasn’t been great for our chef as his restaurant business got sabotaged because of lockdown, nevertheless no worries our chef is a multi-talented guy. Chef has decided to be a freelancer and work remotely. According to chef’s maths, he should be able to work on maximum tasks assuming that he can only work on a single task at a time. 
Assume that chef does N tasks. The start and finish time units of those tasks are given. Select the maximum number of tasks that can be performed by a chef, assuming that a he can only work on a single task at a time.

-----Input:-----
- The first input contains of size of array N representing the total number of tasks.
- The second and third lines contains N space-seperated integers representing the starting and finish time of the the tasks.

-----Output:-----
A single line containing indices of tasks that chef will be able to do.

-----Constraints-----
- $1 \leq N \leq 10^5$
- Note: The lists have been sorted based on the ending times of the tasks.

-----Sample Input 1:-----
3

10 12 20

20 25 30  

-----Sample Output 1:-----
0  2 

-----Sample Input 2:-----
6

1 2 0 6 3 7

2 4 5 7 9 10  

-----Sample Output 2:-----
0  1  3  5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ada, Bertrand and Charles often argue over which TV shows to watch, and to avoid some of their fights they have finally decided to buy a video tape recorder. This fabulous, new device can record $k$ different TV shows simultaneously, and whenever a show recorded in one the machine’s $k$ slots ends, the machine is immediately ready to record another show in the same slot.

The three friends wonder how many TV shows they can record during one day. They provide you with the TV guide for today’s shows, and tell you the number of shows the machine can record simultaneously. How many shows can they record, using their recording machine? Count only shows that are recorded in their entirety.

-----Input-----
The first line of input contains two integers $n,k$ ($1\leq k < n \leq 100\ 000$). Then follow $n$ lines, each containing two integers $x_ i,y_ i$, meaning that show $i$ starts at time $x_ i$ and finishes by time $y_ i$. This means that two shows $i$ and $j$, where $y_ i = x_ j$, can be recorded, without conflict, in the same recording slot. You may assume that $0 \leq x_{i} < y_{i} \leq 1\ 000\ 000\ 000$.

-----Output-----
The output should contain exactly one line with a single integer: the maximum number of full shows from the TV guide that can be recorded with the tape recorder.

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

Sample Input 2:
4 1
1 3
4 6
7 8
2 5
Sample Output 2:
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string s of '(' , ')' and lowercase English characters. 
Your task is to remove the minimum number of parentheses ( '(' or ')', in any positions ) so that the resulting parentheses string is valid and return any valid string.
Formally, a parentheses string is valid if and only if:

It is the empty string, contains only lowercase characters, or
It can be written as AB (A concatenated with B), where A and B are valid strings, or
It can be written as (A), where A is a valid string.

 
Example 1:
Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"
Explanation: "lee(t(co)de)" , "lee(t(c)ode)" would also be accepted.

Example 2:
Input: s = "a)b(c)d"
Output: "ab(c)d"

Example 3:
Input: s = "))(("
Output: ""
Explanation: An empty string is also valid.

Example 4:
Input: s = "(a(b(c)d)"
Output: "a(b(c)d)"

 
Constraints:

1 <= s.length <= 10^5
s[i] is one of  '(' , ')' and lowercase English letters.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
They say that Berland has exactly two problems, fools and roads. Besides, Berland has *n* cities, populated by the fools and connected by the roads. All Berland roads are bidirectional. As there are many fools in Berland, between each pair of cities there is a path (or else the fools would get upset). Also, between each pair of cities there is no more than one simple path (or else the fools would get lost). 

But that is not the end of Berland's special features. In this country fools sometimes visit each other and thus spoil the roads. The fools aren't very smart, so they always use only the simple paths.

A simple path is the path which goes through every Berland city not more than once.

The Berland government knows the paths which the fools use. Help the government count for each road, how many distinct fools can go on it.

Note how the fools' paths are given in the input.

Input Specification:
The first line contains a single integer *n* (2<=≤<=*n*<=≤<=105) — the number of cities. 

Each of the next *n*<=-<=1 lines contains two space-separated integers *u**i*,<=*v**i* (1<=≤<=*u**i*,<=*v**i*<=≤<=*n*, *u**i*<=≠<=*v**i*), that means that there is a road connecting cities *u**i* and *v**i*. 

The next line contains integer *k* (0<=≤<=*k*<=≤<=105) — the number of pairs of fools who visit each other. 

Next *k* lines contain two space-separated numbers. The *i*-th line (*i*<=&gt;<=0) contains numbers *a**i*,<=*b**i* (1<=≤<=*a**i*,<=*b**i*<=≤<=*n*). That means that the fool number 2*i*<=-<=1 lives in city *a**i* and visits the fool number 2*i*, who lives in city *b**i*. The given pairs describe simple paths, because between every pair of cities there is only one simple path.

Output Specification:
Print *n*<=-<=1 integer. The integers should be separated by spaces. The *i*-th number should equal the number of fools who can go on the *i*-th road. The roads are numbered starting from one in the order, in which they occur in the input.

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

Demo Output:
['2 1 1 1 \n', '3 1 1 1 \n']

Note:
In the first sample the fool number one goes on the first and third road and the fool number 3 goes on the second, first and fourth ones.

In the second sample, the fools number 1, 3 and 5 go on the first road, the fool number 5 will go on the second road, on the third road goes the fool number 3, and on the fourth one goes fool number 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string text of words that are placed among some number of spaces. Each word consists of one or more lowercase English letters and are separated by at least one space. It's guaranteed that text contains at least one word.
Rearrange the spaces so that there is an equal number of spaces between every pair of adjacent words and that number is maximized. If you cannot redistribute all the spaces equally, place the extra spaces at the end, meaning the returned string should be the same length as text.
Return the string after rearranging the spaces.
 
Example 1:
Input: text = "  this   is  a sentence "
Output: "this   is   a   sentence"
Explanation: There are a total of 9 spaces and 4 words. We can evenly divide the 9 spaces between the words: 9 / (4-1) = 3 spaces.

Example 2:
Input: text = " practice   makes   perfect"
Output: "practice   makes   perfect "
Explanation: There are a total of 7 spaces and 3 words. 7 / (3-1) = 3 spaces plus 1 extra space. We place this extra space at the end of the string.

Example 3:
Input: text = "hello   world"
Output: "hello   world"

Example 4:
Input: text = "  walks  udp package   into  bar a"
Output: "walks  udp  package  into  bar  a "

Example 5:
Input: text = "a"
Output: "a"

 
Constraints:

1 <= text.length <= 100
text consists of lowercase English letters and ' '.
text contains at least one word.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Koa the Koala has a directed graph G with n nodes and m edges. Each edge has a capacity associated with it. Exactly k edges of the graph, numbered from 1 to k, are special, such edges initially have a capacity equal to 0.

Koa asks you q queries. In each query she gives you k integers w_1, w_2, …, w_k. This means that capacity of the i-th special edge becomes w_i (and other capacities remain the same).

Koa wonders: what is the [maximum flow](https://en.wikipedia.org/wiki/Maximum_flow_problem#Definition) that goes from node 1 to node n after each such query?

Help her!

Input

The first line of the input contains four integers n, m, k, q (2 ≤ n ≤ 10^4, 1 ≤ m ≤ 10^4, 1 ≤ k ≤ min(10, m), 1 ≤ q ≤ 2 ⋅ 10^5) — the number of nodes, the number of edges, the number of special edges and the number of queries.

Each of the next m lines contains three integers u, v, w (1 ≤ u, v ≤ n; 0 ≤ w ≤ 25) — the description of a directed edge from node u to node v with capacity w.

Edges are numbered starting from 1 in the same order they are listed in the input. The first k edges are the special edges. It is guaranteed that w_i = 0 for all i with 1 ≤ i ≤ k.

Each of the next q lines contains k integers w_1, w_2, …, w_k (0 ≤ w_i ≤ 25) — the description of the query. w_i denotes the capacity of i-th edge.

Output

For the i-th query, print one integer res_i — the maximum flow that can be obtained from node 1 to node n given the i-th query's special edge weights.

Examples

Input


2 1 1 3
1 2 0
0
1
2


Output


0
1
2


Input


4 4 2 5
1 2 0
2 3 0
2 4 5
3 4 2
0 0
1 10
10 0
7 1
7 2


Output


0
1
5
6
7

Note

For the second sample, the following images correspond to the first two queries (from left to right respectively). For each edge there is a pair flow/capacity denoting flow pushed through the edge and edge's capacity. The special edges are colored in red.

<image>

As you can see in first query maximum flow from node 1 to node 4 equals 0 and in second query equals 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Today is the planned day tor Thik and Ayvak's wedding. Kark is infatuated with Ayvak. He offers to play a game with Thik. Whosoever wins, will get to marry Ayvak. Ayvak, who values games of chance over all the other things in life, agrees to this.

Kark sets up an N by M grid (N rows, M columns), labelled from left to right and top to bottom consecutively with numbers from 1 to M*N, with 1 at the top left corner and M*N at the bottom right corner. For example, a labelled 3 by 6 grid looks as follows:

Kark has already painted K unit squares of the grid with a heart each. Next, Thik randomly picks a rectangle with sides on the grid lines, and having a positive area, with each valid rectangle having an equal probability of being chosen. Three distinct possibilities for Thik's rectangle in the 3 by 6 grid are shown below: 

The nine different rectangles in a 2 by 2 grid are shown below:


If Thik's rectangle contains at least half of the hearts, Thik gets to marry Ayvak. Otherwise, Kark will marry Ayvak. Kark wants to know whether or not he has an advantage here, so he wants to know the expected value of the number of hearts a randomly chosen rectangle will cover. I'm sure that you have a good heart, so please, cover this job for him. 

-----Input-----
The first line of input contains one integer T, the number of test cases.
For each test case, the first line contains 3 space-separated integers N, M, K, as described in the problem statement. The next line contains K space-separated integers, each a single number from 1 to M*N, representing a square that is painted with a heart. It is guaranteed that all K integers are distinct.

-----Output-----
Output T lines, each containing a single real number, containing the expected number of hearts that a randomly chosen rectangle will contain. The answer will be considered correct if its relative or absolute error does not exceed 10-6.

-----Constraints-----
- 1 ≤ T ≤ 5  
- 1 ≤ N, M ≤ 107  
- 1 ≤ K ≤ 105 
- Each of the K integers representing a heart are between 1 and N*M, inclusive. All K integers are distinct. 

-----Subtasks-----Subtask 1 (15 points) : 

- 1 ≤ N, M ≤ 10
- 1 ≤ K ≤ N * M  
Subtask 2 (85 points) : no additional constraints 


-----Example-----
Input:
1
2 2 2
1 2

Output:
0.8888888888888888

-----Explanation-----
There are a total of 9 possible rectangles Thik could draw, shown in the figure above, and grid squares 1 and 2 are painted with a heart. The top row of possible selections (shown in the figure) contain 1, 0, 1, 2, and 2 hearts (from left to right), and the bottom row of possible selections (in the figure) contain 1, 0, 1, and 0 hearts. Therefore, 3/9 of the time 0 hearts are contained in the rectangle, 4/9 of the times 1 heart is contained in the rectangle, and 2/9 of the time 2 hearts are contained in the rectangle. The expected value is then 0 * 3/9 + 1 * 4/9 + 2 * 2/9 = 8/9.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array arr[] of n numbers. The task is to print only those numbers whose digits are from set {1,2,3}.
Example 1:
Input:
n = 3
arr[] = {4,6,7}
Output: -1
Explanation: No elements are there in the 
array which contains digits 1, 2 or 3.
Example 2:
Input:
n = 4
arr[] = {1,2,3,4}
Output: 1 2 3
Explanation: 1, 2 and 3 are the only 
elements in the array which conatins 
digits as 1, 2 or 3.
Your Task:
Complete findAll function and marked satisfied number as '1' in the map mp in range 1 to 1000000. If no number is marked as satified number -1 will automatically be printed by the drivers code. The driver code prints the elements in sorted order.
Expected Time Complexity : O(n)
Expected Auxilliary Space : O(n)
Constraints:
1 <= n <= 10^{6}
1 <= A[i] <= 10^{6}

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Little Vlad is fond of popular computer game Bota-2. Recently, the developers announced the new add-on named Bota-3. Of course, Vlad immediately bought only to find out his computer is too old for the new game and needs to be updated.

There are *n* video cards in the shop, the power of the *i*-th video card is equal to integer value *a**i*. As Vlad wants to be sure the new game will work he wants to buy not one, but several video cards and unite their powers using the cutting-edge technology. To use this technology one of the cards is chosen as the leading one and other video cards are attached to it as secondary. For this new technology to work it's required that the power of each of the secondary video cards is divisible by the power of the leading video card. In order to achieve that the power of any secondary video card can be reduced to any integer value less or equal than the current power. However, the power of the leading video card should remain unchanged, i.e. it can't be reduced.

Vlad has an infinite amount of money so he can buy any set of video cards. Help him determine which video cards he should buy such that after picking the leading video card and may be reducing some powers of others to make them work together he will get the maximum total value of video power.

Input Specification:
The first line of the input contains a single integer *n* (1<=≤<=*n*<=≤<=200<=000) — the number of video cards in the shop.

The second line contains *n* integers *a*1, *a*2, ..., *a**n* (1<=≤<=*a**i*<=≤<=200<=000) — powers of video cards.

Output Specification:
The only line of the output should contain one integer value — the maximum possible total power of video cards working together.

Demo Input:
['4\n3 2 15 9\n', '4\n8 2 2 7\n']

Demo Output:
['27\n', '18\n']

Note:
In the first sample, it would be optimal to buy video cards with powers 3, 15 and 9. The video card with power 3 should be chosen as the leading one and all other video cards will be compatible with it. Thus, the total power would be 3 + 15 + 9 = 27. If he buys all the video cards and pick the one with the power 2 as the leading, the powers of all other video cards should be reduced by 1, thus the total power would be 2 + 2 + 14 + 8 = 26, that is less than 27. Please note, that it's not allowed to reduce the power of the leading video card, i.e. one can't get the total power 3 + 1 + 15 + 9 = 28.

In the second sample, the optimal answer is to buy all video cards and pick the one with the power 2 as the leading. The video card with the power 7 needs it power to be reduced down to 6. The total power would be 8 + 2 + 2 + 6 = 18.

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