Background

Xiao Zhi is watching a not-so-famous Bilibili uploader, 脚踢喷火幼儿园 (hereinafter referred to as “喷火”), and his friends ATA_Radio_STN and sltheen playing the famous game PLAYERUNKNOWN’S BATTLEGROUNDS (PUBG: Battle Royale).

Problem Description

喷火 has just landed after parachuting. Dangers are everywhere around him. He has an initial backpack, and all supplies he picks up will be put into this backpack. The game map is simplified into an $n \times m$ grid, and each cell contains either supplies or an enemy.

Supplies are divided into primary/secondary weapons and ammunition. Ammunition is further divided into bullets and throwables. Each weapon corresponds to a certain bullet type. For example, the Beryl M762 assault rifle uses 7.62mm bullets, the M416 assault rifle uses 5.56mm bullets, and the AKM assault rifle also uses 7.62mm bullets.

When 喷火 walks onto a cell containing supplies, he will pick up the supplies on the ground and put them into the backpack. However, the backpack capacity is limited, so when it is full, he will throw away some supplies to make room for the new supplies. He discards supplies according to the following rules:

1. If the picked-up item is a weapon, then replace according to the priority: shotgun > assault rifle > designated marksman rifle > bolt-action rifle > bare hands. Prefer replacing the primary weapon, and the primary weapon’s priority must be strictly higher than the secondary weapon’s. If the primary weapon is replaced, the replaced primary weapon is discarded directly, and will no longer be used to replace the secondary weapon.
2. If there are unnecessary bullets (meaning bullets not used by either the primary or secondary weapon), discard these bullets first, until there is enough space to hold the new supplies.
3. If after discarding all unnecessary bullets, space is still insufficient, or if there are multiple kinds of unnecessary bullets, then discard the ammo whose latest pickup time is earliest (including bullets used by the primary/secondary weapon and throwables), until there is enough space to hold the new supplies. (Note that even if the new supplies are “unnecessary bullets”, after discarding all existing “unnecessary bullets”, if the backpack space is still not enough, 喷火 will still discard other ammo until he picks up all the “unnecessary bullets”.)
4. Whether the picked-up item is new or already owned, its latest pickup time will be updated to the current time.
5. At most two weapons can be held at the same time, i.e., primary/secondary weapons. Weapons of the same priority will not replace each other between primary and secondary.

Each cell’s supplies will only be picked up once. When entering a cell for the second time, items will not respawn: he will not pick up the items dropped last time in this cell, nor will he pick up the initial items again.

When 喷火 walks onto a cell containing an enemy, he will fight the enemy. He is very strong in combat: he only needs enough bullets to eliminate the enemy. Each enemy has two parameters $a, b$, meaning it requires consuming $a$ rounds of primary-weapon bullets; if the primary-weapon bullets are not enough, then do not consume primary-weapon bullets, but consume $b$ rounds of secondary-weapon bullets instead. If neither the primary nor secondary weapon has enough bullets, then 喷火 is killed by the enemy, and the enemy will squat-taunt on his loot box.

Each cell’s enemy will only appear once. If entering a cell with an enemy for the second time, nothing will happen.

Now, 喷火 starts on the cell at row 1, column 1. ATA_Radio_STN has already scouted the map situation for him, and sltheen will give him commands. 喷火 wants to know whether he is still alive after executing the last command. If he survives, output the item types and quantities in the backpack in order of latest pickup time from earlier to later. If he dies, output the coordinates of the cell where he dies.

Below are the possible supplies, their categories, the bullet types they use, the space required, and their corresponding IDs.

Weapons:

Ammunition:

Please note that in the table above, the “Space Used” of bullets means the space occupied by a single round.

In addition, the enemy’s ID on the map is 17.

Input Format

The first line contains four integers, representing the number of map rows $n$, columns $m$, backpack capacity $k$, and the number of commands sltheen will give, $t$.
In the next $n \times m$ lines, line $i$ represents the cell at row $\lfloor\frac{i - 1}{n}\rfloor + 1$ and column $(i - 1)\%n + 1$. Here, $i \% n$ denotes the remainder when dividing $i$ by $n$:

• If this cell contains supplies, this line contains two space-separated integers: the supply ID $x$ and the quantity $y$. The supply ID can be found in the last column of the table in “Description”. (If the supply is a gun, it is guaranteed that $y = 1$.)
• If this cell contains an enemy, this line contains three space-separated integers. The first integer is $17$, indicating an enemy. The next two integers are the enemy’s parameters $a, b$.

Then follow $t$ lines, each containing an integer $op$, indicating the movement direction command given by sltheen: 1 means up, 2 means down, 3 means left, 4 means right. (Row 1, column 1 is the top-left corner of the map, and the last row, column 1 is the bottom-left corner.)

Output Format

If 喷火 dies, output two numbers $u, v$, meaning he dies at row $u$, column $v$.

If 喷火 does not die, first output two lines: the first line is the primary weapon ID, and the second line is the secondary weapon ID. Then output several lines; each line contains two integers separated by a space: the first integer is the supply name, and the second integer is its quantity. Output them sorted by the latest pickup time from earlier to later.

3 3 60 8
1 1
14 300
15 30
5 1
10 1
17 11 10
17 10 10
17 10 10
15 10
4
4
2
3
3
2
4
4

1
0
14 254
10 1
15 12

Hint

Constraints

For all test points, it is guaranteed that:

• $1 \leq n, m \leq 100$, and $1 \leq n \times m \leq 100$.
• $1 \leq k \leq 500$, $1 \leq t, a, b \leq 200$.
• $1 \leq x \leq 16$, $1 \leq y \leq 5000$.
• $1 \leq op \leq 4$.
• The testdata guarantees that each cell contains only one type of supplies (or one enemy), and that the backpack can hold the supplies in any single cell.

Translated by ChatGPT 5