Background

In 1951, after the end of the $-32$nd National Youth Informatics Olympiad Winter Camp, little A, who had been competing all morning, was extremely tired and wanted to relax. So he used the Time Transport Interface (Time Transport Interface) to connect to a computer from 2015, and obtained the latest game “AC Project 15 / Legacy of DWT AKing IOI” to play.

Problem Description

This is a traditional problem.

You need to control a robot to play a bullet-dodging game. The game screen is a rectangle in the first quadrant, with coordinates ranging from $(0,0)$ to $(n,m)$. The robot initially spawns at $(0,0)$. You can control the robot using the following commands:

$$\begin{array}{|c|l|}\hline \textsf{\textbf{Command}} & \textsf{\textbf{Description}} \cr\hline \bm 0 & \textsf{The robot stays still} \cr\hline \bm 1 & \textsf{The robot moves left by $1$ unit, i.e. from $(x,y)$ to $(x-1,y)$} \cr\hline \bm 2 & \textsf{The robot moves down by $1$ unit, i.e. from $(x,y)$ to $(x,y-1)$} \cr\hline \bm 3 & \textsf{The robot moves up by $1$ unit, i.e. from $(x,y)$ to $(x,y+1)$} \cr\hline \bm 4 & \textsf{The robot moves right by $1$ unit, i.e. from $(x,y)$ to $(x+1,y)$} \cr\hline \end{array}$$

The command sequence you construct is represented by a digit string $C'$. Each command has a certain cost. Specifically, for the original commands $C'$, each occurrence of command $i$ costs $P_i$.

Your commands will be repeated $k$ times as the robot’s movement commands $C$. For example, when $C'=1123$ and $k=3$, the robot receives $C=112311231123$.

In the game, $b$ bullets will be generated. Each bullet is represented by an ordered 6-tuple $(l_i,r_i,x_i,y_i,p_i,q_i)$. This means the bullet is created at second $l_i$ and destroyed at second $r_i$. Its initial position is $(x_i,y_i)$. Each second it moves $p_i$ units in the positive $x$ direction and $q_i$ units in the positive $y$ direction.

The game lasts for $d$ seconds. If within these $d$ seconds the robot collides with a bullet or moves outside the screen, the robot explodes and the game fails. If the robot does not explode by the end of second $d$, the game is won.

Each second in the game is divided into five phases, and the next phase is executed only after the previous one ends:

1. Robot movement phase. In second $i$, the robot executes command $C_i$. If the length of $C$ is $< i$, meaning all commands have been executed, then it stays still.
2. Bullet movement phase. All bullets that have already been created and not yet destroyed move once. Specifically, let the current second be $c$. For each bullet $(l_i,r_i,x_i,y_i,p_i,q_i)$ satisfying $l_i<c\le r_i$, its position becomes $(x_i+(c-l_i)p_i,y_i+(c-l_i)q_i)$.
3. Bullet creation phase. Let the current second be $c$. For all bullets with $l_i=c$, create them on the screen at their initial positions $(x_i,y_i)$.
4. Check phase. If at this moment the robot’s position is outside the screen, or it collides with any bullet that has been created and not yet destroyed, then the robot is hit and explodes. More precisely, for each bullet on the screen, let its position at the start of this second be $P=(x',y')$ and its current position be $Q=(x'',y'')$. If the bullet is created during this second, then $P=Q$. Consider the line segment $PQ$. If the robot’s current coordinates lie on this segment (including endpoints), it is considered a collision with the bullet.
5. Bullet destruction phase. Let the current second be $c$. For all bullets with $r_i=c$, destroy them.

Input Format

• The first line contains six integers $n,m,b,d,k,maxc$.
• The second line contains five integers $P_0,P_1,P_2,P_3,P_4$.
• Lines $3$ to $b+2$ each contain six integers. In line $i+2$, the integers represent $l_i,r_i,x_i,y_i,p_i,q_i$.

Output Format

• If $maxc\ge 0$, output one line with a string representing the command sequence you construct. You must guarantee that the command cost is $\le maxc$.
• Otherwise, output one line with one integer, the minimum cost among all command sequences that can successfully finish the game.

