vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Given a directed weighted graph and two vertices $s$, $t$, the goal is to find a subset $U$ of the vertices such that $s \in U$, $t \not\in U$, and the weight of edges from $U$ to $\overline{U}$ is minimized.

-----Input-----
The first line of input contains four non-negative integers, $2 \le n \le 500$, $0 \le m \le 10000$, $0 \le s \le n-1$ and $0 \le t \le n-1$, separated by single spaces, where $n$ is the numbers of nodes in the graph, $m$ is the number of edges, $s$ is the source and $t$ is the sink ($s \ne t$). Nodes are numbered from $0$ to $n-1$. Then follow $m$ lines, each line consisting of three (space-separated) integers $u$, $v$ and $w$ indicating that there is an edge from $u$ to $v$ in the graph with weight $1 \le w \le 10^8$.

-----Output-----
Output should begin with a line containing an integer $k$, giving the size of $U$. Then follow $k$ lines giving the vertices in $U$, one per line. If there are multiple choices for $U$ any one will be accepted.

You may assume that there is a cut such that the total weight of edges from $U$ to $\overline{U}$ is less than $2^{31}$.

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

Sample Input 2:
2 1 0 1
0 1 100000
Sample Output 2:
1
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Red John has committed another murder. This time, he doesn't leave a red smiley behind. Instead he leaves a puzzle for Patrick Jane to solve. He also texts Teresa Lisbon that if Patrick is successful, he will turn himself in. The puzzle begins as follows.  

There is a wall of size 4xn in the victim's house. The victim has an infinite supply of bricks of size 4x1 and 1x4 in her house. There is a hidden safe which can only be opened by a particular configuration of bricks. First we must calculate the total number of ways in which the bricks can be arranged so that the entire wall is covered.  The following diagram shows how bricks might be arranged to cover walls where $1\leq n\leq4$:

There is one more step to the puzzle.  Call the number of possible arrangements $\mbox{M}$.   Patrick must calculate the number of prime numbers $\mbox{P}$ in the inclusive range $\textbf{0}-M$.  

As an example, assume $n=3$.  From the diagram above, we determine that there is only one configuration that will cover the wall properly.  $\mbox{I}$ is not a prime number, so $P=0$.

A more complex example is $n=5$.  The bricks can be oriented in $3$ total configurations that cover the wall.  The two primes $2$ and $3$ are less than or equal to $3$, so $P=2$.

Function Description  

Complete the redJohn function in the editor below.  It should return the number of primes determined, as an integer.  

redJohn has the following parameter(s):  

n: an integer that denotes the length of the wall  

Input Format

The first line contains the integer $\boldsymbol{\boldsymbol{t}}$, the number of test cases. 

Each of the next $\boldsymbol{\boldsymbol{t}}$ lines contains an integer $n$, the length of the $4\times n$ wall.

Constraints

$1\leq t\leq20$
$1\leq n\leq40$

Output Format

Print the integer $\mbox{P}$ on a separate line for each test case.

Sample Input
2
1
7

Sample Output
0
3

Explanation

For $n=1$, the brick can be laid in 1 format only: vertically. 

The number of primes $\leq1$ is $\mbox{o}$. 

For $unrecognized$, one of the ways in which we can lay the bricks is 

There are $5$ ways of arranging the bricks for $n=7$ and there are $3$ primes $\leq5$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Enemy is weak

Time Limit: 5 seconds

Memory Limit: 256 megabytes

Problem Description:
The Romans have attacked again. This time they are much more than the Persians but Shapur is ready to defeat them. He says: "A lion is never afraid of a hundred sheep". 

Nevertheless Shapur has to find weaknesses in the Roman army to defeat them. So he gives the army a weakness number.

In Shapur's opinion the weakness of an army is equal to the number of triplets *i*,<=*j*,<=*k* such that *i*<=&lt;<=*j*<=&lt;<=*k* and *a**i*<=&gt;<=*a**j*<=&gt;<=*a**k* where *a**x* is the power of man standing at position *x*. The Roman army has one special trait — powers of all the people in it are distinct.

