In this task, you take on the role of a judge of the Polish Olympiad in Informatics. You are currently preparing tests for one of the problems. You have found a flawed solution and now you must prepare tests that this solution will fail. This task consists of three subtasks. Your job is to write one program which, based on the input, recognizes which subtask it is dealing with and finds a solution for that subtask.

Since your solutions will generate tests, they must print the data in exactly the format specified. You must take care of spaces and newline characters. In particular, at the end of the output you must always print exactly one newline character.

Task Files

• quicksort.cpp
• dijkstra_wolna.cpp
• dijkstra_poprawna.cpp
• bfs_poprawny.cpp

The above files contain the source codes referenced later.

Note: You can obtain a total of 150 points for this task.

Scoring

Subtask 1. (50 points)

In this subtask, you are given a sequence of $n$ integers that must be sorted. File quicksort.cpp contains a solution that implements the Quicksort algorithm. Due to the pivot selection method used, this solution may run slowly. Your task is to write a program that generates tests for which the total number of iterations of the two inner while loops in the quicksort function is at least $50n$.

Input Format

The first and only line of input contains the word sortowanie, followed by an integer $n$ ($200 \leq n \leq 100,000$).

Output Format

Your program should print the input data for quicksort.cpp in the following format. The first line of output should contain the integer $n$ read from the input. The second line should contain a sequence of $n$ integers $a_i$ ($1 \leq a_i \leq 10^9$).

Subtask 2. (50 points)

In this subtask, you are given a square board of size $n \times n$ consisting of $n^2$ square cells. A token moves on the board. In each move, the token can move to one of the four cells adjacent to the cell it is currently in. Some cells are blocked and the token can never be on them. The remaining cells are called accessible cells. The goal is to compute, for each accessible cell, in how many moves the token can reach it. A correct solution is in bfs_poprawny.cpp. It contains an implementation of BFS using the STL queue template.

However, it is easy to make a certain (non-obvious) mistake and use a queue implementation that assumes that the queue will contain at most 1000 elements at any time. In this subtask, your program should output a test for which the above procedure will, at some point during execution, store more than 1000 elements in the queue.

Input Format

The first and only line of input contains the word bfs, followed by an integer $n$ ($300 \leq n \leq 2000$).

Output Format

Your program should print the input data for bfs_poprawny.cpp in the following format. The first line should contain the integer $n$ read from the input, followed by two integers $p_x$ and $p_y$ ($1 \leq p_x,p_y \leq n$). They mean that the token starts at the cell in row $p_x$ and column $p_y$.

Next, there should be a description of the board as $n$ lines of $n$ characters # and/or . — these denote a blocked cell and an accessible cell, respectively. The starting cell must be accessible.

For the given board, in the program bfs_poprawny.cpp, more than 1000 elements should be inserted into the queue.

Subtask 3. (50 points)

In this subtask, you must write an algorithm that finds shortest paths in an undirected graph whose edges have lengths given by positive integers. The graph consists of $n$ vertices, numbered $1,\ldots,n$. The goal is to find the distance from vertex 1 to every vertex of the graph. A correct solution can be found in dijkstra_poprawna.cpp. It implements a (slightly modified) Dijkstra algorithm using priority_queue, i.e. the STL priority queue.

Short description of the modification

In the textbook version of Dijkstra’s algorithm, for each unvisited vertex for which we have already found some path, we store the length of that path in the priority queue and update this value. The modification in the attached code is that when we find a new, shorter path to a vertex, we simply add a new element to the priority queue. The queue element that represented the previous value becomes “garbage” from that point on, so when removing elements from the queue we check whether we encounter “garbage”, and if so we skip processing it (see the break instruction in the code).

One mistake that can be made here is using a normal queue instead of a priority queue. Such an implementation is in dijkstra_wolna.cpp. It is correct, but sometimes runs much more slowly.

Your task is to write a program that generates tests for which the inner for loop in the second program executes at least 20 times more iterations than the analogous loop in the first program.

Input Format

The first and only line of input contains the word sciezki, followed by an integer $n$ ($300 \leq n \leq 100,000$).

Output Format

Your program should print the input for dijkstra_poprawna.cpp and dijkstra_wolna.cpp in the following format. The first line of output should contain: the integer $n$ read from input and an integer $m$ ($1 \leq m \leq 5n$). The number $n$ is the number of vertices, and $m$ is the number of edges. In the next $m$ lines, you should print the descriptions of the edges. The description of one edge should consist of three integers $a_i$, $b_i$, $c_i$ ($1 \leq a_i, b_i \leq n$, $a_i \neq b_i$, $1 \leq c_i \leq 10^9$). For each pair of vertices, there may exist at most one edge connecting them. Each edge of the graph should be printed exactly once. There must exist at least one edge incident to vertex 1.