vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Booking System

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Innovation technologies are on a victorious march around the planet. They integrate into all spheres of human activity!

A restaurant called "Dijkstra's Place" has started thinking about optimizing the booking system. 

There are *n* booking requests received by now. Each request is characterized by two numbers: *c**i* and *p**i* — the size of the group of visitors who will come via this request and the total sum of money they will spend in the restaurant, correspondingly.

We know that for each request, all *c**i* people want to sit at the same table and are going to spend the whole evening in the restaurant, from the opening moment at 18:00 to the closing moment.

Unfortunately, there only are *k* tables in the restaurant. For each table, we know *r**i* — the maximum number of people who can sit at it. A table can have only people from the same group sitting at it. If you cannot find a large enough table for the whole group, then all visitors leave and naturally, pay nothing.

Your task is: given the tables and the requests, decide which requests to accept and which requests to decline so that the money paid by the happy and full visitors was maximum.

Input Specification:
The first line of the input contains integer *n* (1<=≤<=*n*<=≤<=1000) — the number of requests from visitors. Then *n* lines follow. Each line contains two integers: *c**i*,<=*p**i* (1<=≤<=*c**i*,<=*p**i*<=≤<=1000) — the size of the group of visitors who will come by the *i*-th request and the total sum of money they will pay when they visit the restaurant, correspondingly.

The next line contains integer *k* (1<=≤<=*k*<=≤<=1000) — the number of tables in the restaurant. The last line contains *k* space-separated integers: *r*1,<=*r*2,<=...,<=*r**k* (1<=≤<=*r**i*<=≤<=1000) — the maximum number of people that can sit at each table.

Output Specification:
In the first line print two integers: *m*,<=*s* — the number of accepted requests and the total money you get from these requests, correspondingly.

Then print *m* lines — each line must contain two space-separated integers: the number of the accepted request and the number of the table to seat people who come via this request. The requests and the tables are consecutively numbered starting from 1 in the order in which they are given in the input.

If there are multiple optimal answers, print any of them.

Demo Input:
['3\n10 50\n2 100\n5 30\n3\n4 6 9\n']