Help Shapur find out how weak the Romans are.

Input Specification:
The first line of input contains a single number *n* (3<=≤<=*n*<=≤<=106) — the number of men in Roman army. Next line contains *n* different positive integers *a**i* (1<=≤<=*i*<=≤<=*n*,<=1<=≤<=*a**i*<=≤<=109) — powers of men in the Roman army.

Output Specification:
A single integer number, the weakness of the Roman army. 

Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preffered to use cout (also you may use %I64d).

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

Demo Output:
['1\n', '0\n', '4\n', '1\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
>When no more interesting kata can be resolved, I just choose to create the new kata, to solve their own, to enjoy the process  --myjinxin2015 said

# Description:
 Give you two number `m` and `n`(two positive integer, m < n), make a triangle pattern with number sequence `m to n`. The order is clockwise, starting from the top corner, like this:
 
```
 When m=1 n=10  triangle is:
    1
   9 2
  8 0 3
 7 6 5 4
```
 Note: The pattern only uses the last digit of each number; Each row separated by "\n"; Each digit separated by a space; Left side may need pad some spaces, but don't pad the right side; If `m to n` can not make the triangle, return `""`.
  
# Some examples:

```
makeTriangle(1,3) should return:
 1
3 2

makeTriangle(6,20) should return: 

    6
   7 7
  6 8 8
 5 0 9 9
4 3 2 1 0

makeTriangle(1,12) should return ""
 
```

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You're given *Q* queries of the form (*L*,<=*R*). 

For each query you have to find the number of such *x* that *L*<=≤<=*x*<=≤<=*R* and there exist integer numbers *a*<=&gt;<=0, *p*<=&gt;<=1 such that *x*<==<=*a**p*.

Input Specification:
The first line contains the number of queries *Q* (1<=≤<=*Q*<=≤<=105).

The next *Q* lines contains two integers *L*, *R* each (1<=≤<=*L*<=≤<=*R*<=≤<=1018).

Output Specification:
Output *Q* lines — the answers to the queries.

Demo Input:
['6\n1 4\n9 9\n5 7\n12 29\n137 591\n1 1000000\n']

Demo Output:
['2\n1\n0\n3\n17\n1111\n']

Note:
In query one the suitable numbers are 1 and 4.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Yi has moved to Sweden and now goes to school here. The first years of schooling she got in China, and the curricula do not match completely in the two countries. Yi likes mathematics, but now... The teacher explains the algorithm for subtraction on the board, and Yi is bored. Maybe it is possible to perform the same calculations on the numbers corresponding to the reversed binary representations of the numbers on the board? Yi dreams away and starts constructing a program that reverses the binary representation, in her mind. As soon as the lecture ends, she will go home and write it on her computer.

-----Task-----
Your task will be to write a program for reversing numbers in binary. For instance, the binary representation of 13 is 1101, and reversing it gives 1011, which corresponds to number 11.

-----Input-----
The input contains a single line with an integer $N$, $1 \leq N \leq 1\; 000\; 000\; 000$.

-----Output-----
Output one line with one integer, the number we get by reversing the binary representation of $N$.

-----Examples-----
Sample Input:
13
Sample Output:
11

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
As you know, every birthday party has a cake! This time, Babaei is going to prepare the very special birthday party's cake.

Simple cake is a cylinder of some radius and height. The volume of the simple cake is equal to the volume of corresponding cylinder. Babaei has n simple cakes and he is going to make a special cake placing some cylinders on each other.

However, there are some additional culinary restrictions. The cakes are numbered in such a way that the cake number i can be placed only on the table or on some cake number j where j < i. Moreover, in order to impress friends Babaei will put the cake i on top of the cake j only if the volume of the cake i is strictly greater than the volume of the cake j.

Babaei wants to prepare a birthday cake that has a maximum possible total volume. Help him find this value.


-----Input-----

The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of simple cakes Babaei has.

Each of the following n lines contains two integers r_{i} and h_{i} (1 ≤ r_{i}, h_{i} ≤ 10 000), giving the radius and height of the i-th cake.


-----Output-----

Print the maximum volume of the cake that Babaei can make. Your answer will be considered correct if its absolute or relative error does not exceed 10^{ - 6}.

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if $\frac{|a - b|}{\operatorname{max}(1, b)} \leq 10^{-6}$.


-----Examples-----
Input
2
100 30
40 10

Output
942477.796077000

Input
4
1 1
9 7
1 4
10 7

Output
3983.539484752



-----Note-----

In first sample, the optimal way is to choose the cake number 1.

In second sample, the way to get the maximum volume is to use cakes with indices 1, 2 and 4.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Autumn came late to the kingdom of Far Far Away. The harvest was exuberant and it is now time to get ready for the winter. As most people celebrate the Harvest festival, Simon the Caretaker tries to solve a very non-trivial task of how to find place for the agricultural equipment in the warehouse.

He's got problems with some particularly large piece of equipment, which is, of course, turboplows. The problem is that when a turboplow is stored, it takes up not some simply rectangular space. It takes up a T-shaped space like on one of the four pictures below (here character "#" stands for the space occupied by the turboplow and character "." stands for the free space):
    
    
    ###      ..#      .#.      #..  
    .#.      ###      .#.      ###  
    .#.      ..#      ###      #..  
    

Simon faced a quite natural challenge: placing in the given n × m cells warehouse the maximum number of turboplows. As one stores the turboplows, he can rotate them in any manner (so that they take up the space like on one of the four pictures above). However, two turboplows cannot "overlap", that is, they cannot share the same cell in the warehouse.

Simon feels that he alone cannot find the optimal way of positioning the plugs in the warehouse that would maximize their quantity. Can you help him?

Input

The only line contains two space-separated integers n and m — the sizes of the warehouse (1 ≤ n, m ≤ 9).

Output

In the first line print the maximum number of turboplows that can be positioned in the warehouse. In each of the next n lines print m characters. Use "." (dot) to mark empty space and use successive capital Latin letters ("A" for the first turboplow, "B" for the second one and so on until you reach the number of turboplows in your scheme) to mark place for the corresponding turboplows considering that they are positioned in the optimal manner in the warehouse. The order in which you number places for the turboplows does not matter. If there are several optimal solutions for a warehouse of the given size, print any of them.

Examples

Input

3 3


Output

1
AAA
.A.
.A.


Input

5 6


Output

4
A..C..
AAAC..
ABCCCD
.B.DDD
BBB..D


Input

2 2


Output

0
..
..

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a picture consisting of $n$ rows and $m$ columns. Rows are numbered from $1$ to $n$ from the top to the bottom, columns are numbered from $1$ to $m$ from the left to the right. Each cell is painted either black or white. 

You think that this picture is not interesting enough. You consider a picture to be interesting if there is at least one cross in it. A cross is represented by a pair of numbers $x$ and $y$, where $1 \le x \le n$ and $1 \le y \le m$, such that all cells in row $x$ and all cells in column $y$ are painted black.

For examples, each of these pictures contain crosses:

 [Image] 

The fourth picture contains 4 crosses: at $(1, 3)$, $(1, 5)$, $(3, 3)$ and $(3, 5)$.

Following images don't contain crosses:

 [Image] 

You have a brush and a can of black paint, so you can make this picture interesting. Each minute you may choose a white cell and paint it black.

What is the minimum number of minutes you have to spend so the resulting picture contains at least one cross?

You are also asked to answer multiple independent queries.


-----Input-----

The first line contains an integer $q$ ($1 \le q \le 5 \cdot 10^4$) — the number of queries.

The first line of each query contains two integers $n$ and $m$ ($1 \le n, m \le 5 \cdot 10^4$, $n \cdot m \le 4 \cdot 10^5$) — the number of rows and the number of columns in the picture.

Each of the next $n$ lines contains $m$ characters — '.' if the cell is painted white and '*' if the cell is painted black.

It is guaranteed that $\sum n \le 5 \cdot 10^4$ and $\sum n \cdot m \le 4 \cdot 10^5$.


-----Output-----

Print $q$ lines, the $i$-th line should contain a single integer — the answer to the $i$-th query, which is the minimum number of minutes you have to spend so the resulting picture contains at least one cross.


-----Example-----
Input
9
5 5
..*..
..*..
*****
..*..
..*..
3 4
****
.*..
.*..
4 3
***
*..
*..
*..
5 5
*****
*.*.*
*****
..*.*
..***
1 4
****
5 5
.....
..*..
.***.
..*..
.....
5 3
...
.*.
.*.
***
.*.
3 3
.*.
*.*
.*.
4 4
*.**
....
*.**
*.**

Output
0
0
0
0
0
4
1
1
2



-----Note-----

The example contains all the pictures from above in the same order.

The first 5 pictures already contain a cross, thus you don't have to paint anything.

You can paint $(1, 3)$, $(3, 1)$, $(5, 3)$ and $(3, 5)$ on the $6$-th picture to get a cross in $(3, 3)$. That'll take you $4$ minutes.

You can paint $(1, 2)$ on the $7$-th picture to get a cross in $(4, 2)$.

You can paint $(2, 2)$ on the $8$-th picture to get a cross in $(2, 2)$. You can, for example, paint $(1, 3)$, $(3, 1)$ and $(3, 3)$ to get a cross in $(3, 3)$ but that will take you $3$ minutes instead of $1$.

There are 9 possible crosses you can get in minimum time on the $9$-th picture. One of them is in $(1, 1)$: paint $(1, 2)$ and $(2, 1)$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given string s that is appended with a number at last. The task is to check whether the length of string excluding that number is equal to that number. 
Example 1:
Input:  s = "geeks5"
Output: 1
Explanation: Length of geeks is 5
and the last number is also 5.
Example 2:
Input:  s = "geek5"
Output: 0
Explanation: Length of geek is 4
and the last number is 5.
User Task:
Your task is to complete the function isSame() which takes a single string as input and returns 1 in case the answer is true, otherwise 0. You do not need to take any input or print anything.
Expected Time Complexity: O(|s|)
Expected Auxiliary Space: O(1)
Constraints:
1 <= |s| <= 10^{5}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya has got an array consisting of $n$ integers, and two integers $k$ and $len$ in addition. All numbers in the array are either between $1$ and $k$ (inclusive), or equal to $-1$. The array is good if there is no segment of $len$ consecutive equal numbers.

Vasya will replace each $-1$ with some number from $1$ to $k$ (inclusive) in such a way that the resulting array is good. Tell him the number of ways to do this replacement. Since the answer may be large, print it modulo $998244353$.


-----Input-----

The first line contains three integers $n, k$ and $len$ ($1 \le n \le 10^5, 1 \le k \le 100, 1 \le len \le n$).

The second line contains $n$ numbers — the array. Each number is either $-1$ or between $1$ and $k$ (inclusive).


-----Output-----

Print one integer — the number of ways to replace each $-1$ with some number from $1$ to $k$ (inclusive) so the array is good. The answer may be large, so print it modulo $998244353$.


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

Output
2

Input
6 3 2
1 1 -1 -1 -1 -1

Output
0

Input
10 42 7
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1

Output
645711643



-----Note-----

Possible answers in the first test:   $[1, 2, 1, 1, 2]$;  $[1, 2, 1, 2, 2]$. 

There is no way to make the array good in the second test, since first two elements are equal.

There are too many answers in the third test, so we won't describe any of them.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef discovered that his secret recipe has been stolen. He immediately informs the police of the theft.

It is known that the policeman and thief move on the number line. You are given that:
The initial location of the policeman on the number line is X and his speed is 2 units per second.
The initial location of the thief on the number line is Y and his speed is 1 unit per second.

Find the minimum time (in seconds) in which the policeman can catch the thief. Note that, the policeman catches the thief as soon as their locations become equal and the thief will try to evade the policeman for as long as possible.

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

- The first line of input will contain an integer T — the number of test cases. The description of T test cases follows.
- The first and only line of each test case contains two integers X and Y, as described in the problem statement. 

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

For each test case, output in a single line the minimum time taken by the policeman to catch the thief. 

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

$1 ≤ T ≤ 1000$
$-10^{5} ≤ X, Y ≤ 10^{5}$

----- Sample Input 1 ------ 
3
1 3
2 1
1 1
----- Sample Output 1 ------ 
2
1
0
----- explanation 1 ------ 
Test case $1$: The initial locations of the policeman and thief are $1$ and $3$ respectively. The minimum time taken by the policeman to catch the thief is $2$ seconds, and this happens when both the policeman and the thief move towards the right.  

Test case $2$: The initial location of the policeman and thief are $2$ and $1$ respectively. The minimum time taken by the policeman to catch the thief is $1$ second, and this happens when both the policeman and the thief move towards the left.  

Test case $3$: The initial locations of the policeman and thief are $1$ and $1$ respectively. Because the police is already present at the location of thief, the time taken by police to catch the thief is $0$ seconds.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Big Maximum Sum

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
Ahmed and Mostafa used to compete together in many programming contests for several years. Their coach Fegla asked them to solve one challenging problem, of course Ahmed was able to solve it but Mostafa couldn't.

This problem is similar to a standard problem but it has a different format and constraints.

In the standard problem you are given an array of integers, and you have to find one or more consecutive elements in this array where their sum is the maximum possible sum.

But in this problem you are given *n* small arrays, and you will create one big array from the concatenation of one or more instances of the small arrays (each small array could occur more than once). The big array will be given as an array of indexes (1-based) of the small arrays, and the concatenation should be done in the same order as in this array. Then you should apply the standard problem mentioned above on the resulting big array.

For example let's suppose that the small arrays are {1, 6, -2}, {3, 3} and {-5, 1}. And the indexes in the big array are {2, 3, 1, 3}. So the actual values in the big array after formatting it as concatenation of the small arrays will be {3, 3, -5, 1, 1, 6, -2, -5, 1}. In this example the maximum sum is 9.

Can you help Mostafa solve this problem?

Input Specification:
The first line contains two integers *n* and *m*, *n* is the number of the small arrays (1<=≤<=*n*<=≤<=50), and *m* is the number of indexes in the big array (1<=≤<=*m*<=≤<=250000). Then follow *n* lines, the *i*-th line starts with one integer *l* which is the size of the *i*-th array (1<=≤<=*l*<=≤<=5000), followed by *l* integers each one will be greater than or equal -1000 and less than or equal 1000. The last line contains *m* integers which are the indexes in the big array, and you should concatenate the small arrays in the same order, and each index will be greater than or equal to 1 and less than or equal to *n*.

The small arrays are numbered from 1 to *n* in the same order as given in the input. Some of the given small arrays may not be used in big array.

Note, that the array is very big. So if you try to build it straightforwardly, you will probably get time or/and memory limit exceeded.

Output Specification:
Print one line containing the maximum sum in the big array after formatting it as described above. You must choose at least one element for the sum, i. e. it cannot be empty.

Please, do not use %lld specificator to write 64-bit integers in C++. It is preferred to use cout (also you may use %I64d).

Demo Input:
['3 4\n3 1 6 -2\n2 3 3\n2 -5 1\n2 3 1 3\n', '6 1\n4 0 8 -3 -10\n8 3 -2 -5 10 8 -9 -5 -4\n1 0\n1 -3\n3 -8 5 6\n2 9 6\n1\n']

Demo Output:
['9\n', '8\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: On Sum of Fractions

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Let's assume that 
 -  *v*(*n*) is the largest prime number, that does not exceed *n*;-  *u*(*n*) is the smallest prime number strictly greater than *n*. 
Find .

Input Specification:
The first line contains integer *t* (1<=≤<=*t*<=≤<=500) — the number of testscases. 

Each of the following *t* lines of the input contains integer *n* (2<=≤<=*n*<=≤<=109).

Output Specification:
Print *t* lines: the *i*-th of them must contain the answer to the *i*-th test as an irreducible fraction "*p*/*q*", where *p*,<=*q* are integers, *q*<=&gt;<=0.

Demo Input:
['2\n2\n3\n']

Demo Output:
['1/6\n7/30\n']

Note:
none

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