Grid Survival and Inventory Management

You are given an n × m grid representing a game map. Each cell in the grid contains either an item or an enemy. Items include weapons and ammunition. Ammunition comes in various types and each bullet occupies a specified amount of space. Weapons use a specific type of bullet (see tables below).

The list of possible weapons is:

Weapon Name	Type	Bullet Type Used	Code
Empty Hand	Empty	N/A	0
BerylM762	Assault Rifle	7.62mm	1
AKM	Assault Rifle	7.62mm	2
SKS	Marksman Rifle	7.62mm	3
Kar98K	Bolt-action	7.62mm	4
M416	Assault Rifle	5.56mm	5
MK12	Marksman Rifle	5.56mm	6
Mini14	Marksman Rifle	5.56mm	7
S686	Shotgun	12# Shotgun	8
DBS	Shotgun	12# Shotgun	9

The list of possible ammunition (and throwables) is:

Ammunition Name	Type	Space Occupied per Unit	Code
FragGrenade	Throwable	5	10
SmokeGrenade	Throwable	4	11
MolotovCocktail	Throwable	3	12
Flashbang	Throwable	2	13
7.62mm	Bullet	0.2	14
5.56mm	Bullet	0.1	15
3in (12# Shotgun)	Bullet	0.5	16

An enemy is represented by code 17 and comes with two parameters a and b. When you step into a cell with an enemy, combat occurs. The enemy requires you to spend a rounds of ammunition from the bullet type used by your primary weapon. If you do not have enough ammo for your primary weapon, then you will instead spend b rounds from the bullet type used by your secondary weapon. If neither weapon’s ammunition is sufficient, you die, and the enemy leaves a mocking mark at that cell.

You start at cell (1, 1) with an initial backpack that already contains the Empty Hand weapon (code 0) and occupies a space of 1 unit. Your backpack has a limited capacity (given in the input). Each item occupies some space (we assume weapons cost 1 unit each while ammunition costs as in the table above).

When you enter a cell with an item, you pick it up (each cell’s item is only available once). However, if there is not enough space in your backpack, you must free space by discarding items based on the following rules:

1. If the item is a weapon, you may replace one of your current weapons. The replacement priority is as follows (from high to low): Shotgun > Assault Rifle > Marksman Rifle > Bolt-action > Empty Hand. You always try to replace your primary weapon provided that its priority is lower than the new weapon and (if you have a secondary weapon) its priority is strictly higher than the secondary weapon. If you replace the primary weapon, the dropped weapon is discarded permanently.
2. If the item is ammunition, first discard any ammunition that is not used by either of your currently held weapons (i.e. not matching the bullet type of any weapon you hold) in the order of the earliest last pickup time, one unit at a time, until there is enough space.
3. If discarding all non‐needed ammunition does not free enough space (or there are multiple kinds of non‐needed ammunition), continue discarding other ammunition (including those that you actually need) in the order of earliest last pickup time until there is sufficient space. (Note: even if the new item is ammunition that is not needed, if freeing space from non‐needed ammo is not enough, you still drop other ammunition.)
4. Regardless of whether the new item is being picked up for the first time or is already in your backpack, its last pickup time is updated to the current time.
5. You may only hold at most two weapons at the same time (primary and secondary). If a weapon with the same priority as one you already hold is picked up, no replacement occurs.

Cells with items or enemies only trigger their effect the first time you enter; revisiting a cell does nothing.

The input consists of a description of the grid and a series of move instructions (each being U, D, L, or R). After executing the last instruction, if you are still alive, output the list of item types and quantities in your backpack sorted by last pickup time (from earliest to latest). If you die during an enemy encounter, output the coordinates of the cell where you died.

Input and Output Details:

The input format is as follows:

n m C T
(row 1 of grid)
(row 2 of grid)
...
(row n of grid)
(instruction 1)
(instruction 2)
...
(instruction T)

In the grid, each cell is represented by a token. For an item, the token is its code (an integer). For an enemy, the token is formatted as 17,a,b (without spaces) where a and b are integers.
Note: All coordinates are 1-indexed.

inputFormat

The first line contains four numbers: n, m, C, and T where n and m are the dimensions of the grid, C is the total backpack capacity (a number), and T is the number of move instructions.

The next n lines each contain m tokens separated by spaces representing the grid. Each token is either an integer (indicating an item code) or a string of the form 17,a,b indicating an enemy with parameters a and b.

The following T lines each contain a single character: U (up), D (down), L (left), or R (right), indicating the move direction.

outputFormat

If you die during an enemy encounter, output the row and column (separated by a space) of the cell where you died.

If you survive all moves, output the inventory content in ascending order by their last pickup time. For each distinct item in your backpack, output a line with the item code and its quantity separated by a space. (Note: If the same item is picked up multiple times, only the latest pickup time is used for sorting.)

sample

2 2 5 2
1 14
17,2,1 5
D
R

2 1