Final round of the X Vologda Regional Informatics Olympiad for the Governors Prize 2025, grades 9-10
1. Weights
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given $$$4 \cdot k$$$ weights with masses of 1 gram, 2 grams, ..., $$$4 \cdot k$$$ grams. They are divided into two equal parts in terms of both quantity and mass. Remove two weights from each group so that the masses of the groups remain equal.

Input

The first line of the input contains an integer $$$k$$$ ($$$1 \le k \le 50000$$$). The second line contains $$$2 \cdot k$$$ integers separated by spaces, which are the masses of the weights in the first group. The third line contains $$$2 \cdot k$$$ integers, which are the masses of the weights in the second group. The sums of the numbers in the groups are equal. Each number from 1 to $$$4 \cdot k$$$ appears exactly once.

Output

Output four integers in any order – the masses of the weights that need to be removed. If there are multiple correct answers, output any.

Scoring

Subtask 1 (up to 40 points): $$$k \le 20$$$

Subtask 2 (up to 28 points): $$$k \le 200$$$

Subtask 3 (up to 32 points): $$$k \le 50000$$$

Example
Input
2
2 5 3 8
7 1 6 4
Output
3 2 4 1
Note

Note for Python users: to input a set of numbers separated by spaces, you can do it like this: 

a = [int(x) for x in input().split()]

2. Weights Again
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

While creating tests for the previous problem, the jury pondered the question: how many different tests can be devised for a given $$$k$$$? The jury considers two tests to be different if one cannot be obtained from the other by swapping groups and/or permuting numbers within the groups. Write a program to find the answer to this question.

Input

A single integer $$$k$$$ ($$$1 \le k \le 16$$$) is given.

Output

Output a single integer — the number of ways to split the first $$$4 \cdot k$$$ natural numbers into two groups of $$$2 \cdot k$$$ numbers each, such that the sums of the numbers in the groups are equal.

Example
Input
2
Output
4
Note

For the example with $$$k=2$$$, there are 4 different ways to partition:

  • 1 2 7 8 and 3 4 5 6
  • 1 3 6 8 and 2 4 5 7
  • 1 4 5 8 and 2 3 6 7
  • 1 4 6 7 and 2 3 5 8

Grading System. Solutions that work correctly for $$$k \le 6$$$ will be awarded 50 points.

Note: The answer may not fit in a 32-bit integer type; it is recommended to use a 64-bit type (long long in C++, long in Java and C#, int64 in Pascal). In Python, no additional steps are required.

3. First Number
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Vasya wrote down $$$n$$$ consecutive positive integers on a piece of paper. In total, there are $$$k$$$ digits written down. What number did Vasya write first?

Input

Two integers $$$n$$$ and $$$k$$$ are given, each on a separate line ($$$1 \le n \le 10^{17}$$$, $$$1 \le k \le \min(18 \cdot n, 10^{18})$$$).

Output

Output the number that was written first. If there are multiple correct answers, output the smallest one. If there are no solutions, output -1.

Examples
Input
9
10
Output
2
Input
2
1
Output
-1
Note

Grading System.

Subtask 1 (up to 28 points): $$$n \le 100$$$, $$$k \le \min(3 \cdot n, 10^3)$$$.

Subtask 2 (up to 36 points): $$$n \le 10^6$$$, $$$k \le \min(7 \cdot n, 10^7)$$$.

Subtask 3 (up to 36 points): $$$n \le 10^{17}$$$, $$$k \le \min(18 \cdot n, 10^{18})$$$.

Note: The input data and answer in the third subtask may not fit into a 32-bit integer type, it is recommended to use a 64-bit type (long long in C++, long in Java and C#, int64 in Pascal). In Python, no additional actions are required.

4. Search with Error
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Write a program to search for a substring in a string. Additional condition: one error is allowed, meaning that one pair of characters may not match.

Input

The first line of the input contains the string $$$s$$$, in which we are searching. The second line contains the substring $$$q$$$, which we are looking for. The strings contain only lowercase Latin letters, and their lengths do not exceed $$$2 \cdot 10^5$$$ characters.

Output

Output a single integer — the position of the occurrence of the substring $$$q$$$ in the string $$$s$$$ (positions are numbered starting from one). If there are multiple correct answers, output the smallest one. If there are no occurrences, output 0.

Example
Input
abacabadaba
bad
Output
2
Note

Solutions that work for strings of length up to 1000 characters can earn up to 40 points.

5. Square in the Maze
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A maze of size $$$N \times M$$$ cells is given. In the upper left corner of the maze, there is a square with a side length of $$$P$$$ cells. In one step, the square can move one cell up, down, right, or left, provided it does not collide with occupied cells. You need to find the shortest possible path length for the square to reach the lower right corner.

Input

The first line contains three numbers $$$N$$$, $$$M$$$, $$$P$$$. Next, there are $$$N$$$ lines of $$$M$$$ characters representing the cells of the maze: '.' if the cell is free, 'X' if it is occupied. It is guaranteed that the upper left and lower right $$$P \times P$$$ squares do not contain occupied cells.

Output

Output the shortest possible path length, or $$$-1$$$ if such a path does not exist.

Examples
Input
5 5 2
...XX
....X
X...X
XX...
XX...
Output
6
Input
5 5 2
...XX
...XX
XX.XX
XX...
XX...
Output
-1
Note

Subtask 1 (up to 20 points): $$$1 \leq N,M \leq 10$$$, $$$P = 1$$$

Subtask 2 (up to 20 points): $$$1 \leq N,M \leq 2000$$$, $$$P = 1$$$

Subtask 3 (up to 20 points): $$$1 \leq N,M \leq 50$$$, $$$P = 2$$$

Subtask 4 (up to 20 points): $$$1 \leq N,M \leq 2000$$$, $$$1 \leq P \leq \min(50,N,M)$$$

Subtask 5 (up to 20 points): $$$1 \leq N,M \leq 2000$$$, $$$1 \leq P \leq \min(N,M)$$$