Challenge Allocation for Robot Teams

You are given n teams and m challenges. In addition, there are k available robot models. Each team has an associated efficiency (which is provided but not used in the allocation). Each challenge is represented by a pair of teams that must both participate in solving it using the same robot model.

The goal is to assign a robot model (numbered from 1 to k) to each challenge such that for every team the difference between the maximum and minimum number of challenges solved using each robot model does not exceed 2. In other words, if for a given team the counts for the robot models are c₁, c₂, ..., c_k, then the following must hold:

$$\max_{1\le i \le k} c_i - \min_{1\le i \le k} c_i \le 2 $$

If no robot model can be assigned to a challenge without breaking the rule for either of the two teams involved, output 0 for that challenge. The challenges should be processed in the order they are given.

Note: The input is provided via standard input and the output should be printed to standard output.

inputFormat

The first line contains three integers n m k, representing the number of teams, the number of challenges, and the number of robot models respectively.

The second line contains n integers, representing the efficiencies of each team.

The following m lines each contain two integers a b (1-indexed) indicating that there is a challenge between team a and team b.

outputFormat

Output a single line with m space‐separated integers. The i-th integer is the robot model (in the range 1 to k) chosen for the i-th challenge, or 0 if no valid assignment exists.

## sample

5 8 3
5 3 8 2 6
1 3
1 2
3 4
2 5
4 5
1 5
3 2
2 4

1 1 1 1 1 2 2 1