<|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.

171. Sarov zones
time limit per test: 0.25 sec.
memory limit per test: 4096 KB
input: standard
output: standard



It is known that to participate the All-Russian Mathematic Olympiad one should do one of other olympiads enough good. These olympiads are called "zone olympiads" and the region from which people participate the same zone olympiad is called "zone". Sarov city of Nizhny Novgorod district is situated near the boundary of zones, so every year school students of Sarov participate several zones.

This year K zones invited students from Sarov to participate their olympiads. i-th zone invited N[i] students, so N=N[1]+N[2]+...+N[K] totally students were invited. After the Sarov city olympiad, N students were selected, so now the olympiad authorities of Sarov have to decide, which students will participate which zone olympiad. Each student is characterized by his olympiad level and each zone is characterized by its zone level. If a student with olympiad level P participates zone with zone level Q, he will be invited to All-Russian olympiad if and only if P>Q.

Every student is also characterized by his "weight". The Sarov olympiad authorities want, that the All-Russian Olympiad will be participated by students with maximal summary weight. You are to help them. Write a program which will divide the students between zones. Keep in mind that exactly N[i] students can go to i-th zone.

Input
On the first line of input there is an only integer K (1<=K<=100). On the second line there are K integers N[1], N[2], ... ,N[K] (0<=N[i]<=16000). On the third line there are K more integers Q[1], Q[2], ... ,Q[K] --- the zone levels of the zones. On the fourth line there are N integers P[1], P[2], ... P[N] --- olympiad levels of the students. (0<=Q[i]<=1000000, 0<=P[i]<=1000000). On the last (and fifth) line there are N integers w[1], w[2], ... w[k] --- the "weights" of students. 0<=w[i]<=100000. It is also guaranteed that 0<=N<=16000.

Output
Output only N integers --- Z[1], Z[2], ... Z[N] --- the numbers of zones which should be participated by students 1, 2, ... N.

Sample test(s)

Input
2
1 1
4 1
2 3
2 1

Output
2 1
Author:	NNSU #2 team
Resource:	
Date:

<|response|>
1. Abridged problem statement  
We have K zones, each zone i with capacity C[i] and quality Q[i]. There are N = Σ C[i] students, and each student j has skill P[j] and weight w[j]. We must assign each student to exactly one zone (respecting the capacities) to maximize the total weight of those students who satisfy P[j] > Q[zone assigned to j]. Output for each student the index of the zone they go to.

2. Key observations  
- Assigning a student j to zone i gives us profit w[j] if P[j] > Q[i], otherwise 0.  
- We want high-weight students to occupy “slots” in zones whose quality they can beat.  
- This is analogous to the classic “jobs with deadlines and profits” greedy: schedule highest-profit jobs as late as possible before their deadline.  
- For each student, think of the “latest possible” zone slot in ascending order of Q that the student can beat.  
- Greedily process students in descending order of weight, trying to place each into the highest-quality zone it still qualifies for and that has a free seat.  
- Students who cannot be profitably placed (or run out of qualifying seats) get assigned later to any leftover slot (they contribute zero).

3. Full solution approach  
a. Read K, the array of capacities C[1..K], the array of qualities Q[1..K], then N = ΣC[i], and students’ arrays P[1..N], w[1..N].  
b. Build a list of zones as tuples (Q, capacity, original_index). Sort it by Q ascending.  
c. Build a list of students as tuples (w, P, original_index). Sort by w descending.  
d. Prepare an answer array ans[1..N], initialized to –1.  
e. For each student in descending weight order:  
   i.   Binary-search on the sorted zones to find the last zone whose quality < P.  
   ii.  From that zone index, scan backwards until you find one with capacity > 0 (if any).  
   iii. If found, assign the student to that zone: record ans[student_id] = zone_original_index + 1, decrement capacity.  
f. After the loop, some students still have ans = –1. Fill them one by one into any zone with leftover capacity (scan zones from low Q to high or vice versa).  
g. Print ans in order of student 1 to N.  

Time complexity: sorting O(N log N + K log K), each of N students does an O(log K + K) search in the worst case → O(N·K), acceptable for N≤16 000, K≤100.

4. C++ implementation

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

struct Zone {
    int q, cap, id;
};

struct Student {
    int p, w, id;
};

