yl-9/probench huggingface dataset:
# Sheriff's Defense

## Problem Description

"Why, master," quoth Little John, taking the bags and weighing them in his hand, "here is the chink of gold."



The folk hero Robin Hood has been troubling Sheriff of Nottingham greatly. Sheriff knows that Robin Hood is about to attack his camps and he wants to be prepared.

Sheriff of Nottingham built the camps with strategy in mind and thus there are exactly $ n $ camps numbered from $ 1 $ to $ n $ and $ n-1 $ trails, each connecting two camps. Any camp can be reached from any other camp. Each camp $ i $ has initially $ a_i $ gold.

As it is now, all camps would be destroyed by Robin. Sheriff can strengthen a camp by subtracting exactly $ c $ gold from each of its neighboring camps and use it to build better defenses for that camp. Strengthening a camp doesn't change its gold, only its neighbors' gold. A camp can have negative gold.

After Robin Hood's attack, all camps that have been strengthened survive the attack, all others are destroyed.

What's the maximum gold Sheriff can keep in his surviving camps after Robin Hood's attack if he strengthens his camps optimally?

Camp $ a $ is neighboring camp $ b $ if and only if there exists a trail connecting $ a $ and $ b $ . Only strengthened camps count towards the answer, as others are destroyed.

## Input Format

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases.

Each test case begins with two integers $ n $ , $ c $ ( $ 1 \le n \le 2\cdot10^5, 1 \le c \le 10^9 $ ) — the number of camps and the gold taken from each neighboring camp for strengthening.

The second line of each test case contains $ n $ integers $ a_1,a_2,\dots,a_n $ ( $ -10^9 \le a_i \le 10^9 $ ) — the initial gold of each camp.

Then follow $ n-1 $ lines, each with integers $ u $ , $ v $ ( $ 1 \le u, v \le n $ , $ u \ne v $ ) — meaning that there is a trail between $ u $ and $ v $ .

The sum of $ n $ over all test cases doesn't exceed $ 2\cdot10^5 $ .

It is guaranteed that any camp is reachable from any other camp.

## Output Format

Output a single integer, the maximum gold Sheriff of Nottingham can keep in his surviving camps after Robin Hood's attack.

## Sample #1

### Sample Input #1

```
5
3 1
2 3 1
1 2
2 3
3 1
3 6 3
1 2
2 3
3 1
-2 -3 -1
1 2
2 3
6 1
5 -4 3 6 7 3
4 1
5 1
3 5
3 6
1 2
8 1
3 5 2 7 8 5 -3 -4
7 3
1 8
4 3
3 5
7 6
8 7
2 1
```

### Sample Output #1

```
3
8
0
17
26
```

## Hint

In the first test case, it is optimal to strengthen the second base. The final gold at each base is $ [1,3,0] $ .

In the second test case, it is optimal to strengthen all bases. The final gold at each base is $ [2,4,2] $ .

In the third test case, it is optimal to not strengthen any base.

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: dfs and similar, dp, greedy, trees
Difficulty: 2000
# Robert Hood and Mrs Hood

## Problem Description

Impress thy brother, yet fret not thy mother.



Robin's brother and mother are visiting, and Robin gets to choose the start day for each visitor.

All days are numbered from $ 1 $ to $ n $ . Visitors stay for $ d $ continuous days, all of those $ d $ days must be between day $ 1 $ and $ n $ inclusive.

Robin has a total of $ k $ risky 'jobs' planned. The $ i $ -th job takes place between days $ l_i $ and $ r_i $ inclusive, for $ 1 \le i \le k $ . If a job takes place on any of the $ d $ days, the visit overlaps with this job (the length of overlap is unimportant).

Robin wants his brother's visit to overlap with the maximum number of distinct jobs, and his mother's the minimum.

Find suitable start days for the visits of Robin's brother and mother. If there are multiple suitable days, choose the earliest one.

## Input Format

The first line of the input contains a single integer $ t $ ( $ 1\leq t \leq 10^4 $ ) — the number of test cases.

The first line of each test case consists of three integers $ n $ , $ d $ , $ k $ ( $ 1 \le n \le 10^5, 1 \le d, k \le n $ ) — the number of total days, duration of the visits, and the number of jobs.

Then follow $ k $ lines of each test case, each with two integers $ l_i $ and $ r_i $ ( $ 1 \le l_i \le r_i \le n $ ) — the start and end day of each job.

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

## Output Format

For each test case, output two integers, the best starting days of Robin's brother and mother respectively. Both visits must fit between day $ 1 $ and $ n $ inclusive.

## Sample #1

### Sample Input #1

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

### Sample Output #1

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

