<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

376. Berland All-Round Competitions
Time limit per test: 0.5 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



The Berland has a tradition of all-round competitions. The rules of those competitions are the following. The first stage is swimming some distance, then there are K stages of horse riding. There are N horses located at the start of each of the riding stages (N is the number of participatnts). For each horse, its ridingness Sj is known. The more the ridingness is, the faster the horse finishes the stage. For each participant, there are three parameters: swimming skill Wi, riding skill Ri and strength Pi. Participant who reaches the start of some riding stage (which is the finish of the previous stage) takes the horse with maximal ridingness from those who are still at the start of this stage. Each horse can participate only in one stage. If two participants reach the start of any stage simoultaneously, the one with the most strength takes the better horse. All participants have different strengths. Time required to complete the riding stage for i-th participant is equal to 2· 107 - Ri - Sj, for the swimming stage the time is 2 · 107 - Wi. After the start of the competition (i. e. the start of the swimming stage) there are no pauses and changing or taking the horse requires no time.

Petya knows all characteristics of participants. Also he knows that the jury picks horses in such a way that on i-th stage (1 ≤ i ≤ K) the ridingness of j-th horse (1 ≤ j≤ N) is equal to f(i, j) = 3Ai2 + 5Ai Bj + 2Bj2, where all Ai and Bj are also known.

Now Peter wants to know the order of the participants on the finish line. Help him.

Input
The first line of the input contains two integers N and K (1≤ N≤ 103, 1≤ K≤ 103). N lines follow, containing three integers each: Wi, Ri and Pi (1 ≤ Wi, Ri, Pi ≤ 106). Then there are two lines: the first is for A, which contains K natural numbers not greater then 103, the second is for B, which contains N natural numbers not greater than 103.

Output
Output the space-separated transposition of N numbers — the order of participants. If two participants reach the finish simultaneously, they use armwrestling to determine the winner, and the participant with higher strength takes the better place.

Example(s)
sample input
sample output
4 2
2 5 3
3 1 4
3 4 1
2 2 2
2 3
4 5 6 7
2 3 1 4

<|response|>
## 1) Abridged problem statement (concise)

There are **N** participants and a competition consisting of:

- 1 swimming stage  
  `Tswim(i) = 2·10^7 − Wi`
- then **K** horse-riding stages. On each stage there are **N horses** available at that stage start; **each horse can be used only once** on that stage (i.e., each participant gets exactly one horse per stage).

Participant `i` has:
- swimming skill `Wi`
- riding skill `Ri`
- strength `Pi` (all strengths are distinct)

At the start of each riding stage:
- Participants arrive at different times (or possibly equal).
- The earliest arrival chooses first; if several arrive simultaneously, higher strength chooses first.
- Each chooser takes the **best remaining horse** (maximum ridingness `Sj`).

Riding time if participant `i` rides horse with value `Sj`:
`Tride(i) = 2·10^7 − Ri − Sj`

Horse values depend on the stage `s` and index `j`:
`Sj = f(s, j) = 3·A_s^2 + 5·A_s·B_j + 2·B_j^2`

Given arrays `A` (length `K`) and `B` (length `N`), output the **final ranking** (participant IDs 1..N) by total time ascending; ties on total time are broken by higher strength.

Constraints: `N, K ≤ 1000`.

---

## 2) Key observations

1. **Horse assignment on a stage is purely rank-based.**  
   If you sort participants by:
   - arrival time ascending
   - strength descending (tie-break)
   
   then the 1st participant gets the best horse, 2nd gets the 2nd best, etc.

2. **For each stage, horses can be precomputed and sorted once.**  
   For a fixed stage `s`, compute all `N` values `f(s, j)` and sort them in descending order.

3. **We can simulate stage-by-stage using only “arrival times”.**  
   Let `arrival[i]` be the time when participant `i` reaches the start of the current stage.
   - Initially: `arrival[i] = 2·10^7 − Wi` (after swimming).
   - After assigning a horse of value `H` on a stage:
     `arrival[i] += (2·10^7 − Ri) − H`

4. Complexity is fine:  
   Each stage needs:
   - sort participants: `O(N log N)`
   - sort horses: `O(N log N)` (or precompute per stage)
   
   Total: `O(K N log N)` for `N, K ≤ 1000`.

---

## 3) Full solution approach

1. **Read input** and store for each participant:
   - `swim_time = 2e7 - Wi`
   - `ride_base = 2e7 - Ri` (later subtract horse value)
   - `strength = Pi`
   - `id` (1-based)

2. **Precompute horses for each stage**:
   For every stage `s = 0..K-1`:
   - compute `horse[j] = 3*A[s]^2 + 5*A[s]*B[j] + 2*B[j]^2` for `j=0..N-1`
   - sort `horse` descending
   Store as `stage_horses[s]`.

3. **Initialize arrival times** after swimming:
   `arrival[i] = swim_time[i]`

4. **Simulate each riding stage** `s = 0..K-1`:
   - Create an array `order = [0..N-1]`
   - Sort `order` by `(arrival[i], -strength[i])`
   - For each position `pos` in `0..N-1`:
     - participant index `p = order[pos]`
     - horse value `H = stage_horses[s][pos]` (pos-th best horse)
     - ride time on this stage: `ride_base[p] - H`
     - new arrival: `arrival[p] + (ride_base[p] - H)`
   - Replace `arrival` with the new values.

