Island Shuttle Routing

This is an Agentics migration of Frontier-CS algorithmic problem 309.

Your submitted zip_project run command is executed once per case. It receives exactly one case on stdin and must write the candidate answer to stdout. Do not read or write challenge-owned files. Network access is unavailable during setup, build, and run.

The trusted separated evaluator uses the original Frontier-CS Testlib checker. Public validation is intentionally small and only checks the interface. Official scoring uses the private Frontier-CS-derived run manifest.

Original Statement

Archipelago Relay Network Design

Problem

The Republic of AtCoder consists of L+1 islands aligned west-to-east, numbered 0 to L.

For each 1 <= k <= L, there is a bidirectional air route between islands k-1 and k. Route k is operated by company S_k, which is either A or J.

The government now wants to establish a permanent cargo relay network for daily shipments.

There are N residents who may be hired as shuttle operators.

• Resident i lives on island X_i.
• They own a company coupon C_i (A or J).
• Hiring them costs a fixed management fee H_i.
• If hired, they can operate one bidirectional shuttle service between two islands l_i < r_i such that r_i - l_i <= D_i.

A hired resident creates a direct bidirectional shuttle edge between l_i and r_i.

Coupon rule

When a resident travels along a route owned by their coupon company, that route is free for them. Otherwise, it costs 1.

Therefore:

• The operating cost per unit cargo of resident i's shuttle (l_i, r_i) is the number of routes on the path from l_i to r_i whose owner is not C_i.
• The setup cost of hiring resident i for shuttle (l_i, r_i) is

H_i + min(cost_i(X_i, l_i), cost_i(X_i, r_i))

where cost_i(u, v) is the number of routes on the path between islands u and v whose owner is not C_i.

In addition to hired shuttles, the government may always use the original adjacent-island routes directly for cargo transport at cost 1 per unit cargo per route.

---

There are M daily cargo demands.

Demand j requires shipping W_j units of cargo from island A_j to island B_j every day.

For a fixed set of hired shuttles, each demand is transported independently along a minimum-cost path in the resulting graph:

• vertices: islands 0..L
• always-available edges: (k-1, k) with cost 1
• hired shuttle edges: (l_i, r_i) with cost equal to that resident's operating cost

The total daily cost is:

• sum of setup costs of all hired residents
• plus, for each demand, W_j × (shortest path cost between A_j and B_j)

Your task is to output any feasible relay design. Better designs get better scores.

Input

The input is given in the following format:

L N M
S
X_1 C_1 H_1 D_1
X_2 C_2 H_2 D_2
...
X_N C_N H_N D_N
A_1 B_1 W_1
A_2 B_2 W_2
...
A_M B_M W_M

• S is a string of length L
• S_k is A or J, representing the owner of the route between islands k-1 and k

Output

Output exactly N lines.

For each resident i, output one of the following:

• -1
  meaning resident i is not hired

• l_i r_i
  meaning resident i is hired to operate a shuttle between islands l_i and r_i

Feasibility requirements

If resident i is hired, the following must hold:

• 0 <= l_i < r_i <= L
• r_i - l_i <= D_i

If any line is malformed or any hired resident violates these conditions, the output is infeasible.

Objective

Minimize the total daily cost:

TotalCost =
(sum of setup costs of hired residents)
+ (sum over demands of W_j × shortest_path_cost(A_j, B_j))

Definitions

For resident i, let:

• bad_i(u, v) = number of route indices k on the path between islands u and v such that S_k != C_i

Then for a hired shuttle (l_i, r_i):

• setup cost = H_i + min(bad_i(X_i, l_i), bad_i(X_i, r_i))
• shuttle edge cost = bad_i(l_i, r_i)

The shortest path for each demand is computed in the graph consisting of:

• adjacent-island edges (k-1, k) of cost 1
• all hired shuttle edges, bidirectional, with their shuttle edge costs

Scoring

This is an optimization problem. Lower TotalCost is better.

For each test file:

• Let B be the baseline cost obtained by hiring nobody.
  Then all shipments use only adjacent-island routes, so

B = sum over demands of W_j × |A_j - B_j|

• Let U be your output's TotalCost.

If your output is infeasible, the score for that test file is 0.

Otherwise, the score is:

Score = floor(10^9 × min(5, B / U))

• The baseline solution always scores exactly 10^9.
• Better-than-baseline solutions score more than 10^9.
• Scores are capped at 5 × 10^9 per test file.

The final score is the sum of scores over all test files.

Constraints

• 1 <= L <= 5000
• 1 <= N <= 5000
• 1 <= M <= 20000
• S_k is A or J
• 0 <= X_i <= L
• C_i is A or J
• 0 <= H_i <= 10^9
• 1 <= D_i <= L
• 0 <= A_j, B_j <= L
• A_j != B_j
• 1 <= W_j <= 10^6

Constraints

• Time limit: 5 seconds
• Memory limit: 1024 MB

Example

Sample Input

6 3 3
AAJJAJ
0 A 1 3
6 J 1 3
3 A 4 6
0 6 10
1 5 4
2 4 5

Sample Output

0 3
3 6
-1

Explanation

• Resident 1 operates shuttle (0, 3).

  • Path owner string: AAJ
  • With coupon A, the shuttle edge cost is 1
  • Setup cost is 1 + min(0, 1) = 1

• Resident 2 operates shuttle (3, 6).

  • Path owner string: JAJ
  • With coupon J, the shuttle edge cost is 1
  • Setup cost is 1 + min(1, 0) = 1

• Resident 3 is not hired.

So the fixed setup cost is 2.

The resulting graph has:

• normal edges of cost 1 between consecutive islands
• shuttle edges (0,3) and (3,6), each of cost 1

Demand costs:

• 0 -> 6, volume 10: shortest path cost 2, contributes 20
• 1 -> 5, volume 4: shortest path cost 4, contributes 16
• 2 -> 4, volume 5: shortest path cost 2, contributes 10

Total cost:

2 + 20 + 16 + 10 = 48

Baseline cost:

10×6 + 4×4 + 5×2 = 86

Score for this test file:

floor(10^9 × 86 / 48) = 1791666666