## Hint

In the first test case, the only job fills all $ 2 $ days, both should visit on day $ 1 $ .

In the second test case, day $ 2 $ overlaps with $ 2 $ jobs and day $ 1 $ overlaps with only $ 1 $ .

In the third test case, Robert visits for days $ [1,2] $ , Mrs. Hood visits for days $ [4,5] $ .

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: brute force, data structures, greedy, sortings
Difficulty: 1400
# Robin Hood in Town

## Problem Description

In Sherwood, we judge a man not by his wealth, but by his merit.



Look around, the rich are getting richer, and the poor are getting poorer. We need to take from the rich and give to the poor. We need Robin Hood!

There are $ n $ people living in the town. Just now, the wealth of the $ i $ -th person was $ a_i $ gold. But guess what? The richest person has found an extra pot of gold!

More formally, find an $ a_j=max(a_1, a_2, \dots, a_n) $ , change $ a_j $ to $ a_j+x $ , where $ x $ is a non-negative integer number of gold found in the pot. If there are multiple maxima, it can be any one of them.

A person is unhappy if their wealth is strictly less than half of the average wealth $ ^{\text{∗}} $ .

If strictly more than half of the total population $ n $ are unhappy, Robin Hood will appear by popular demand.

Determine the minimum value of $ x $ for Robin Hood to appear, or output $ -1 $ if it is impossible.

 $ ^{\text{∗}} $ The average wealth is defined as the total wealth divided by the total population $ n $ , that is, $ \frac{\sum a_i}{n} $ , the result is a real number.

## Input Format

The first line of input contains one integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases.

The first line of each test case contains an integer $ n $ ( $ 1 \le n \le 2\cdot10^5 $ ) — the total population.

The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 10^6 $ ) — the wealth of each person.

It is guaranteed that the sum of $ n $ across all test cases does not exceed $ 2 \cdot 10^5 $ .

## Output Format

For each test case, output one integer — the minimum number of gold that the richest person must find for Robin Hood to appear. If it is impossible, output $ -1 $ instead.

## Sample #1

### Sample Input #1

```
6
1
2
2
2 19
3
1 3 20
4
1 2 3 4
5
1 2 3 4 5
6
1 2 1 1 1 25
```

### Sample Output #1

```
-1
-1
0
15
16
0
```

## Hint

In the first test case, it is impossible for a single person to be unhappy.

In the second test case, there is always $ 1 $ happy person (the richest).

In the third test case, no additional gold are required, so the answer is $ 0 $ .

In the fourth test case, after adding $ 15 $ gold, the average wealth becomes $ \frac{25}{4} $ , and half of this average is $ \frac{25}{8} $ , resulting in $ 3 $ people being unhappy.

In the fifth test case, after adding $ 16 $ gold, the average wealth becomes $ \frac{31}{5} $ , resulting in $ 3 $ people being unhappy.

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: binary search, greedy, math
Difficulty: 1100
# Robin Hood and the Major Oak

## Problem Description

In Sherwood, the trees are our shelter, and we are all children of the forest.



The Major Oak in Sherwood is known for its majestic foliage, which provided shelter to Robin Hood and his band of merry men and women.

The Major Oak grows $ i^i $ new leaves in the $ i $ -th year. It starts with $ 1 $ leaf in year $ 1 $ .

Leaves last for $ k $ years on the tree. In other words, leaves grown in year $ i $ last between years $ i $ and $ i+k-1 $ inclusive.

Robin considers even numbers lucky. Help Robin determine whether the Major Oak will have an even number of leaves in year $ n $ .

## Input Format

The first line of the input contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases.

Each test case consists of two integers $ n $ , $ k $ ( $ 1 \le n \le 10^9 $ , $ 1 \le k \le n $ ) — the requested year and the number of years during which the leaves remain.

## Output Format

For each test case, output one line, "YES" if in year $ n $ the Major Oak will have an even number of leaves and "NO" otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

## Sample #1

### Sample Input #1

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

### Sample Output #1

```
NO
YES
NO
NO
YES
```

## Hint

In the first test case, there is only $ 1 $ leaf.

In the second test case, $ k=1 $ , so in the $ 2 $ -nd year there will be $ 2^2=4 $ leaves.

In the third test case, $ k=2 $ , so in the $ 2 $ -nd year there will be $ 1+2^2=5 $ leaves.

In the fourth test case, $ k=2 $ , so in the $ 3 $ -rd year there will be $ 2^2 + 3^3 = 4 + 27 = 31 $ leaves.

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: math
Difficulty: 800
# Robin Helps

## Problem Description

There is a little bit of the outlaw in everyone, and a little bit of the hero too.



