# 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:

```text
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:

```text
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

```text
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:

```text
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
```text
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
```text
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:
```text
2 + 20 + 16 + 10 = 48
```

Baseline cost:
```text
10×6 + 4×4 + 5×2 = 86
```

Score for this test file:
```text
floor(10^9 × 86 / 48) = 1791666666
```
