Resonant Bay Layout

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

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

Resonant Bay Layout

Problem

A research lab wants to place n oscillators on a long straight rail with numbered bays 0, 1, ..., m-1.

Oscillator i has an intrinsic phase ratio p_i / q_i. Some pairs of oscillators are connected by coupling channels. If oscillators u and v are placed d = |x_u - x_v| bays apart, then channel (u, v) produces energy

[ E_{u,v}(d)

w_{u,v} \cdot \left|\sin\left(\pi \frac{p_u}{q_u} d\right)\right| \cdot \left|\sin\left(\pi \frac{p_v}{q_v} d\right)\right|. ]

You must assign every oscillator to a distinct integer bay. Your goal is to maximize the total produced energy over all channels.

This is an optimization challenge: any feasible output is accepted, and better layouts receive better scores.

Input

The first line contains an integer t — the number of test cases.

For each test case:

• The first line contains three integers n, m, and r:
  • n — number of oscillators
  • m — number of bays
  • r — number of coupling channels
• The next n lines each contain two integers p_i and q_i.
• The next r lines each contain three integers u, v, and w describing a channel between oscillators u and v with weight w.

Oscillators are numbered from 1 to n.

There are no self-loops and no repeated channels.

Output

For each test case, output one line containing n integers:

[ x_1, x_2, \dots, x_n ]

where x_i is the bay chosen for oscillator i.

A solution is feasible for a test case if and only if:

• 0 <= x_i < m for all i
• all x_i are pairwise distinct

If a test case output is infeasible, its objective value is defined as 0.

Objective

For a feasible layout, let

[ d_{u,v} = |x_u - x_v|. ]

The total energy is

[ F

\sum_{(u,v)\in \text{channels}} w_{u,v} \cdot \left|\sin\left(\pi \frac{p_u}{q_u} d_{u,v}\right)\right| \cdot \left|\sin\left(\pi \frac{p_v}{q_v} d_{u,v}\right)\right|. ]

You must maximize F.

Judge computation details

For each factor, the judge may reduce the angle using periodicity before evaluating sine:

[ \sin\left(\pi \frac{p_i}{q_i} d\right)

\sin\left(\pi \frac{(p_i d \bmod 2q_i)}{q_i}\right). ]

This is mathematically equivalent and avoids large angles.

Scoring

For each test case, a deterministic baseline layout is defined as follows:

1. Compute the weighted degree of each oscillator: [ \deg(i) = \sum_{(i,j)\in \text{channels}} w_{i,j}. ]
2. Sort oscillators by decreasing deg(i), breaking ties by smaller index.
3. Define baseline bays:
   • if n = 1, the only bay is 0
   • otherwise, for k = 0, 1, ..., n-1: [ b_k = \left\lfloor \frac{k(m-1)}{n-1} \right\rfloor ]
4. Assign the k-th oscillator in the sorted order to bay b_k.

Let B be the objective value of this baseline layout, and let F be the objective value of your output.

The score for that test case is

[ S

10^6 \cdot \operatorname{clamp}\left( \frac{F+1}{B+1}, 0, 2 \right), ]

where

[ \operatorname{clamp}(x,0,2)= \begin{cases} 0 & x<0\ x & 0\le x\le 2\ 2 & x>2 \end{cases} ]

The score of an input file is the arithmetic mean of its test case scores.

Higher is better.

Constraints

• 1 <= t <= 20
• 2 <= n <= 400
• n <= m <= 10^9
• 1 <= r <= min(30000, n(n-1)/2)
• 1 <= p_i, q_i <= 10^9
• 1 <= w <= 10^6

Across one input file:

• sum(n) <= 4000

• sum(r) <= 120000

• Time limit: 8 seconds

• Memory limit: 512 MB

Example

Input

1
4 7 4
1 2
1 3
2 5
1 4
1 2 10
1 3 7
2 4 8
3 4 6

Output

0 3 5 1

Explanation

This places the 4 oscillators in distinct bays:

• oscillator 1 at bay 0
• oscillator 2 at bay 3
• oscillator 3 at bay 5
• oscillator 4 at bay 1

For each channel, the judge computes the bay distance, evaluates the two sine factors, multiplies by the channel weight, and sums the results.

The baseline layout is built from weighted-degree order and evenly spaced bays. Your score depends continuously on how your total energy compares to that baseline.