The heroic outlaw Robin Hood is famous for taking from the rich and giving to the poor.

Robin encounters $ n $ people starting from the $ 1 $ -st and ending with the $ n $ -th. The $ i $ -th person has $ a_i $ gold. If $ a_i \ge k $ , Robin will take all $ a_i $ gold, and if $ a_i=0 $ , Robin will give $ 1 $ gold if he has any. Robin starts with $ 0 $ gold.

Find out how many people Robin gives gold to.

## Input Format

The first line of the input contains a single integer $ t $ ( $ 1\leq t \leq 10^4 $ ) — the number of test cases.

The first line of each test case contains two integers $ n $ , $ k $ ( $ 1 \le n \le 50, 1 \le k \le 100 $ ) — the number of people and the threshold at which Robin Hood takes the gold.

The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \le a_i \le 100 $ ) — the gold of each person.

## Output Format

For each test case, output a single integer, the number of people that will get gold from Robin Hood.

## Sample #1

### Sample Input #1

```
4
2 2
2 0
3 2
3 0 0
6 2
0 3 0 0 0 0
2 5
5 4
```

### Sample Output #1

```
1
2
3
0
```

## Hint

In the first test case, Robin takes $ 2 $ gold from the first person and gives a gold to the second person.

In the second test case, Robin takes $ 3 $ gold and gives $ 1 $ gold to each of the next $ 2 $ people.

In the third test case, Robin takes $ 3 $ gold and so only gives gold to $ 3 $ other people.

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: greedy, implementation
Difficulty: 800
# Game in Tree (Hard Version)

## Problem Description

This is the hard version of the problem. In this version, it is not guaranteed that $ u = v $ . You can make hacks only if both versions of the problem are solved.

Alice and Bob are playing a fun game on a tree. This game is played on a tree with $ n $ vertices, numbered from $ 1 $ to $ n $ . Recall that a tree with $ n $ vertices is an undirected connected graph with $ n - 1 $ edges.

Alice and Bob take turns, with Alice going first. Each player starts at some vertex.

On their turn, a player must move from the current vertex to a neighboring vertex that has not yet been visited by anyone. The first player who cannot make a move loses.

You are given two vertices $ u $ and $ v $ . Represent the simple path from vertex $ u $ to $ v $ as an array $ p_1, p_2, p_3, \ldots, p_m $ , where $ p_1 = u $ , $ p_m = v $ , and there is an edge between $ p_i $ and $ p_{i + 1} $ for all $ i $ ( $ 1 \le i < m $ ).

You need to determine the winner of the game if Alice starts at vertex $ 1 $ and Bob starts at vertex $ p_j $ for each $ j $ (where $ 1 \le j \le m $ ).

## Input Format

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows.

The first line of each test case contains a single integer $ n $ ( $ 2 \le n \le 2 \cdot 10^5 $ ) — the number of vertices in the tree.

Each of the following $ n - 1 $ lines contains two integers $ a $ and $ b $ ( $ 1 \le a, b \le n $ ), denoting an undirected edge between vertices $ a $ and $ b $ . It is guaranteed that these edges form a tree.

The last line of each test case contains two integers $ u $ and $ v $ ( $ 2 \le u, v \le n $ ).

It is guaranteed that the path from $ u $ to $ v $ does not pass through vertex $ 1 $ .

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

## Output Format

For each test case, output $ m $ lines.

In the $ i $ -th line, print the winner of the game if Alice starts at vertex $ 1 $ and Bob starts at vertex $ p_i $ . Print "Alice" (without quotes) if Alice wins, or "Bob" (without quotes) otherwise.

## Sample #1

### Sample Input #1

```
3
3
1 2
2 3
2 3
6
1 2
1 3
2 4
2 5
1 6
4 5
4
1 2
1 3
2 4
2 4
```

### Sample Output #1

```
Bob
Alice
Alice
Bob
Alice
Bob
Alice
```

## Hint

![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF2013F2/e1cf544a0db6c078ce895e1ac7918ee5810cf6b5.png) Tree from the first example.In the first test case, the path will be ( $ 2,3 $ ). If Bob starts at vertex $ 2 $ , Alice will not be able to move anywhere on her first turn and will lose.

However, if Bob starts at vertex $ 3 $ , Alice will move to vertex $ 2 $ , and Bob will have no remaining vertices to visit and will lose.

## Limit



Time Limit
4.00s

Memory Limit
250.00MB

Tags: binary search, data structures, trees
Difficulty: 3500
# Game in Tree (Easy Version)

## Problem Description

This is the easy version of the problem. In this version, $ \mathbf{u = v} $ . You can make hacks only if both versions of the problem are solved.