1 1 3 100 1 5
1 1 1 2 3
1 100 0 0 1 0
1 100 1 0 0 0
2 3 0 1 0 0

34

Hint

Sample Explanation

In the diagram, 0 represents bullets, 1 represents the robot, and . represents an empty cell.

Second $1$: the robot moves to $(0,1)$; a bullet is created at $(0,0)$ and another at $(1,0)$.

1.
00

Second $2$: the robot moves to $(1,1)$; the bullet at $(0,0)$ moves to $(0,1)$; a bullet is created at $(0,1)$. So now there are two bullets at $(0,1)$ (in the figure below, because the bullets overlap, only one is shown).

01
.0

Second $3$: the robot does not move; one bullet at $(0,1)$ flies out of the screen; the other bullet at $(0,1)$ is destroyed.

.1
.0

Seconds $4$ to $100$: the robot does not move; the bullet outside the screen remains outside after moving, and the bullet inside the screen does not move. The screen is the same as in the third second.

Therefore, this command sequence can successfully finish the game, and the cost is $1\times 3+ 1 \times2=5$.

---

Constraints and Limits

This problem uses bundled tests.

$$\begin{array}{|c|c|c|c|c|c|c|c|c|}\hline \textbf{subtask} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\cr\hline \textbf{Score} & 10 & 10 & 10 & 10 & 15 & 15 & 15 & 15\cr\hline \end{array}$$

For $100\%$ of the testdata, it is guaranteed that $n,m,b,d,P_i\ge0$, $k\ge 1$, $1\le l \le r$, and $maxc\ge-1$.

You might think: what kind of constraints are these? Why is there no upper bound? And why are there no special limits for each subtask in the table? In fact, the problem setter also does not know the upper bounds or the special limits.

Due to an operational mistake by the setter, the source code of the data generator was accidentally lost, and only the executable remains. The provided files include executables compiled for Windows / Linux / Mac. The file names on different operating systems are as follows:

• For Windows (file name genX-w32): g++ genX.cpp -o genX -O3 -std=c++14, compiled on Windows10 with Dev-C++ 5.50 and TDM-GCC 4.9.2 32bit.
• For Linux/Mac (32-bit, file name genX-l32): g++ genX.cpp -o genX -O3 -std=c++14 -m32, compiled on NOI Linux 2.0 with GCC 9.3.0.
• For Linux/Mac (64-bit, file name genX-l64): g++ genX.cpp -o genX -O3 -std=c++14 -m64, compiled on NOI Linux 2.0 with GCC 9.3.0.

After starting the data generator, you need to input an integer in the range $[1,2^{30})$ as the random seed. It will generate an input file into 0.in. The setter cannot guarantee the constraints of the generated data, but can guarantee:

• Data generated by the same generator share the same special limitation.
• All generators run on NOI Linux 2.0 with an i5-4200m CPU, taking no more than 3s and using no more than 2G memory.
• The generated data depends only on the seed you input, and does not depend on other changing factors such as current time or operating system.
• Some data generators have a very small probability of generating an unsolvable instance, but it is guaranteed that all data on the OJ has a solution.
• The seed you input is used only as a random seed. The generator will not do things like special-casing certain seeds to generate interfering data.

Each subtask’s data corresponds to data generated by one generator. The generator for subtask number $X$ is genX.

Note: since the input format does not require you to input the “subtask number”, you need to determine by yourself which subtask the current data belongs to. Also, the subtasks are in a shuffled order, so you need to judge the difficulty of each subtask by yourself.

Also, the provided files include checker.cpp. Compile it using g++ checker.cpp -o checker -std=c++14, then run ./checker <inputfile> <outputfile>, and checker will report whether the game is won or lost. Here <inputfile> is the .in file generated by the data generator, and <outputfile> contains your output. This checker is only for understanding the game rules. It is different from the checker actually used, and it does not guarantee that the time complexity of the checker is correct.

Translated by ChatGPT 5