vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Snuke's town has a subway system, consisting of N stations and M railway lines. The stations are numbered 1 through N. Each line is operated by a company. Each company has an identification number.
The i-th ( 1 \leq i \leq M ) line connects station p_i and q_i bidirectionally. There is no intermediate station. This line is operated by company c_i.
You can change trains at a station where multiple lines are available.
The fare system used in this subway system is a bit strange. When a passenger only uses lines that are operated by the same company, the fare is 1 yen (the currency of Japan). Whenever a passenger changes to a line that is operated by a different company from the current line, the passenger is charged an additional fare of 1 yen. In a case where a passenger who changed from some company A's line to another company's line changes to company A's line again, the additional fare is incurred again.
Snuke is now at station 1 and wants to travel to station N by subway. Find the minimum required fare.

-----Constraints-----
 - 2 \leq N \leq 10^5
 - 0 \leq M \leq 2×10^5
 - 1 \leq p_i \leq N (1 \leq i \leq M)
 - 1 \leq q_i \leq N (1 \leq i \leq M)
 - 1 \leq c_i \leq 10^6 (1 \leq i \leq M)
 - p_i \neq q_i (1 \leq i \leq M)

-----Input-----
The input is given from Standard Input in the following format:
N M
p_1 q_1 c_1
:
p_M q_M c_M

-----Output-----
Print the minimum required fare. If it is impossible to get to station N by subway, print -1 instead.

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

-----Sample Output-----
1

Use company 1's lines: 1 → 2 → 3. The fare is 1 yen.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given is an integer N. Find the number of positive integers less than or equal to N that have an odd number of digits (in base ten without leading zeros).

-----Constraints-----
 - 1 \leq N \leq 10^5

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

-----Output-----
Print the number of positive integers less than or equal to N that have an odd number of digits.

-----Sample Input-----
11

-----Sample Output-----
9

Among the positive integers less than or equal to 11, nine integers have an odd number of digits: 1, 2, \ldots, 9.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Lazy boy has gone home during his vacations. As it is the season of Holi, his mother expects him to

do some of her work so that she can relax a little bit. However, since lazy boy is lazy, he wants to do

as less work as possible, giving him more time to sleep, as lazy boy loves to sleep. However, he also

knows that he needs to do a minimum amount of work, otherwise he will be scolded by his father

for being too lazy. There are n distinct tasks that her mother asks him to do, and each task has an associated

amount of work with it. Lazy boy knows how much amount of work he needs to do to avoid being

scolded by his father. He wants to do this much amount of work by doing the least number of tasks.

Also, he never does more than two distinct tasks. Lazy boy wants to know what is the minimum

number of tasks he should do so that the total amount of work done by him is equal to the required

amount of work to avoid being scolded. Lazy boy makes q such queries to you, you need to give an

answer for every query.

You will be given an array a, of n elements, giving the amount of work associated with each of the n

tasks, and a number k, meaning the lazy boy never does more than k tasks in total. After that there will be q

queries. For each query, which contains a single number, you need to tell what is the minimum

number of tasks he should do to achieve the amount of work given in the query. If it is not possible