int k;
int64_t total_n;
vector<Zone> zones;
vector<Student> students;

void read() {
    cin >> k;
    zones.resize(k);
    total_n = 0;
    for(int i = 0; i < k; i++) {
        cin >> zones[i].cap;
        total_n += zones[i].cap;
    }

    for(int i = 0; i < k; i++) {
        cin >> zones[i].q;
        zones[i].id = i;
    }

    students.resize(total_n);
    for(int i = 0; i < total_n; i++) {
        cin >> students[i].p;
    }

    for(int i = 0; i < total_n; i++) {
        cin >> students[i].w;
        students[i].id = i;
    }
}

void solve() {
    // A student qualifies for the All-Russian olympiad iff his level p exceeds
    // his zone's level q. To maximise total qualifying weight we greedily
    // process students by decreasing weight; sort zones by increasing level
    // and place each student into the highest-level zone that still has free
    // capacity and that he can beat (q < p). This keeps low-level zones free
    // for weaker students who can only qualify there. Any students left
    // unassigned are poured into whatever capacity remains, in zone order.

    sort(students.begin(), students.end(), [&](auto& a, auto& b) {
        return a.w > b.w;
    });

    sort(zones.begin(), zones.end(), [&](auto& a, auto& b) {
        return a.q < b.q;
    });

    vector<int> answer(total_n, -1);

    for(auto& st: students) {
        int best_zone = -1;
        for(int j = k - 1; j >= 0; j--) {
            if(zones[j].q < st.p && zones[j].cap > 0) {
                best_zone = j;
                break;
            }
        }

        if(best_zone != -1) {
            answer[st.id] = zones[best_zone].id + 1;
            zones[best_zone].cap--;
        }
    }

    int zi = 0;
    for(int i = 0; i < total_n; i++) {
        if(answer[i] == -1) {
            while(zi < k && zones[zi].cap == 0) {
                zi++;
            }

            answer[i] = zones[zi].id + 1;
            zones[zi].cap--;
        }
    }

    for(int i = 0; i < total_n; i++) {
        cout << answer[i] << (i + 1 < total_n ? ' ' : '\n');
    }
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python implementation with detailed comments  

```python
import sys

def main():
    data = list(map(int, sys.stdin.read().split()))
    it = iter(data)
    K = next(it)

    # Read capacities and total students
    caps = [next(it) for _ in range(K)]
    totalN = sum(caps)

    # Read zone qualities
    quals = [next(it) for _ in range(K)]

    # Read student skills and weights
    skills = [next(it) for _ in range(totalN)]
    weights = [next(it) for _ in range(totalN)]

    # Build zone list and sort by quality ascending
    zones = []
    for i in range(K):
        zones.append([quals[i], caps[i], i])  # [quality, remaining cap, original idx]
    zones.sort(key=lambda z: z[0])

    # Build student list and sort by weight descending
    students = []
    for j in range(totalN):
        students.append([weights[j], skills[j], j])  # [weight, skill, original idx]
    students.sort(key=lambda s: -s[0])

    # Prepare answer array
    ans = [-1] * totalN

    # Greedy: assign heavy students first
    for w, p, sid in students:
        # binary search for the last zone quality < p
        lo, hi, pos = 0, K-1, -1
        while lo <= hi:
            mid = (lo + hi) // 2
            if zones[mid][0] < p:
                pos = mid
                lo = mid + 1
            else:
                hi = mid - 1
        # scan backward from pos to find a zone with free cap
        z = pos
        while z >= 0:
            if zones[z][1] > 0:
                ans[sid] = zones[z][2] + 1  # 1-based zone index
                zones[z][1] -= 1
                break
            z -= 1
        # if none found, ans[sid] remains -1

    # Fill remaining students arbitrarily
    zi = 0
    for sid in range(totalN):
        if ans[sid] == -1:
            # find next zone with cap > 0
            while zones[zi][1] == 0:
                zi += 1
            ans[sid] = zones[zi][2] + 1
            zones[zi][1] -= 1

    # Print the assignment
    print(" ".join(map(str, ans)))

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

Explanation of the greedy choice: by assigning the heaviest student to the “deepest” zone they can beat, we preserve earlier (lower-quality) seats for other students who might not qualify for the very best zones, thus maximizing total collected weight.