Demo Output:
['2 130\n2 1\n3 2\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two integers $n$ and $k$. You are asked to choose maximum number of distinct integers from $1$ to $n$ so that there is no subset of chosen numbers with sum equal to $k$.

A subset of a set is a set that can be obtained from initial one by removing some (possibly all or none) elements of it.


-----Input-----

The first line contains the number of test cases $T$ ($1 \le T \le 100$).

Each of the next $T$ lines contains two integers $n$ and $k$ ($1 \le k \le n \le 1000$) — the description of test cases.


-----Output-----

For each test case output two lines. In the first line output a single integer $m$ — the number of chosen integers.

In the second line output $m$ distinct integers from $1$ to $n$ — the chosen numbers.

If there are multiple answers, print any. You can print the numbers in any order.


-----Examples-----

Input
3
3 2
5 3
1 1
Output
2
3 1 
3
4 5 2 
0


-----Note-----

None

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an undirected tree1 with each of its node assigned a magic $X_ i$. The magic of a path2 is defined as the product of the magic of the nodes on that path divided by the number of the nodes on the path. For example, the magic of a path that consists of nodes with magic $3$ and $5$ is $7.5$ ($3\cdot 5 / 2$). In the given tree, find the path with the minimal magic and output the magic of that path.

-----Input-----
The first line of input contains the integer $N$ ($1 \leq N \leq 10^6$), the number of nodes in the tree. Each of the following $N - 1$ lines contains two integers, $A_ i$ and $B_ i$ ($1 \leq A_ i, B_ i \leq N$), the labels of nodes connected with an edge. The $i$-th of the following $N$ lines contains the integer $X_ i$ ($1 \leq X_ i \leq 10^9$), magic of the $i$-th node.

-----Output-----
Output the magic of the path with minimal magic in the form of a completely reduced fraction $P/Q$ ($P$ and $Q$ are relatively prime integers).

In all test cases, it will hold that the required $P$ and $Q$ are smaller than $10^{18}$.

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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Now it's time for actual battle between Ram and Ravana.  Battle field is given in the form of an array of integers.  But Ram has no idea about the field, so he asked Angad to help him out.  Now, Angad has decided a strategy to divide the field into exactly two parts such that the difference between the powers for the two parts is as minimum as possible. The  Power of a part is defined as the sum of the elements in that part.

Input:

First line contains T, denoting the number of test cases.

Each test case contains 2 lines:

First line contains an integer N denoting the size of  the array

Second line consists of N space separated integers.

Output:

Output the required answer in new line. 

Constraints:

0 <  T ≤ 20

1 < N ≤ 100000

-10^8 ≤ A[i] ≤ 10^8

Note:

Both parts has to be contiguous.

Large input/output files,  use scanf() , printf() for fast I/OSAMPLE INPUT
2
2 
1 2 
3
1 2 3

SAMPLE OUTPUT
1
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Prof. Vasechkin wants to represent positive integer n as a sum of addends, where each addends is an integer number containing only 1s. For example, he can represent 121 as 121=111+11+–1. Help him to find the least number of digits 1 in such sum.


-----Input-----

The first line of the input contains integer n (1 ≤ n < 10^15).


-----Output-----

Print expected minimal number of digits 1.


-----Examples-----
Input
121

Output
6

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string s of length n, consisting of first k lowercase English letters.

We define a c-repeat of some string q as a string, consisting of c copies of the string q. For example, string "acbacbacbacb" is a 4-repeat of the string "acb".

Let's say that string a contains string b as a subsequence, if string b can be obtained from a by erasing some symbols.

Let p be a string that represents some permutation of the first k lowercase English letters. We define function d(p) as the smallest integer such that a d(p)-repeat of the string p contains string s as a subsequence.

There are m operations of one of two types that can be applied to string s:

  1. Replace all characters at positions from li to ri by a character ci. 
  2. For the given p, that is a permutation of first k lowercase English letters, find the value of function d(p). 



All operations are performed sequentially, in the order they appear in the input. Your task is to determine the values of function d(p) for all operations of the second type.

Input

The first line contains three positive integers n, m and k (1 ≤ n ≤ 200 000, 1 ≤ m ≤ 20000, 1 ≤ k ≤ 10) — the length of the string s, the number of operations and the size of the alphabet respectively. The second line contains the string s itself.

Each of the following lines m contains a description of some operation: 

  1. Operation of the first type starts with 1 followed by a triple li, ri and ci, that denotes replacement of all characters at positions from li to ri by character ci (1 ≤ li ≤ ri ≤ n, ci is one of the first k lowercase English letters). 
  2. Operation of the second type starts with 2 followed by a permutation of the first k lowercase English letters.

Output

For each query of the second type the value of function d(p).

Examples

Input

7 4 3
abacaba
1 3 5 b
2 abc
1 4 4 c
2 cba


Output

6
5

Note

After the first operation the string s will be abbbbba.

In the second operation the answer is 6-repeat of abc: ABcaBcaBcaBcaBcAbc.

After the third operation the string s will be abbcbba.

In the fourth operation the answer is 5-repeat of cba: cbAcBacBaCBacBA.

Uppercase letters means the occurrences of symbols from the string s.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a Directed Acyclic Graph (DAG) with $n$ vertices and $m$ edges. Each vertex $v$ has an integer, $a_v$, associated with it and the initial value of $a_v$ is $0$ for all vertices. You must perform $\textit{q}$ queries on the DAG, where each query is one of the following types:

1 u x: Set $a_v$ to $\boldsymbol{x}$ for all $v$ such that there is a path in the DAG from $\mbox{u}$ to $v$.
2 u x: Set $a_v$ to $\boldsymbol{x}$ for all $v$ such that there is a path from $\mbox{u}$ to $v$ and $a_v>x$.
3 u: Print the value of $a_{u}$ on a new line.

Input Format

The first line contains three space-separated integers describing the respective values of $n$ (the number of vertices in the DAG), $m$ (the number of edges in the DAG), and $\textit{q}$ (the number of queries to perform). 

Each of the $m$ subsequent lines contains two space-separated integers describing the respective values of $\mbox{u}$ and $v$ (where $1\leq u,v\leq n$, $u\neq v$) denoting a directed edge from vertex $\mbox{u}$ to vertex $v$ in the graph. 

Each of the $\textit{q}$ subsequent lines contains a query in one of the three formats described above.

Constraints

$2\leq n\leq10^5$
$1\leq m,q\leq10^5$
$0\leq x\leq10^9$
$0\leq a_v\leq10^9$
It's guaranteed that the graph is acyclic, but there may be more than one edge connecting two nodes.

Output Format

For each query of type $3$ (i.e., 3 u), print the value of $a_{u}$ on a new line.

Sample Input 0
6 5 18
1 2
1 3
3 4
2 4
5 6
1 1 3
3 1
3 2
3 3
3 4
1 2 2
3 1
3 2
3 3
3 4
2 6 7
3 5
3 6
2 1 3
3 1
3 2
3 3
3 4

Sample Output 0
3
3
3
3
3
2
3
2
0
0
3
2
3
2

Explanation 0

The diagram below depicts the changes to the graph after all type $1$ and type $2$ queries:

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A well-known art union called "Kalevich is Alive!" manufactures objects d'art (pictures). The union consists of n painters who decided to organize their work as follows.

Each painter uses only the color that was assigned to him. The colors are distinct for all painters. Let's assume that the first painter uses color 1, the second one uses color 2, and so on. Each picture will contain all these n colors. Adding the j-th color to the i-th picture takes the j-th painter t_{ij} units of time.

Order is important everywhere, so the painters' work is ordered by the following rules:  Each picture is first painted by the first painter, then by the second one, and so on. That is, after the j-th painter finishes working on the picture, it must go to the (j + 1)-th painter (if j < n);  each painter works on the pictures in some order: first, he paints the first picture, then he paints the second picture and so on;  each painter can simultaneously work on at most one picture. However, the painters don't need any time to have a rest;  as soon as the j-th painter finishes his part of working on the picture, the picture immediately becomes available to the next painter. 

Given that the painters start working at time 0, find for each picture the time when it is ready for sale.


-----Input-----

The first line of the input contains integers m, n (1 ≤ m ≤ 50000, 1 ≤ n ≤ 5), where m is the number of pictures and n is the number of painters. Then follow the descriptions of the pictures, one per line. Each line contains n integers t_{i}1, t_{i}2, ..., t_{in} (1 ≤ t_{ij} ≤ 1000), where t_{ij} is the time the j-th painter needs to work on the i-th picture.


-----Output-----

Print the sequence of m integers r_1, r_2, ..., r_{m}, where r_{i} is the moment when the n-th painter stopped working on the i-th picture.


-----Examples-----
Input
5 1
1
2
3
4
5

Output
1 3 6 10 15 
Input
4 2
2 5
3 1
5 3
10 1

Output
7 8 13 21

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

Problem Statement

Mr. T has had an integer sequence of N elements a_1, a_2, ... , a_N and an integer K. Mr. T has created N integer sequences B_1, B_2, ... , B_N such that B_i has i elements.

* B_{N,j} = a_j (1 \leq j \leq N)
* B_{i,j} = K \times B_{i+1,j} + B_{i+1,j+1} (1\leq i \leq N-1, 1 \leq j \leq i)



Mr. T was so careless that he lost almost all elements of these sequences a and B_i. Fortunately, B_{1,1}, B_{2,1}, ... , B_{N,1} and K are not lost. Your task is to write a program that restores the elements of the initial sequence a for him. Output the modulo 65537 of each element instead because the absolute value of these elements can be extremely large. More specifically, for all integers i (1 \leq i \leq N), output r_i that satisfies r_i  $\equiv$ a_i $ \bmod \;$ 65537, 0 \leq r_i < 65537. Here, we can prove that the original sequence Mr. T had can be uniquely determined under the given constraints.

Input


T
N_1 K_1
C_{1,1} C_{1,2} ... C_{1,N}
N_2 K_2
C_{2,1} C_{2,2} ... C_{2,N}
:
N_T K_T
C_{T,1} C_{T,2} ... C_{T,N}


The first line contains a single integer T that denotes the number of test cases. Each test case consists of 2 lines. The first line of the i-th test case contains two integers N_i and K_i. The second line of the i-th test case contains N_i integers C_{i,j} (1 \leq j \leq N_i). These values denote that N = N_i , K = K_i , B_{j,1} = C_{i,j} (1 \leq j \leq N_i) in the i-th test case.

Constraints

* 1 \leq T \leq 10
* 1 \leq N \leq 50000
* |K| \leq 10^9
* |B_{i,1}| \leq 10^9
* All input values are integers.



Output

Output T lines. For the i-th line, output the answer for the i-th test case a_1, a_2, ..., a_N in this order. Each number must be separated by a single space.

Sample Input 1


2
3 0
1 2 3
3 1
1 2 3


Output for Sample Input 1


3 2 1
3 65536 0






Example

Input

2
3 0
1 2 3
3 1
1 2 3


Output

3 2 1
3 65536 0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef has two strings A and B consisting of lowercase alphabets, each of length N. Help Chef in finding the number of indices i (1 ≤ i ≤ N) such that A[i \dots N] < B[i \dots N].

S[i \dots N] denotes the suffix of string S starting at index i, i.e. S_{iS}_{i+1} \dots S_{N}. 
String S < String T denotes that S is lexicographically smaller than T. If two strings S and T have the same length N, we say that S is lexicographically smaller than T if there exists an index i(1 ≤ i ≤ N) such that S_{1} = T_{1}, S_{2} = T_{2}, \ldots, S_{i-1} = T_{i-1} and S_{i} < T_{i}. For example, "abc" is lexicographically smaller than "acd", "abe", but not smaller than "abc", "aac".

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

- The first line contains T denoting the number of test cases. Then the test cases follow.
- The first line of each test case contains N, denoting the length of the strings A and B.
- The second line of each test case contains the string A.
- The third line of each test case contains the string B.

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

For each test case, print a single line containing one integer -  the number of indices i such that A[i \dots N] < B[i\dots N].

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{6}$
- The sum of $N$ over all test cases does not exceed $10^{6}$

----- Sample Input 1 ------ 
2
2
ab
bb
3
aaa
aab
----- Sample Output 1 ------ 
1
3

----- explanation 1 ------ 
Test Case $1$: 
- For $i = 1$, $A[1 \dots 2] = $ "$ab$", $B[1 \dots 2] = $ "$bb$" and lexicographically, "$ab$" $<$ "$bb$".
- For $i = 2$, $A[2 \dots 2] =$ "$b$", $B[2 \dots 2] = $ "$b$" and lexicographically, "$b$" $=$ "$b$".

Test Case $2$: For each $i \in \{1 , 2, 3\}$, $A[i \dots 3] < B[i \dots 3]$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Autobots are instructed by Optimus Prime to mobilize in the form of a rectangular shape with each Autobot on each vertex of the rectangle region on a -”deployment area” (which may consist of one or more regions). This is done so as to take care of the inner rectangular area called “region”. However the rule states-“no two regions may overlap”.  You have been asked to remove some regions from the “deployment area” so the remaining regions do not obscure each other. To keep the disturbance to the minimum level, you should remove the minimum number of regions to achieve this goal. You may not remove a region and place it in another position; all regions you leave in “deployment area” must be in their original position.
When you examined the “deployment area”, you noticed something very nice. Every region was placed on the deployment area by placing each autobot in the four corners. This was done in a very courteous manner since each autobot is guarding only the region it is holding. 
The reason Optimus Prime wants your help because you are good at taking down a single region without disturbing the rest, even if that region is obscured by many others.


-----Input-----
The first line consists of a single integer T indicating the number of test cases (about 25).
Each test case consists begins with a single integer n indicating the number of regions. The next n lines consist of 4 integers x0, x1, y0, and y1 satisfying x0 < x1 and y0 < y1. This means the region covers all points (x,y) satisfying x0 <= x <= x1 and y0 <= y <= y1.
As stated before hand, no corner of any region will intersect any other region anywhere. That is, if (x,y) is a corner point of one region and another region is described by x0, x1, y0, and y1, then we do not have x0 <= x <= x1 and y0 <= y <= y1.
Bounds: 1 <= n <= 100 and each integer in a region description fits in a signed 32 bit integer.

-----Output-----
The output for each test case is a single line containing a single integer that is the maximum number of regions that can be left on the wall such that no two regions share a common point in the deployment area.

-----Example-----
Input:
1
4
0 4 0 4
1 3 1 2
2 3 1 3
3 4 1 3
Output:
2

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

Write a helper function that takes in a Time object and converts it to a more human-readable format. You need only go up to '_ weeks ago'.
```python
to_pretty(0) => "just now"

to_pretty(40000) => "11 hours ago"
```
##Specifics
 - The output will be an amount of time, t, included in one of the following phrases: "just now", "[t] seconds ago", "[t] minutes ago", "[t] hours ago", "[t] days ago", "[t] weeks ago".
 - You will have to handle the singular cases. That is, when t = 1, the phrasing will be one of "a second ago", "a minute ago", "an hour ago", "a day ago", "a week ago".
 - The amount of time is always rounded down to the nearest integer. For example, if the amount of time is actually 11.73 hours ago, the return value will be "11 hours ago".
 - Only times in the past will be given, with the range "just now" to "52 weeks ago"

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Watching Fireworks is Fun

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
A festival will be held in a town's main street. There are *n* sections in the main street. The sections are numbered 1 through *n* from left to right. The distance between each adjacent sections is 1.

In the festival *m* fireworks will be launched. The *i*-th (1<=≤<=*i*<=≤<=*m*) launching is on time *t**i* at section *a**i*. If you are at section *x* (1<=≤<=*x*<=≤<=*n*) at the time of *i*-th launching, you'll gain happiness value *b**i*<=-<=|*a**i*<=-<=*x*| (note that the happiness value might be a negative value).

You can move up to *d* length units in a unit time interval, but it's prohibited to go out of the main street. Also you can be in an arbitrary section at initial time moment (time equals to 1), and want to maximize the sum of happiness that can be gained from watching fireworks. Find the maximum total happiness.

Note that two or more fireworks can be launched at the same time.

Input Specification:
The first line contains three integers *n*, *m*, *d* (1<=≤<=*n*<=≤<=150000; 1<=≤<=*m*<=≤<=300; 1<=≤<=*d*<=≤<=*n*).

Each of the next *m* lines contains integers *a**i*, *b**i*, *t**i* (1<=≤<=*a**i*<=≤<=*n*; 1<=≤<=*b**i*<=≤<=109; 1<=≤<=*t**i*<=≤<=109). The *i*-th line contains description of the *i*-th launching.

It is guaranteed that the condition *t**i*<=≤<=*t**i*<=+<=1 (1<=≤<=*i*<=&lt;<=*m*) will be satisfied.

Output Specification:
Print a single integer — the maximum sum of happiness that you can gain from watching all the fireworks.

Please, do not write the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specifier.

Demo Input:
['50 3 1\n49 1 1\n26 1 4\n6 1 10\n', '10 2 1\n1 1000 4\n9 1000 4\n']

Demo Output:
['-31\n', '1992\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Pens And Days Of Week

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Stepan has *n* pens. Every day he uses them, and on the *i*-th day he uses the pen number *i*. On the (*n*<=+<=1)-th day again he uses the pen number 1, on the (*n*<=+<=2)-th — he uses the pen number 2 and so on.

On every working day (from Monday to Saturday, inclusive) Stepan spends exactly 1 milliliter of ink of the pen he uses that day. On Sunday Stepan has a day of rest, he does not stend the ink of the pen he uses that day. 

Stepan knows the current volume of ink in each of his pens. Now it's the Monday morning and Stepan is going to use the pen number 1 today. Your task is to determine which pen will run out of ink before all the rest (that is, there will be no ink left in it), if Stepan will use the pens according to the conditions described above.

Input Specification:
The first line contains the integer *n* (1<=≤<=*n*<=≤<=50<=000) — the number of pens Stepan has.

The second line contains the sequence of integers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=109), where *a**i* is equal to the number of milliliters of ink which the pen number *i* currently has.

Output Specification:
Print the index of the pen which will run out of ink before all (it means that there will be no ink left in it), if Stepan will use pens according to the conditions described above. 

Pens are numbered in the order they are given in input data. The numeration begins from one. 

Note that the answer is always unambiguous, since several pens can not end at the same time.

Demo Input:
['3\n3 3 3\n', '5\n5 4 5 4 4\n']

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

Note:
In the first test Stepan uses ink of pens as follows: 
 1.  on the day number 1 (Monday) Stepan will use the pen number 1, after that there will be 2 milliliters of ink in it; 1.  on the day number 2 (Tuesday) Stepan will use the pen number 2, after that there will be 2 milliliters of ink in it; 1.  on the day number 3 (Wednesday) Stepan will use the pen number 3, after that there will be 2 milliliters of ink in it; 1.  on the day number 4 (Thursday) Stepan will use the pen number 1, after that there will be 1 milliliters of ink in it; 1.  on the day number 5 (Friday) Stepan will use the pen number 2, after that there will be 1 milliliters of ink in it; 1.  on the day number 6 (Saturday) Stepan will use the pen number 3, after that there will be 1 milliliters of ink in it; 1.  on the day number 7 (Sunday) Stepan will use the pen number 1, but it is a day of rest so he will not waste ink of this pen in it; 1.  on the day number 8 (Monday) Stepan will use the pen number 2, after that this pen will run out of ink. 
So, the first pen which will not have ink is the pen number 2.

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