Alice and Bob are playing a fun game on a tree. This game is played on a tree with $ n $ vertices, numbered from $ 1 $ to $ n $ . Recall that a tree with $ n $ vertices is an undirected connected graph with $ n - 1 $ edges.

Alice and Bob take turns, with Alice going first. Each player starts at some vertex.

On their turn, a player must move from the current vertex to a neighboring vertex that has not yet been visited by anyone. The first player who cannot make a move loses.

You are given two vertices $ u $ and $ v $ . Represent the simple path from vertex $ u $ to $ v $ as an array $ p_1, p_2, p_3, \ldots, p_m $ , where $ p_1 = u $ , $ p_m = v $ , and there is an edge between $ p_i $ and $ p_{i + 1} $ for all $ i $ ( $ 1 \le i < m $ ).

You need to determine the winner of the game if Alice starts at vertex $ 1 $ and Bob starts at vertex $ p_j $ for each $ j $ (where $ 1 \le j \le m $ ).

## Input Format

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows.

The first line of each test case contains a single integer $ n $ ( $ 2 \le n \le 2 \cdot 10^5 $ ) — the number of vertices in the tree.

Each of the following $ n - 1 $ lines contains two integers $ a $ and $ b $ ( $ 1 \le a, b \le n $ ), denoting an undirected edge between vertices $ a $ and $ b $ . It is guaranteed that these edges form a tree.

The last line of each test case contains two integers $ u $ and $ v $ ( $ 2 \le u, v \le n $ , $ \mathbf{u = v} $ ).

It is guaranteed that the path from $ u $ to $ v $ does not pass through vertex $ 1 $ .

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

## Output Format

For each test case, output $ m $ lines.

In the $ i $ -th line, print the winner of the game if Alice starts at vertex $ 1 $ and Bob starts at vertex $ p_i $ . Print "Alice" (without quotes) if Alice wins, or "Bob" (without quotes) otherwise.

## Sample #1

### Sample Input #1

```
3
3
1 2
2 3
2 2
3
1 2
2 3
3 3
6
1 2
1 3
2 4
2 5
1 6
4 4
```

### Sample Output #1

```
Bob
Alice
Alice
```

## Hint

![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF2013F1/e1cf544a0db6c078ce895e1ac7918ee5810cf6b5.png) Tree from the first and second examples.In the first test case, the path will be ( $ 2,2 $ ). Bob starts at vertex $ 2 $ , Alice will not be able to move anywhere on her first turn and will lose.

In the second test case, the path will be ( $ 3,3 $ ). Bob starts at vertex $ 3 $ , Alice will move to vertex $ 2 $ , and Bob will have no remaining vertices to visit and will lose.

## Limit



Time Limit
4.00s

Memory Limit
250.00MB

Tags: binary search, brute force, data structures, dp, games, greedy, implementation, trees
Difficulty: 2700
# Prefix GCD

## Problem Description

Since Mansur is tired of making legends, there will be no legends for this task.

You are given an array of positive integer numbers $ a_1, a_2, \ldots, a_n $ . The elements of the array can be rearranged in any order. You need to find the smallest possible value of the expression $ $$$\gcd(a_1) + \gcd(a_1, a_2) + \ldots + \gcd(a_1, a_2, \ldots, a_n), $ $  where  $ \\gcd(a\_1, a\_2, \\ldots, a\_n) $  denotes the <a href="https://en.wikipedia.org/wiki/Greatest_common_divisor">greatest common divisor (GCD)</a> of  $ a\_1, a\_2, \\ldots, a\_n$$$.

## Input Format

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows.

The first line of each test case contains a single number $ n $ ( $ 1 \le n \le 10^5 $ ) — the size of the array.

The second line of each test case contains $ n $ numbers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 10^5 $ ) — the initial array.

The sum of $ n $ over all test cases does not exceed $ 10^5 $ .

The sum of $ \max(a_1, a_2, \ldots, a_n) $ over all test cases does not exceed $ 10^5 $ .

## Output Format

For each test case, output a single number on a separate line — the answer to the problem.

## Sample #1

### Sample Input #1

```
5
3
4 2 2
2
6 3
3
10 15 6
5
6 42 12 52 20
4
42 154 231 66
```

### Sample Output #1

```
6
6
9
14
51
```

## Hint

In the first test case, the elements can be rearranged as follows: $ [2, 4, 2] $ . Then the answer will be $ \gcd(2) + \gcd(2, 4) + \gcd(2, 4, 2) = 2 + 2 + 2 = 6 $ .

