vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Cycling City

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are organizing a cycling race on the streets of the city. The city contains *n* junctions, some pairs of them are connected by roads; on each road you can move in any direction. No two roads connect the same pair of intersections, and no road connects the intersection with itself.

You want the race to be open to both professional athletes and beginner cyclists, and that's why you will organize the race in three nominations: easy, moderate and difficult; each participant will choose the more suitable nomination. For each nomination you must choose the route — the chain of junctions, consecutively connected by roads. Routes must meet the following conditions:
-  all three routes should start at the same intersection, and finish at the same intersection (place of start and finish can't be the same);-  to avoid collisions, no two routes can have common junctions (except for the common start and finish), and can not go along the same road (irrespective of the driving direction on the road for those two routes);-  no route must pass twice through the same intersection or visit the same road twice (irrespective of the driving direction on the road for the first and second time of visit).
Preparing for the competition is about to begin, and you need to determine the routes of the race as quickly as possible. The length of the routes is not important, it is only important that all the given requirements were met.

Input Specification:
The first line contains two integers *n* and *m* (1<=≤<=*n*,<=*m*<=≤<=2·105) — the number of intersections and roads, respectively.

The following *m* lines contain two integers — the numbers of the intersections connected by a road (the intersections are numbered starting with 1). It is guaranteed that each pair of intersections is connected by no more than one road, and no road connects the intersection to itself.

Please note that it is not guaranteed that you can get from any junction to any other one by using the roads.

Output Specification:
If it is possible to create the routes, in the first line print "YES". In the next three lines print the descriptions of each of the three routes in the format "*l* *p*1 ... *p**l*", where *l* is the number of intersections in the route, and *p*1,<=...,<=*p**l* are their numbers in the order they follow. The routes must meet all the requirements specified in the statement.

If it is impossible to make the routes in accordance with the requirements, print NO.

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

Demo Output:
['NO\n', 'YES\n3 5 4 1\n3 5 3 1\n3 5 2 1\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef solved so many hard questions, now he wants to solve some easy problems for refreshment. Chef asks Cheffina for the new question. Cheffina challanges the chef to print the total number of 1's in the binary representation of N(natural number).

-----Input:-----
- First-line will contain $T$, the number of test cases. Then the test cases follow. 
- Each test case contains a single line of input, $N$. 

-----Output:-----
For each test case, output in a single line answer.

-----Constraints-----
- $1 \leq T \leq 10^6$
- $1 \leq N \leq 10^6$

-----Sample Input:-----
2
2
5

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

-----EXPLANATION:-----
For 1) Binary representation of 2 is 10. i.e. only one 1 present in it.
For 2) Binary representation of 5 is 101, i.e. two 1's present in it.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a permutation P of length N.

You can perform the following operation on P:
Select two distinct indices i and j (1≤ i, j ≤ N) and swap the elements P_{i} and P_{j}.
The cost of the operation is abs(i-j).

The total cost is defined as the sum of costs of all operations performed.
Find the minimum total cost to sort the permutation in increasing order and the order of operations required to do so.

Note:
A permutation consists of all elements from 1 to N exactly once.
You do not need to minimise the number of operations required to sort the array. The number of operations can lie in the range [0, N^{2}].

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains an integer N — the length of the permutation.
- The next line contains N space-separated integers, the elements of permutation P.

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

For each test case:
- In the first line, output minimum total cost to sort the permutation in increasing order.
- In the next line, output an integer K (0≤ K ≤ N^{2}), denoting the number of operations required to sort the permutation.
- The next K lines contain two space-separated integers i and j, denoting the operation.

If there are multiple ways to sort the permutation using minimum total cost, print any.

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

$1 ≤ T ≤ 100$
$2 ≤ N ≤ 500$
$P$ is a permutation of length $N$.
- The sum of $N$ over all test cases won't exceed $500$.

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

----- Sample Output 1 ------ 
1
1
2 3
0
0
2
2
1 2
3 4

