Algo Cup 2025 by csspace.io (Qualification Round)
A. Athletes
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are the host of a large tournament that will feature $$$k$$$ athletes. You have $$$n$$$ familiar athletes, and you want to invite some of them to participate in a tournament. For each athlete, you know their strength and endurance (let's denote the strength of the $$$i$$$-th athlete as $$$p_i$$$ and their endurance as $$$s_i$$$). The $$$j$$$-th athlete will definitely defeat the $$$i$$$-th athlete only if they are strictly stronger and more enduring (i.e., if $$$p_j \gt p_i$$$ and $$$s_j \gt s_i$$$); otherwise, either of them could win.

The tournament proceeds as follows: as long as there are at least two athletes remaining, a pair is formed from two randomly selected athletes who have not been eliminated, the winner stays in the tournament, and the loser is eliminated. This continues until a tournament winner is determined.

To make the tournament as spectacular and unpredictable as possible, you want to invite a set of exactly $$$k$$$ athletes such that the winner is not predetermined. In other words, for a fixed set of $$$k$$$ athletes and considering all possible outcomes of pairwise wins and losses, there will be at least two outcomes where tournament winners are different.

Before finalizing the tournament lineup, you want to determine how many suitable sets of exactly $$$k$$$ athletes exist.

Input

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 5000$$$) — the number of athletes and the size of the tournament.

The second line contains $$$n$$$ integers $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le 10^9$$$); where the $$$i$$$-th integer represents the strength of the $$$i$$$-th athlete.

The third line contains $$$n$$$ integers $$$s_1, s_2, \dots, s_n$$$ ($$$1 \le s_i \le 10^9$$$); where the $$$i$$$-th integer represents the endurance of the $$$i$$$-th athlete.

Output

In a single line, print a number — the amount of suitable sets of exactly $$$k$$$ athletes. Since the answer may be quite large, output it modulo $$$998\,244\,353$$$.

Examples
Input
4 2
1 1 3 3
1 3 1 3
Output
5
Input
5 3
2 2 4 4 5
1 1 4 5 4
Output
7

B. Proof of Incorrectness
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem. Remember that your program must flush the output buffer every time after printing. To flush the output buffer, you can use fflush(stdout) in C++, system.out.flush() in Java, stdout.flush() in Python, or flush(output) in Pascal. If you are using another programming language, check its documentation for how to perform this operation.

Vasya claims that he has invented a sorting algorithm for an $$$n$$$-element array $$$a$$$ (where all elements are pairwise distinct) that makes less than $$$\lceil \log_2 (n!)\rceil$$$ comparisons!

Vasya will ask you no more than $$$\lceil \log_2 (n!)\rceil - 1$$$ queries of the form: compare elements $$$a_i$$$ and $$$a_j$$$. Vasya claims that these queries are sufficient to uniquely determine the permutation of the positions of the array $$$a$$$ from the smallest element to the largest: $$$\operatorname{ord}_1, \operatorname{ord}_2, \dots, \operatorname{ord}_n$$$. Your task is to find a permutation of positions that differs from Vasya's permutation but is consistent with all of Vasya's queries.

Interaction

Initially, the jury's program will send a single integer $$$n$$$ ($$$3 \le n \le 18$$$) — the size of the array.

Then, the jury's program will send no more than $$$\lceil \log_2 (n!)\rceil - 1$$$ queries in the following format:

  • $$$?$$$ $$$i$$$ $$$j$$$ — compare $$$a_i$$$ and $$$a_j$$$ ($$$1 \le i, j \le n$$$; $$$i \ne j$$$).

For each query, your program must output < if $$$a_i \lt a_j$$$, and > otherwise.

After that, the jury's program will send its answer in the following format:

  • $$$!$$$ $$$\operatorname{ord}_1 \operatorname{ord}_2 \dots \operatorname{ord}_n$$$

In response, your program must output a permutation that differs from the jury's permutation and is consistent with all previous queries, in the same format. If there are multiple possible permutations, output any of them. Please pay attention that you should not output the array $$$a$$$!

If your answer is correct, the jury's program will send the string CORRECT on a separate line, indicating that you can terminate the program. If the answer is incorrect, the jury's program will send the string ERROR on a separate line.