In the third test case, the elements can be rearranged as follows: $ [6, 10, 15] $ . Then the answer will be $ \gcd(6) + \gcd(6, 10) + \gcd(6, 10, 15) = 6 + 2 + 1 = 9 $ .

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: brute force, dp, greedy, math, number theory
Difficulty: 2200
# Minimize the Difference

## Problem Description

Zhan, tired after the contest, gave the only task that he did not solve during the contest to his friend, Sungat. However, he could not solve it either, so we ask you to try to solve this problem.

You are given an array $ a_1, a_2, \ldots, a_n $ of length $ n $ . We can perform any number (possibly, zero) of operations on the array.

In one operation, we choose a position $ i $ ( $ 1 \leq i \leq n - 1 $ ) and perform the following action:

- $ a_i := a_i - 1 $ , and $ a_{i+1} := a_{i+1} + 1 $ .

Find the minimum possible value of $ \max(a_1, a_2, \ldots, a_n) - \min(a_1, a_2, \ldots, a_n) $ .

## Input Format

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^5 $ ). The description of the test cases follows.

The first line of each test case contains an integer $ n $ ( $ 1 \leq n \leq 2 \cdot 10^5 $ ).

The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_i \leq 10^{12} $ ).

The sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

## Output Format

For each test case, output a single integer: the minimum possible value of $ \max(a_1, a_2, \ldots, a_n) - \min(a_1, a_2, \ldots, a_n) $ .

## Sample #1

### Sample Input #1

```
5
1
1
3
1 2 3
4
4 1 2 3
4
4 2 3 1
5
5 14 4 10 2
```

### Sample Output #1

```
0
2
1
1
3
```

## Hint

In the third testcase, you can perform the operation twice with $ i = 1 $ .

After that, the array is $ a = [2, 3, 2, 3] $ , and $ \max(2, 3, 2, 3) - \min(2, 3, 2, 3) = 3 - 2 = 1 $ .

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: binary search, greedy
Difficulty: 1900
# Password Cracking

## Problem Description

Dimash learned that Mansur wrote something very unpleasant about him to a friend, so he decided to find out his password at all costs and discover what exactly he wrote.

Believing in the strength of his password, Mansur stated that his password — is a binary string of length $ n $ . He is also ready to answer Dimash's questions of the following type:

Dimash says a binary string $ t $ , and Mansur replies whether it is true that $ t $ is a substring of his password.

Help Dimash find out the password in no more than $ 2n $ operations; otherwise, Mansur will understand the trick and stop communicating with him.

## Input Format

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 100 $ ). The description of the test cases follows.

## Output Format

At the beginning of each test case, first read $ n $ ( $ 1 \le n \le 100 $ ) — the size of the binary string. Then proceed to guessing it.

To guess each string $ s $ , you can make no more than $ 2n $ queries of the following type:

- "? t", where $ t $ is a binary string such that ( $ 1 \le |t| \le n $ ).

In response to this query, you will receive $ 1 $ if $ t $ is a substring of $ s $ , and $ 0 $ otherwise.

Once you receive the answer, output a single string in the following format:

- "! s", where $ s $ is a binary string of size $ n $ .

After that, proceed to solve the next test case.

If you make an incorrect attempt or exceed the limit of $ 2n $ attempts, you will receive $ -1 $ instead of an answer and get the verdict Wrong answer. In this case, your program should terminate immediately to avoid undefined verdicts.

After outputting the queries, do not forget to output a newline character and flush the output buffer. Otherwise, you will receive the verdict Solution "hung". To flush the buffer, use:

- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- flush(output) in Pascal;
- stdout.flush() in Python;
- refer to the documentation for other languages.

Hacks:

To use hacks, use the following format of tests:

The first line should contain a single integer $ t $ ( $ 1\le t\le 100 $ ) — the number of test cases.

The first line of each test case should contain a single number $ n $ ( $ 1 \le n \le 100 $ ) — the length of the string. The second line should contain a binary string of size $ n $ .

## Sample #1

### Sample Input #1

```
4
3

0

0

1

4

4

2
```

### Sample Output #1

```
? 00

? 000

? 010

! 010

! 1100

! 0110

! 10
```

## Hint

In the first example, the string $ 010 $ is given. Therefore, the answers to the queries are as follows:

"? 00" $ 00 $ is not a substring of $ 010 $ , so the answer is $ 0 $ .

"? 000" $ 000 $ is not a substring, so the answer is $ 0 $ .

"? 010" $ 010 $ is a substring, so the answer is $ 1 $ .

In the second example, the string is $ 1100 $ , in the third $ 0110 $ , and in the fourth $ 10 $ .

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: constructive algorithms, interactive, strings
Difficulty: 1400