5. **Final ranking**:
   - Sort participants by `(arrival[i], -strength[i])` (arrival now equals total time)
   - Output their 1-based IDs.

---

## 4) C++ implementation (detailed comments)

```cpp
#include <bits/stdc++.h>
using namespace std;

struct Participant {
    int id;                 // 1-based id
    long long swim_time;    // 2e7 - Wi
    long long ride_base;    // 2e7 - Ri (horse value will be subtracted)
    long long strength;     // Pi (all distinct)
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    cin >> N >> K;

    vector<Participant> p(N);
    for (int i = 0; i < N; i++) {
        long long W, R, P;
        cin >> W >> R >> P;
        p[i].id = i + 1;
        p[i].swim_time = 20000000LL - W;
        p[i].ride_base = 20000000LL - R;
        p[i].strength  = P;
    }

    vector<long long> A(K), B(N);
    for (int i = 0; i < K; i++) cin >> A[i];
    for (int j = 0; j < N; j++) cin >> B[j];

    // Precompute and sort horses for each stage:
    // stage_horses[s][pos] = pos-th best horse value at stage s
    vector<vector<long long>> stage_horses(K, vector<long long>(N));
    for (int s = 0; s < K; s++) {
        long long a = A[s];
        for (int j = 0; j < N; j++) {
            long long b = B[j];
            stage_horses[s][j] = 3*a*a + 5*a*b + 2*b*b;
        }
        sort(stage_horses[s].begin(), stage_horses[s].end(), greater<long long>());
    }

    // arrival[i] = time participant i reaches the current stage start
    vector<long long> arrival(N);
    for (int i = 0; i < N; i++) arrival[i] = p[i].swim_time;

    // Simulate K riding stages
    for (int s = 0; s < K; s++) {
        vector<int> order(N);
        iota(order.begin(), order.end(), 0);

        // Order of choosing horses: earlier arrival first; if tie, stronger first
        sort(order.begin(), order.end(), [&](int x, int y) {
            if (arrival[x] != arrival[y]) return arrival[x] < arrival[y];
            return p[x].strength > p[y].strength;
        });

        vector<long long> new_arrival(N);

        // Assign horses in sorted order: best horse to first chooser, etc.
        for (int pos = 0; pos < N; pos++) {
            int idx = order[pos];
            long long horse = stage_horses[s][pos];

            // riding time = (2e7 - Ri) - horse_value
            long long ride_time = p[idx].ride_base - horse;

            // finish time (arrival for next stage)
            new_arrival[idx] = arrival[idx] + ride_time;
        }

        arrival.swap(new_arrival);
    }

    // Final ranking by total time (arrival after last stage), tie by strength
    vector<int> fin(N);
    iota(fin.begin(), fin.end(), 0);
    sort(fin.begin(), fin.end(), [&](int x, int y) {
        if (arrival[x] != arrival[y]) return arrival[x] < arrival[y];
        return p[x].strength > p[y].strength;
    });

    for (int i = 0; i < N; i++) {
        if (i) cout << ' ';
        cout << p[fin[i]].id;
    }
    cout << "\n";
    return 0;
}
```

---

## 5) Python implementation (detailed comments)

```python
import sys

def solve() -> None:
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)

    n = next(it)
    k = next(it)

    # Participant arrays (parallel arrays are fast in Python)
    swim = [0] * n        # 2e7 - Wi
    ride_base = [0] * n   # 2e7 - Ri
    strength = [0] * n    # Pi

    for i in range(n):
        w = next(it); r = next(it); p = next(it)
        swim[i] = 20_000_000 - w
        ride_base[i] = 20_000_000 - r
        strength[i] = p

    A = [next(it) for _ in range(k)]
    B = [next(it) for _ in range(n)]

    # Precompute horses for each stage, sorted descending
    stage_horses = []
    for s in range(k):
        a = A[s]
        horses = [3*a*a + 5*a*b + 2*b*b for b in B]
        horses.sort(reverse=True)
        stage_horses.append(horses)

    # arrival time at current stage start
    arrival = swim[:]  # after swimming, they arrive at stage 1

    # Simulate each riding stage
    for s in range(k):
        # Sort participants by arrival asc, strength desc
        order = list(range(n))
        order.sort(key=lambda i: (arrival[i], -strength[i]))

        horses = stage_horses[s]
        new_arrival = [0] * n

        # pos-th participant gets pos-th best horse
        for pos, i in enumerate(order):
            horse = horses[pos]
            ride_time = ride_base[i] - horse
            new_arrival[i] = arrival[i] + ride_time

        arrival = new_arrival

    # Final ranking by total time asc, then strength desc
    fin = list(range(n))
    fin.sort(key=lambda i: (arrival[i], -strength[i]))

    # Output 1-based ids
    ans = [str(i + 1) for i in fin]
    sys.stdout.write(" ".join(ans))

if __name__ == "__main__":
    solve()
```