----- explanation 1 ------ 
Test case $1$: The minimum total cost to sort the permutation is $1$. We can sort the permutation using $1$ operation:
- Operation $1$: Choose $i = 2$ and $j = 3$ and swap $P_{2}$ and $P_{3}$. The cost of this operation is $abs(2-3) = 1$. The updated permutation is $[1, 2, 3]$, which is sorted.

Test case $2$: The permutation is already sorted. Thus, we require $0$ cost and $0$ operations to sort the permutation.

Test case $3$: The minimum total cost to sort the permutation is $2$. We can sort the permutation using $2$ operation:
- Operation $1$: Choose $i = 1$ and $j = 2$ and swap $P_{1}$ and $P_{1}$. The cost of this operation is $abs(1-2) = 1$. The updated permutation is $[1, 2, 4, 3]$.
- Operation $2$: Choose $i = 3$ and $j = 4$ and swap $P_{3}$ and $P_{4}$. The cost of this operation is $abs(3-4) = 1$. The updated permutation is $[1, 2, 3, 4]$, which is sorted.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Minimum number of steps

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
We have a string of letters 'a' and 'b'. We want to perform some operations on it. On each step we choose one of substrings "ab" in the string and replace it with the string "bba". If we have no "ab" as a substring, our job is done. Print the minimum number of steps we should perform to make our job done modulo 109<=+<=7.

The string "ab" appears as a substring if there is a letter 'b' right after the letter 'a' somewhere in the string.

Input Specification:
The first line contains the initial string consisting of letters 'a' and 'b' only with length from 1 to 106.

Output Specification:
Print the minimum number of steps modulo 109<=+<=7.

Demo Input:
['ab\n', 'aab\n']

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

Note:
The first example: "ab"  →  "bba".

The second example: "aab"  →  "abba"  →  "bbaba"  →  "bbbbaa".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Tieu owns a pizza restaurant and he manages it in his own way.  While in a normal restaurant, a customer is served by following the first-come, first-served rule, Tieu simply minimizes the average waiting time of his customers. So he gets to decide who is served first, regardless of how sooner or later a person comes. 

Different kinds of pizzas take different amounts of time to cook. Also, once he starts cooking a pizza, he cannot cook another pizza until the first pizza is completely cooked. Let's say we have three customers who come at time t=0, t=1, & t=2 respectively, and the time needed to cook their pizzas is 3, 9, & 6 respectively. If Tieu applies first-come, first-served rule, then the waiting time of three customers is 3, 11, & 16  respectively. The average waiting time in this case is (3 + 11 + 16) / 3 = 10. This is not an optimized solution. After serving the first customer at time t=3, Tieu can choose to serve the third customer. In that case, the waiting time will be 3, 7, & 17 respectively. Hence the average waiting time is (3 + 7 + 17) / 3 = 9.

Help Tieu achieve the minimum average waiting time. For the sake of simplicity, just find the integer part of the minimum average waiting time.

Input Format

The first line contains an integer N, which is the number of customers. 

In the next N lines, the i^{th} line contains two space separated numbers T_{i} and L_{i}. T_{i} is the time when i^{th} customer order a pizza, and L_{i} is the time required to cook that pizza.  

The $i^{\mbox{th}}$ customer is not the customer arriving at the $i^{\mbox{th}}$ arrival time. 

Output Format

Display the integer part of the minimum average waiting time.

Constraints

1 ≤ N ≤ $10^{5}$
0 ≤ T_{i} ≤ $10^{9}$
1 ≤ L_{i} ≤$10^{9}$

Note

The waiting time is calculated as the difference between the time a customer orders pizza (the time at which they enter the shop) and the time she is served.

Cook does not know about the future orders.

Sample Input #00

3
0 3
1 9
2 6

Sample Output #00

9

Sample Input #01

3
0 3
1 9
2 5

Sample Output #01

8

Explanation #01