If your program violates the format of the queries, the jury will respond with the string ERROR. In this case, your program should terminate immediately to receive a Wrong answer verdict. Otherwise, you may receive an arbitrary verdict because your solution will continue to read from a closed stream.

Remember to flush the output buffer every time you print something!

Example
Input
4
? 2 1

? 4 3

? 4 2

? 1 4

! 1 3 4 2

CORRECT
Output


>

>

<

<

! 3 1 4 2
Note

Note that spaces in the examples are added only for readability. When checking solutions, the interactor will not output empty lines.

C. Mafia Cafe
time limit per test
6 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

In the city NN, the construction of a mafia cafe has been completed. The tables in this cafe are single-seaters and numbered from $$$1$$$ to $$$n$$$ in order of attractiveness, where table $$$1$$$ is the most attractive, and table $$$n$$$ is the least attractive. For convenience, we will also number the mafia members from $$$1$$$ to $$$n$$$ in order of their significance, so that number $$$1$$$ is the most significant mafia boss, and number $$$n$$$ is the least significant recruit.

Mafiosi are very busy people; the $$$i$$$-th of them has only one slot in their schedule when they can visit the cafe — from time $$$a_i$$$ to time $$$b_i$$$ inclusively, and they want to spend all that time in the cafe.

The cafe administrator plans to seat people at the tables, trying to assign the most attractive tables to the most significant mafia members. Mafioso number $$$1$$$ will be seated at table number $$$1$$$, thus occupying that table from time $$$a_1$$$ to time $$$b_1$$$ inclusively. The administrator will also try to seat mafioso number $$$2$$$ at table number $$$1$$$, but if the segments $$$[a_1, b_1]$$$ and $$$[a_2, b_2]$$$ overlap, this will not be possible, and mafioso number $$$2$$$ will get table number $$$2$$$. Each mafioso number $$$i$$$ will be seated at the lowest numbered table that is free during the time segment from $$$a_i$$$ to $$$b_i$$$. Both boundaries of the segment are included, i.e., if for some mafiosi $$$i$$$ and $$$j$$$ it holds that $$$b_i = a_j$$$, they must be assigned different tables.

Help the administrator to arrange the seating.

Input

Each test consists of several test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. The description of test cases follows.

In the first line of each test case, there is an integer number $$$n$$$ ($$$1 \le n \le 250\,000$$$) — the number of mafiosi and tables.

In the $$$i$$$-th of the following $$$n$$$ lines, there are two integers $$$a_i$$$, $$$b_i$$$ ($$$1 \le a_i \le b_i \le 2n$$$), meaning that the $$$i$$$-th mafioso plans to be in the cafe during the time from $$$a_i$$$ to $$$b_i$$$, inclusively.

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$250\,000$$$.

Output

For each test case, output $$$n$$$ integers $$$c_1, c_2, \dots, c_n$$$, where $$$c_i$$$ is the number of the table that the $$$i$$$-th mafioso will sit at.

Example
Input
5
3
1 1
1 2
2 3
4
1 1
3 3
1 2
2 3
2
3 4
1 2
4
2 3
2 5
2 4
4 5
3
1 1
1 2
2 3
Output
1 2 1 
1 1 2 3 
1 1 
1 2 3 1 
1 2 1

D. Three Subsegments
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given an integer array $$$a_1, a_2, \dots, a_n$$$, all numbers in the array in range from $$$1$$$ to $$$m$$$.

Count the number of ways to choose three non-empty, non-overlapping subsegments such that the number of occurrences of each number from $$$1$$$ to $$$m$$$ in the union of these three subsegments is the same even number.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$3 \le n \le 300; 1 \le m \le n$$$) — the size of the array and the maximum possible value in it.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le m$$$) — the array $$$a$$$.

Output

In a single line, print the answer to the problem — the number of ways to choose three non-empty, non-overlapping subsegments such that the number of occurrences of each number from $$$1$$$ to $$$m$$$ in the union of these three subarrays is the same even number.

Examples
Input
5 2
2 1 2 2 1
Output
7
Input
12 3
1 2 3 2 1 3 3 1 1 2 3 2
Output
278
Note

In the first test, all valid unions look like this:

  • [2] [1] 2 [2 1];
  • [2] [1 2] 2 [1];
  • [2 1] [2] 2 [1];
  • [2 1] 2 [2] [1];
  • 2 [1] [2] [2 1];
  • 2 [1] [2 2] [1];
  • 2 [1 2] [2] [1];