to do so, output “:(” (without quotes).

Note : Lazy boy does at most two of the distinct tasks assigned by his mother, and he does not do more than k
tasks in total. He can repeat a task many times, as long as he does less than or equal to k tasks.

Input :

First line contains two integers n (number of tasks) and k (maximum number of tasks lazy boy

does).

Next line contains n space-separated integers, the array a, giving the amount of work associated

with each task.

Next line contains q, the number of queries.

Each query contains an integer x (the required amount of work to be done).

Output :

For each query, output the minimum number of tasks he should do so that total amount of work

done is equal to x. If it is not possible to do so, print “:(” (without quotes).

Constraints :

n ≤ 5000

k ≤ 20

ai ≤ 10^7

q ≤ 20

x ≤ 2*10^8

Problem setter : Sahil Prakash

SAMPLE INPUT
5 4
1 2 11 12 14
3
1
4
9

SAMPLE OUTPUT
1
2
:(

Explanation

Explaination (for 3 rd query) :
 Since it is not possible to get total amount of work done equal to 9 by

doing only two of the available tasks, not doing more than 4 tasks in total, the ouput is “:(”.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Petya loves lucky numbers. Everybody knows that lucky numbers are positive integers whose decimal representation contains only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Petya has a number consisting of *n* digits without leading zeroes. He represented it as an array of digits without leading zeroes. Let's call it *d*. The numeration starts with 1, starting from the most significant digit. Petya wants to perform the following operation *k* times: find the minimum *x* (1<=≤<=*x*<=&lt;<=*n*) such that *d**x*<==<=4 and *d**x*<=+<=1<==<=7, if *x* is odd, then to assign *d**x*<==<=*d**x*<=+<=1<==<=4, otherwise to assign *d**x*<==<=*d**x*<=+<=1<==<=7. Note that if no *x* was found, then the operation counts as completed and the array doesn't change at all.

You are given the initial number as an array of digits and the number *k*. Help Petya find the result of completing *k* operations.

Input Specification:
The first line contains two integers *n* and *k* (1<=≤<=*n*<=≤<=105,<=0<=≤<=*k*<=≤<=109) — the number of digits in the number and the number of completed operations. The second line contains *n* digits without spaces representing the array of digits *d*, starting with *d*1. It is guaranteed that the first digit of the number does not equal zero.

Output Specification:
In the single line print the result without spaces — the number after the *k* operations are fulfilled.

Demo Input:
['7 4\n4727447\n', '4 2\n4478\n']

Demo Output:
['4427477\n', '4478\n']

Note:
In the first sample the number changes in the following sequence: 4727447 → 4427447 → 4427477 → 4427447 → 4427477.

In the second sample: 4478 → 4778 → 4478.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string S, you have to check if we can split it into four strings such that each string is non-empty and distinct from each other.
 
Example 1:
Input :
S = "geeksforgeeks"
Output:
1
Explanation:
"geeks", "for", "gee", "ks" are four
distinct strings that can form from
given string.
Example 2:
Input: 
S = "aaabb" 
Output:
0
Explanation:
It's not possible to split string S in four
distinct strings
Your Task:  
You don't need to read input or print anything. Your task is to complete the function isPossible() which takes the string S as input parameter and returns 1 if it's possible to split S into four strings such that each string is non-empty and distinct from each other or return 0 otherwise. 
 
Expected Time Complexity: O(|S|^{3})
Expected Space Complexity: O(1)
Constraints:
1< |S| <=10000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a grid that consists of W \times H cells. The upper-left-most cell is (1, 1). You are standing on the cell of (1,1) and you are going to move to cell of (W, H). You can only move to adjacent lower-left, lower or lower-right cells.

There are obstructions on several cells. You can not move to it. You cannot move out the grid, either. Write a program that outputs the number of ways to reach (W,H) modulo 1,000,000,009. You can assume that there is no obstruction at (1,1).



Input

The first line contains three integers, the width W, the height H, and the number of obstructions N. (1 \leq W \leq 75, 2 \leq H \leq 10^{18}, 0 \leq N \leq 30) Each of following N lines contains 2 integers, denoting the position of an obstruction (x_i, y_i).

The last test case is followed by a line containing three zeros.

Output

For each test case, print its case number and the number of ways to reach (W,H) modulo 1,000,000,009.

Example

Input

2 4 1
2 1
2 2 1
2 2
0 0 0


Output

Case 1: 4
Case 2: 0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
=====Problem Statement=====
CSS colors are defined using a hexadecimal (HEX) notation for the combination of Red, Green, and Blue color values (RGB).

Specifications of HEX Color Code

It must start with a '#' symbol.
It can have 3 or 6 digits.
Each digit is in the range of 0 to F. (1, 2, 3, 4, 5, 6, 7, 8, 9, 0, A, B, C, D, E and F).
A – F letters can be lower case. (a, b, c, d, e and f are also valid digits).

Examples

Valid Hex Color Codes
#FFF 
#025 
#F0A1FB 

Invalid Hex Color Codes
#fffabg
#abcf
#12365erff

You are given N lines of CSS code. Your task is to print all valid Hex Color Codes, in order of their occurrence from top to bottom.

CSS Code Pattern

Selector
{
        Property: Value;
}

=====Input Format=====
The first line contains N, the number of code lines.
The next N lines contains CSS Codes.

=====Constraints=====
0<N<50

=====Output Format=====
Output the color codes with '#' symbols on separate lines.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Fox and Number Game

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Fox Ciel is playing a game with numbers now. 

Ciel has *n* positive integers: *x*1, *x*2, ..., *x**n*. She can do the following operation as many times as needed: select two different indexes *i* and *j* such that *x**i* &gt; *x**j* hold, and then apply assignment *x**i* = *x**i* - *x**j*. The goal is to make the sum of all numbers as small as possible.

Please help Ciel to find this minimal sum.

Input Specification:
The first line contains an integer *n* (2<=≤<=*n*<=≤<=100). Then the second line contains *n* integers: *x*1, *x*2, ..., *x**n* (1<=≤<=*x**i*<=≤<=100).

Output Specification:
Output a single integer — the required minimal sum.

Demo Input:
['2\n1 2\n', '3\n2 4 6\n', '2\n12 18\n', '5\n45 12 27 30 18\n']

Demo Output:
['2\n', '6\n', '12\n', '15\n']

Note:
In the first example the optimal way is to do the assignment: *x*<sub class="lower-index">2</sub> = *x*<sub class="lower-index">2</sub> - *x*<sub class="lower-index">1</sub>.

In the second example the optimal sequence of operations is: *x*<sub class="lower-index">3</sub> = *x*<sub class="lower-index">3</sub> - *x*<sub class="lower-index">2</sub>, *x*<sub class="lower-index">2</sub> = *x*<sub class="lower-index">2</sub> - *x*<sub class="lower-index">1</sub>.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Nikola owns a large warehouse which is illuminated by N light bulbs, numbered 1 to N. At the exit of the warehouse, there are S light switches, numbered 1 to S. Each switch swaps the on/off state for some light bulbs, so if a light bulb is off, flipping the switch turns it on, and if the light bulb is on, flipping the switch turns it off.

At the end of the day, Nikola wants to turn all the lights off. To achieve this, he will flip some of the light switches at the exit of the warehouse, but since Nikola is lazy, he wants to flip the _minimum_ number of switches required to turn all the lights off. Since Nikola was not able to calculate the minimum number of switches, he asked you to help him. During a period of D days, Nikola noted which light bulbs were off and which were on at the end of each day. He wants you to tell him the minimum number of switches he needed to flip to turn all the lights off for each of the D days or tell him that it's impossible.

Input

First line contains three integers, N, S and D (1 ≤ N ≤ 10^3, 1 ≤ S ≤ 30, 1 ≤ D ≤ 10^3) – representing number of light bulbs, the number of light switches, and the number of days respectively.

The next S lines contain the description of each light switch as follows: The first number in the line, C_i (1 ≤ C_i ≤ N), represents the number of light bulbs for which the on/off state is swapped by light switch i, the next C_i numbers (sorted in increasing order) represent the indices of those light bulbs.

The next D lines contain the description of light bulbs for each day as follows: The first number in the line, T_i (1 ≤ T_i ≤ N), represents the number of light bulbs which are on at the end of day i, the next T_i numbers (sorted in increasing order) represent the indices of those light bulbs.

Output

Print D lines, one for each day. In the i^{th} line, print the minimum number of switches that need to be flipped on day i, or -1 if it's impossible to turn all the lights off.

Example

Input


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


Output


2
2
3
-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Prof. Peter decided to surprise his class by organizing a new lottery with a very peculiar system.

He starts by announcing a small positive number $M$. Afterwards, each student is going to secretly write an integer from the set $\{ 1, ..., M\} $ on a slip of paper that is then folded. After everyone has selected a number, they reveal all choices and whoever wrote down the lowest unique number is the winner! For instance, if there are only three students in the class, two of them select number $2$ and the other selects number $5$, then the student who chose number $5$ is the winner.

The lottery was a success, but Prof. Peter is now wondering what strategy his students should have used. If everyone follows the same optimal randomized strategy, with which probability should each number be chosen so that they maximize their chances of winning? A strategy is optimal if, when everyone is following it, then no individual student can improve his winning probability by selecting a different strategy. Can you help Prof. Peter?

-----Task-----
Given $N$, the number of students in the class, and $M$, the largest number they can write down, determine the optimal randomized strategy (followed by all students). That is, determine the probability of selecting each number between $1$ and $M$.

-----Input-----
There is one line with two integers: $N$, which is the number of students in the class, and $M$, which is the largest integer each student can choose.

-----Constraints-----

$3$

$\leq $

$N$

$\leq $

$7$

Number of students in the class

$1$

$\leq $

$M$

$\leq $

$N+1$

Maximum number that can be selected

-----Output-----
The output consists of $M$ lines. Line $k$ should have the probability of selecting number $k$.

The result will be considered correct as long as the absolute error does not exceed $10^{-3}$.

-----Examples-----
Sample Input 1:
3 3
Sample Output 1:
0.46410
0.26795
0.26795

Sample Input 2:
7 1
Sample Output 2:
1.00000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Recently Johnny have learned bogosort sorting algorithm. He thought that it is too ineffective. So he decided to improve it. As you may know this algorithm shuffles the sequence randomly until it is sorted. Johnny decided that we don't need to shuffle the whole sequence every time. If after the last shuffle several first elements end up in the right places we will fix them and don't shuffle those elements furthermore. We will do the same for the last elements if they are in the right places. For example, if the initial sequence is (3, 5, 1, 6, 4, 2) and after one shuffle Johnny gets (1, 2, 5, 4, 3, 6) he will fix 1, 2 and 6 and proceed with sorting (5, 4, 3) using the same algorithm. Johnny hopes that this optimization will significantly improve the algorithm. Help him calculate the expected amount of shuffles for the improved algorithm to sort the sequence of the first n natural numbers given that no elements are in the right places initially.

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

The first line of input file is number t - the number of test cases. Each of the following t lines hold single number n - the number of elements in the sequence.

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

1 ≤ t ≤ 150

2 ≤ n ≤ 150

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

For each test case output the expected amount of shuffles needed for the improved algorithm to sort the sequence of first n natural numbers in the form of irreducible fractions.

----- Sample Input 1 ------ 
3
2
6
10
----- Sample Output 1 ------ 
2
1826/189
877318/35343

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a sequence A of length N, the weight of this sequence is defined as

\text{weight}(A) = \sum_{i = 1}^{N} i\cdot A_{i}

Given an integer N, we pick a permutation A of [1, 2 \dots N] uniformly at random. What is the expected weight of this permutation?

It can be shown that the answer can be represented as \displaystyle \frac{P}{Q} where P and Q are coprime integers and Q \neq 0 \pmod{998244353}. Print the value of P \cdot Q^{-1} modulo 998244353.

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

- First line of the input contains T, the number of test cases. Then the test cases follow.
- Each test case contains a single integer on a single line N.

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

For each test case, print a single integer, the answer to the test case.

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

$1 ≤ T ≤ 2 \cdot 10^{5}$
$1 ≤ N ≤ 10^{9}$

------ subtasks ------ 

Subtask 1 (100 points): Original constraints

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

----- Sample Output 1 ------ 
1
499122181
12

----- explanation 1 ------ 
- Test case $1$: There is only one permutation of $[1]$ which is $[1]$ and the weight of this permutation is equal to $1$. So, the expected weight is equal to $1$.
- Test case $2$: There are $2$ permutations of $[1, 2]$ namely
- $[1, 2]$ with weight equal to $5$.
- $[2, 1]$ with weight equal to $4$.

So, the expected weight is equal to $\frac{5 + 4}{2!} = \frac{9}{2}$.
- Test case $3:$
There are $6$ permutations of $[1, 2, 3]$ namely
- $[1, 2, 3]$ with weight equal to $14$.
- $[1, 3, 2]$ with weight equal to $13$.
- $[2, 1, 3]$ with weight equal to $13$.
- $[2, 3, 1]$ with weight equal to $11$.
- $[3, 1, 2]$ with weight equal to $11$.
- $[3, 2, 1]$ with weight equal to $10$.

So, the expected weight is equal to $\frac{14 + 13 + 13 + 11 + 11 + 10}{3!} = 12$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string, return the minimal number of parenthesis reversals needed to make balanced parenthesis. 

For example:
```Javascript
solve(")(") = 2 Because we need to reverse ")" to "(" and "(" to ")". These are 2 reversals. 
solve("(((())") = 1 We need to reverse just one "(" parenthesis to make it balanced.
solve("(((") = -1 Not possible to form balanced parenthesis. Return -1.
```

Parenthesis will be either `"("` or `")"`. 

More examples in the test cases. 

Good luck.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Gildong is playing a video game called Block Adventure. In Block Adventure, there are $n$ columns of blocks in a row, and the columns are numbered from $1$ to $n$. All blocks have equal heights. The height of the $i$-th column is represented as $h_i$, which is the number of blocks stacked in the $i$-th column.

Gildong plays the game as a character that can stand only on the top of the columns. At the beginning, the character is standing on the top of the $1$-st column. The goal of the game is to move the character to the top of the $n$-th column.

The character also has a bag that can hold infinitely many blocks. When the character is on the top of the $i$-th column, Gildong can take one of the following three actions as many times as he wants:   if there is at least one block on the column, remove one block from the top of the $i$-th column and put it in the bag;  if there is at least one block in the bag, take one block out of the bag and place it on the top of the $i$-th column;  if $i < n$ and $|h_i - h_{i+1}| \le k$, move the character to the top of the $i+1$-st column. $k$ is a non-negative integer given at the beginning of the game. Note that it is only possible to move to the next column. 

In actions of the first two types the character remains in the $i$-th column, and the value $h_i$ changes.

The character initially has $m$ blocks in the bag. Gildong wants to know if it is possible to win the game. Help Gildong find the answer to his question.


-----Input-----

Each test contains one or more test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). Description of the test cases follows.

The first line of each test case contains three integers $n$, $m$, and $k$ ($1 \le n \le 100$, $0 \le m \le 10^6$, $0 \le k \le 10^6$) — the number of columns in the game, the number of blocks in the character's bag at the beginning, and the non-negative integer $k$ described in the statement.

The second line of each test case contains $n$ integers. The $i$-th integer is $h_i$ ($0 \le h_i \le 10^6$), the initial height of the $i$-th column.


-----Output-----

For each test case, print "YES" if it is possible to win the game. Otherwise, print "NO".

You can print each letter in any case (upper or lower).


-----Example-----
Input
5
3 0 1
4 3 5
3 1 2
1 4 7
4 10 0
10 20 10 20
2 5 5
0 11
1 9 9
99

Output
YES
NO
YES
NO
YES



-----Note-----

In the first case, Gildong can take one block from the $1$-st column, move to the $2$-nd column, put the block on the $2$-nd column, then move to the $3$-rd column.

In the second case, Gildong has to put the block in his bag on the $1$-st column to get to the $2$-nd column. But it is impossible to get to the $3$-rd column because $|h_2 - h_3| = 3 > k$ and there is no way to decrease the gap.

In the fifth case, the character is already on the $n$-th column from the start so the game is won instantly.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A function receives a certain numbers of integers ```n1, n2, n3 ..., np```(all positive and different from 0) and a factor ```k, k > 0```

The function rearranges the numbers ```n1, n2, ..., np``` in such order that generates the minimum number concatenating the digits and this number should be divisible by ```k```.

The order that the function receives their arguments is:
```python
rearranger(k, n1, n2, n3,....,np)
```

## Examples

```python
rearranger(4, 32, 3, 34, 7, 12)  == "Rearrangement: 12, 3, 34, 7, 32 generates: 12334732 divisible by 4"

rearranger(10, 32, 3, 34, 7, 12) == "There is no possible rearrangement"
```
If there are more than one possible arrengement for the same minimum number, your code should be able to handle those cases:
```python
rearranger(6, 19, 32, 2, 124, 20, 22) == "Rearrangements: 124, 19, 20, 2, 22, 32 and 124, 19, 20, 22, 2, 32 generates: 124192022232 divisible by 6"
```

The arrangements should be in sorted order, as you see: `124, 19, 20, 2, 22, 32` comes first than `124, 19, 20, 22, 2, 32`.

Have an enjoyable time!

(Thanks to `ChristianE.Cooper` for his contribution to this kata)

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