Conveyor Chaos

With the observatory back online and the star map finally rendering again, the crew could see exactly where they were: still weeks from Earth, the rocket cruising on autopilot through a quiet stretch of deep space. The constellations on the panoramic viewport drifted slowly, and the rhythm of Ramadan settled back in.

Halfway through the month, someone suggested they set up their own version of mawa'id ar-rahma, the long community food tables that line every Algerian street at iftar time. Back home, strangers sit side by side, sharing bowls of chorba and plates of bourek while the evening sky turns orange. Up here, the crew rigged a system of conveyor belts in the cargo bay to distribute food packets to different compartments across the ship.

The idea was simple. Drop a food packet on a belt, and the directional arrows carry it to the right compartment. But something went wrong with the configuration. Packets kept looping endlessly through the same belts, and some flew right off the edge into the void of the cargo bay's open side. Dr. Mkouli needed to know where every packet ended up. Some were disappearing entirely, and the rest just went in circles.

Input Format

• Line 1: R C T I where R is the number of rows, C is columns, T is ticks to simulate, and I is the number of items.
• Lines 2 to R+1: The conveyor grid. Each character is one of >, <, v, ^.
• Lines R+2 to R+1+I: Each line contains r c, the starting row and column of an item (0-indexed).

Every cell has exactly one conveyor belt. Multiple items may start on the same cell. Items do not interact with each other (they pass through one another and occupy the same cell freely).

R, C <= 1,000. T <= 10^18. I <= 500,000.

Simulate the conveyor system for exactly T ticks. Each tick, every item simultaneously moves one cell in the direction of its current cell's belt. If an item moves off the grid (past any edge), it is lost and removed permanently.

After T ticks, compute the position checksum: Checksum = sum of (row_i * C + col_i) for all surviving items.

If no items survive, output 0.

Output: The checksum as a single integer.

Example Input

4 5 5 3
>>v<>
^>v<^
<>v<v
>>^<<
0 4
0 0
2 0

Example Walkthrough

Item 1 at (0,4):

Tick 1: Starts at (0,4) on belt >. Moves right. Result: OFF GRID. Item is permanently lost.

Item 2 at (0,0):

Tick 1: (0,0) belt > moves to (0,1) Tick 2: (0,1) belt > moves to (0,2) Tick 3: (0,2) belt v moves to (1,2) Tick 4: (1,2) belt v moves to (2,2) Tick 5: (2,2) belt v moves to (3,2) Position after 5 ticks: (3,2). Contribution: 3 * 5 + 2 = 17.

Item 3 at (2,0):

Tick 1: Starts at (2,0) on belt <. Moves left. Result: OFF GRID. Item is permanently lost.

Checksum = 0 + 17 + 0 = 17.

What is the position checksum after T ticks?