For the second test, there are only some of the valid unions:

  • [1 2 3 2] [1 3 3 1 1 2] [3 2];
  • 1 2 [3 2] 1 [3] 3 [1 1 2] 3 2;
  • [1 2 3] 2 1 3 [3 1] 1 2 3 [2];
  • [1] [2 3 2] [1 3] 3 1 1 2 3 2;
  • [1] 2 3 2 1 3 [3 1] 1 [2 3 2];
  • 1 [2 3] [2 1 3] 3 1 [1] 2 3 2;

E. Shortest Non-Shortest Path
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an undirected connected graph consisting of $$$n$$$ vertices and $$$m$$$ edges. There are no self-loops and multiple edges in the graph. You have to find any path $$$P$$$ between the specified vertices $$$s$$$ and $$$t$$$ such that:

  1. $$$P$$$ does not contain any vertex of the graph more than once;
  2. $$$P$$$ contains more vertices than the shortest path between $$$s$$$ and $$$t$$$;
  3. $$$P$$$ contains the least number of vertices among all paths that satisfy conditions $$$1$$$ and $$$2$$$.
Input

The first line contains four integers $$$n$$$, $$$m$$$, $$$s$$$, $$$t$$$ ($$$2 \le n \le 2\,000$$$; $$$n-1 \le m \le 25\,000$$$; $$$1 \le s, t \le n$$$, $$$s\neq t$$$) — the number of vertices and edges in the graph, and the endpoints of the path $$$P$$$, respectively.

The next $$$m$$$ lines describe the edges: edge $$$i$$$ is defined by a pair of vertices $$$a_i$$$, $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$a_i \ne b_i$$$), where $$$a_i$$$ and $$$b_i$$$ are the vertices connected by the $$$i$$$-th edge.

It is guaranteed that there are no self-loops and multiple edges in the given graph.

Output

If the desired path $$$P$$$ does not exist, print $$$-1$$$ in a single line.

Otherwise, in the first line, print the number $$$k$$$ — the number of vertices in the path $$$P$$$. In the second line, print $$$k$$$ distinct integers, $$$v_1, v_2, \ldots, v_k$$$ ($$$1\le v_i \le n$$$, $$$v_1=s$$$, $$$v_k=t$$$, $$$v_i$$$ and $$$v_{i+1}$$$ are connected by an edge for any $$$1 \le i \lt k$$$) — the vertex numbers in the path $$$P$$$.

If there are multiple answers, print any of them.

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

F. Almost Bipartite Graph
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an undirected graph consisting of $$$n$$$ vertices and $$$m$$$ edges. The graph has no self-loops or multiple edges. It is not guaranteed that the given graph is connected.

Recall that a graph is called bipartite if it is possible to color all the vertices with two colors such that no edge connects two vertices of the same color.

Your task is to determine whether it is possible to remove no more than $$$k$$$ edges in such a way that the resulting graph becomes bipartite.

Input

The first line contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$2 \le n \le 10^3$$$; $$$1 \le m \le 10^3$$$; $$$1 \le k \le 10$$$) — the number of vertices and edges in the graph, and the maximum number of edges that can be removed.

The next $$$m$$$ lines follow, where the $$$i$$$-th line contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$x_i \ne y_i$$$), representing an edge between vertices $$$x_i$$$ and $$$y_i$$$. The given graph has no self-loops or multiple edges.

Output

In the first line, print the number of edges (no more than $$$k$$$) that need to be removed for the graph to become bipartite. In the second line, output the indices of the edges.

If such a set of edges does not exist, output -1 in a single line.

If there are multiple suitable sets of edges, output any of them. The indices of the edges can be output in any order. Edges are numbered from $$$1$$$ to $$$m$$$ in order of the input.

Examples
Input
4 5 1
1 2
1 3
2 3
2 4
3 4
Output
1
3
Input
4 6 1
1 2
2 3
4 2
3 4
3 1
1 4
Output
-1
Input
5 3 2
1 2
2 3
4 5
Output
0
Input
5 6 10
1 2
3 2
5 3
3 4
4 5
1 4
Output
6
1 2 3 4 5 6