Let's call the person ordering at time = 0 as A, time = 1 as B and time = 2 as C. By delivering pizza for A, C and B we get the minimum average wait time to be 

(3 + 6 + 16)/3 = 25/3 = 8.33 

the integer part is 8 and hence the answer.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Easy and hard versions are actually different problems, so read statements of both problems completely and carefully.

Summer vacation has started so Alice and Bob want to play and joy, but... Their mom doesn't think so. She says that they have to read some amount of books before all entertainments. Alice and Bob will read each book together to end this exercise faster.

There are n books in the family library. The i-th book is described by three integers: t_i — the amount of time Alice and Bob need to spend to read it, a_i (equals 1 if Alice likes the i-th book and 0 if not), and b_i (equals 1 if Bob likes the i-th book and 0 if not).

So they need to choose some books from the given n books in such a way that:

  * Alice likes at least k books from the chosen set and Bob likes at least k books from the chosen set; 
  * the total reading time of these books is minimized (they are children and want to play and joy as soon a possible). 



The set they choose is the same for both Alice an Bob (it's shared between them) and they read all books together, so the total reading time is the sum of t_i over all books that are in the chosen set.

Your task is to help them and find any suitable set of books or determine that it is impossible to find such a set.

Input

The first line of the input contains two integers n and k (1 ≤ k ≤ n ≤ 2 ⋅ 10^5).

The next n lines contain descriptions of books, one description per line: the i-th line contains three integers t_i, a_i and b_i (1 ≤ t_i ≤ 10^4, 0 ≤ a_i, b_i ≤ 1), where:

  * t_i — the amount of time required for reading the i-th book; 
  * a_i equals 1 if Alice likes the i-th book and 0 otherwise; 
  * b_i equals 1 if Bob likes the i-th book and 0 otherwise. 

Output

If there is no solution, print only one integer -1. Otherwise print one integer T — the minimum total reading time of the suitable set of books.

Examples

Input

8 4
7 1 1
2 1 1
4 0 1
8 1 1
1 0 1
1 1 1
1 0 1
3 0 0


Output

18


Input

5 2
6 0 0
9 0 0
1 0 1
2 1 1
5 1 0


Output

8


Input

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


Output

-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Rainfall is measured in millimeters. The rain is collected in a vertical transparent tube with millimeter markings, and once the rain has stopped falling, one can check the height of the water in the tube.

In our problem, the tube unfortunately has a leak at height $L$ millimeters (mm). If the water level is above the leak then water drains from the tube at a rate of $K$ millimeters per hour (mm/h).

We want to figure out how much rain fell during a particular rainfall. We assume that the tube is high enough that it does not overflow. We also assume that rain falls at an (unknown) uniform rate during a rainfall, and that water does not evaporate from the tube. The height of the leak itself is also negligible.

-----Input-----
The input is a line with five positive numbers: $L$ $K$ $T_1$ $T_2$ $H$ where$L$

is where the leak is (mm)$K$

is the rate at which water leaks (mm/h)$T_1$

is the duration of the rainfall (h)$T_2$

is the time between the end of the rainfall and the observation of the water level (h)$H$

is the water level in the tube when we observe it (mm)

Each number is at least $0.01$ and at most $1000.00$, and each is given with exactly two decimals.

-----Output-----
One line with two floating point numbers $F_1$ $F_2$ where $F_1$ is the smallest rainfall in millimeters that would result in the given observation, and $F_2$ is the largest rainfall in millimeters that would result in the given observation. Values with either absolute or relative error smaller than $10^{-6}$ are acceptable.

-----Examples-----
Sample Input:
80.00 0.50 2.00 1.50 80.00
Sample Output:
80.000000 80.759403

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A long time ago in a galaxy far, far away$\ldots $ there was a cinematic universe with countless sequels, prequels, and everything in-between. You have always been confused of the ordering of the Star Wars movies. First they created the plot order movies $4$, $5$ and $6$. Then movie $1$, $2$ and $3$. Now they are creating side plot movies that fit in between old movies. 

We actually have two orderings of Star Wars movies: creation order and plot order. You’d like to be able to translate between these orderings. Both orderings start at $1$. If a movie is created and inserted at plot index $i$ the plot index of every movie with a plot index $j$ where $i \leq j$ is increased by $1$.

-----Input-----
The first line of the input contains a single number $Q$, where $1 < Q \leq 600000$.

Then follows $Q$ lines with a query on each.

A query has the following form $q x$, where $q$ is either $1$ or $2$, and $x$ is a positive integer. If $q$ is $1$ it means that we created a movie that currently is number $x$ in plot order. For $q=2$ we would like to know what the creation index is of the movie that currently has the plot index $x$.

If the number of movies so far is denoted with $n$, it is guaranteed that if $q=1$, $1 \leq x \leq n+1$ and if $q=2$, $1 \leq x \leq n$.

-----Output-----
For each query with $q=2$ output a line with a single number, the creation index of the movie with plot index $x$.

-----Sample Explanation-----
Sample Input $1$ corresponds to the $6$ original Star Wars movies. First three movies were created in order, then three more were created that has plot indices prior to the three created first. Then we inspect the creation order of all the movies in plot order. The $1$st, $2$nd and $3$rd movies in plot order are the $4$th, $5$th and $6$th movies created. The $4$th, $5$th and $6$th movies in plot order are the $1$st, $2$nd and $3$rd movies created.

-----Examples-----
Sample Input 1:
12
1 1
1 2
1 3
1 1
1 2
1 3
2 1
2 2
2 3
2 4
2 5
2 6
Sample Output 1:
4
5
6
1
2
3

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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Since due to COVID 19, India has undergone a complete 21 day lockdown. So Amol was attending an online lecture where his professor asked him to solve a question. Amol was unable to solve the question so he asked you to solve the question and give him the correct answer. 

The question was asked a such that his professor gave him a number M and a list of integers of length N (i.e. A1, A2,..... AN) and you have to find out all the subsets that add up to M and the total number of subsets will be the final answer. 

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 line of each test case contains a single integer N. 

• The second line of each test case contains a single integer M. 

• The third line contains N space-separated integers A1, A2,..... AN. 

Output: 
For each test case, print a single line containing one integer ― the no. of subsets that adds upto M.

Constraints: 
• 1≤T≤5

• 1≤N≤100 

• 10≤M≤100 

• 1≤Ai≤100

ExampleInput:

2

4

16

2 4 6 10 

4 

20 

2 8 12 10 

Output:

2

2

Explanation:
In the 1st example there are two subsets {2,4,10} and {6,10} that adds upto 16 so the output is 2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Takahashi is practicing shiritori alone again today.
Shiritori is a game as follows:
 - In the first turn, a player announces any one word.
 - In the subsequent turns, a player announces a word that satisfies the following conditions:
 - That word is not announced before.
 - The first character of that word is the same as the last character of the last word announced.
In this game, he is practicing to announce as many words as possible in ten seconds.
You are given the number of words Takahashi announced, N, and the i-th word he announced, W_i, for each i. Determine if the rules of shiritori was observed, that is, every word announced by him satisfied the conditions.

-----Constraints-----
 - N is an integer satisfying 2 \leq N \leq 100.
 - W_i is a string of length between 1 and 10 (inclusive) consisting of lowercase English letters.

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

-----Output-----
If every word announced by Takahashi satisfied the conditions, print Yes; otherwise, print No.

-----Sample Input-----
4
hoge
english
hoge
enigma

-----Sample Output-----
No

As hoge is announced multiple times, the rules of shiritori was not observed.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have a sequence of N integers: A_1, A_2, \cdots, A_N.
You can perform the following operation between 0 and K times (inclusive):
 - Choose two integers i and j such that i \neq j, each between 1 and N (inclusive). Add 1 to A_i and -1 to A_j, possibly producing a negative element.
Compute the maximum possible positive integer that divides every element of A after the operations. Here a positive integer x divides an integer y if and only if there exists an integer z such that y = xz.

-----Constraints-----
 - 2 \leq N \leq 500
 - 1 \leq A_i \leq 10^6
 - 0 \leq K \leq 10^9
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N K
A_1 A_2 \cdots A_{N-1} A_{N}

-----Output-----
Print the maximum possible positive integer that divides every element of A after the operations.

-----Sample Input-----
2 3
8 20

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

7 will divide every element of A if, for example, we perform the following operation:
 - Choose i = 2, j = 1. A becomes (7, 21).
We cannot reach the situation where 8 or greater integer divides every element of A.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array of positive integers arr, calculate the sum of all possible odd-length subarrays.
A subarray is a contiguous subsequence of the array.
Return the sum of all odd-length subarrays of arr.
 
Example 1:
Input: arr = [1,4,2,5,3]
Output: 58
Explanation: The odd-length subarrays of arr and their sums are:
[1] = 1
[4] = 4
[2] = 2
[5] = 5
[3] = 3
[1,4,2] = 7
[4,2,5] = 11
[2,5,3] = 10
[1,4,2,5,3] = 15
If we add all these together we get 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58
Example 2:
Input: arr = [1,2]
Output: 3
Explanation: There are only 2 subarrays of odd length, [1] and [2]. Their sum is 3.
Example 3:
Input: arr = [10,11,12]
Output: 66

 
Constraints:

1 <= arr.length <= 100
1 <= arr[i] <= 1000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a computer network consisting of n nodes numbered 1 through n. There are links in the network that connect pairs of nodes. A pair of nodes may have multiple links between them, but no node has a link to itself.

Each link supports unlimited bandwidth (in either direction), however a link may only transmit in a single direction at any given time. The cost of sending data across a link is proportional to the square of the bandwidth. Specifically, each link has a positive weight, and the cost of sending data across the link is the weight times the square of the bandwidth.

The network is connected (there is a series of links from any node to any other node), and furthermore designed to remain connected in the event of any single node failure.

You needed to send data from node 1 to node n at a bandwidth of some positive number k. That is, you wish to assign a bandwidth to each link so that the bandwidth into a node minus the bandwidth out of a node is  - k for node 1, k for node n, and 0 for all other nodes. The individual bandwidths do not need to be integers.

Wishing to minimize the total cost, you drew a diagram of the network, then gave the task to an intern to solve. The intern claimed to have solved the task and written the optimal bandwidths on your diagram, but then spilled coffee on it, rendering much of it unreadable (including parts of the original diagram, and the value of k).

From the information available, determine if the intern's solution may have been optimal. That is, determine if there exists a valid network, total bandwidth, and optimal solution which is a superset of the given information. Furthermore, determine the efficiency of the intern's solution (if possible), where efficiency is defined as total cost divided by total bandwidth.

Input

Input will begin with two integers n and m (2 ≤ n ≤ 200000; 0 ≤ m ≤ 200000), the number of nodes and number of known links in the network, respectively. Following this are m lines with four integers each: f, t, w, b (1 ≤ f ≤ n; 1 ≤ t ≤ n; f ≠ t; 1 ≤ w ≤ 100; 0 ≤ b ≤ 100). This indicates there is a link between nodes f and t with weight w and carrying b bandwidth. The direction of bandwidth is from f to t.

Output

If the intern's solution is definitely not optimal, print "BAD x", where x is the first link in the input that violates the optimality of the solution. If the intern's solution may be optimal, print the efficiency of the solution if it can be determined rounded to the nearest integer, otherwise print "UNKNOWN".

Examples

Input

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


Output

6


Input

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


Output

BAD 3


Input

6 4
1 3 31 41
1 5 59 26
2 6 53 58
4 6 97 93


Output

UNKNOWN


Input

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


Output

BAD 4

Note

Although the known weights and bandwidths happen to always be integers, the weights and bandwidths of the remaining links are not restricted to integers.

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