Hide

Problem K
Gravamen

“Next to the confrontation between two highly honed batteries of lawyers, jungle warfare is a stately minuet.” ­–Bill Veeck.

Frivolous lawsuit or legitimate litigation? That is the question the judge Kattis faces today as she presides over lawsuits between individuals and corporations.

There are $R$ individuals and $S$ corporations involved in lawsuits that Kattis must preside over today. For simplicity, we label the individuals $1, 2, \dots , R$ and the corporations $1, 2, \dots , S$. Each of the individuals and corporations is involved in at least one of the $L$ lawsuits; each lawsuit involves exactly one individual and one corporation, and in particular, the $i^\text {th}$ of these lawsuits involves the individual $A_ i$ and the corporation $B_ i$.

There has been a growing resentment among the populace that judges tend to be biased, and Kattis really wants to be known as an equitable and fair judge. For each lawsuit, she needs to rule in favor of one party or the other; the party she rules in favor of is said to have “won” the lawsuit. In an aggressive bid to improve her optics, she has decided to ignore the merits of the arguments involved (as the public is incapable of nuanced discussion anyway), but to rule in such a way that no single individual or corporation wins too many lawsuits, so as to avoid accusations of bias.

That is, she wants to make rulings with the goal of minimizing the maximum number of lawsuits any single individual or corporation wins.

What ruling should she make for each lawsuit?

Input

The first line of input contains three integers, $R$ ($1 \leq R \leq 2\, 000$), $S$ ($1 \leq S \leq 2\, 000$) and $L$ ($\max (R, S) \leq L \leq 2\, 000$) the number of individuals, the number of corporations and the number of lawsuits.

The next $L$ lines contain the descriptions of the lawsuits. In particular, the $i^\text {th}$ of these lines contains two integers $A_ i$ ($1 \leq A_ i \leq R$) and $B_ i$ ($1 \leq B_ i \leq S$), denoting that the $i^\text {th}$ lawsuit involves individual $A_ i$ and corporation $B_ i$.

It is guaranteed that each individual and corporation is involved in at least one lawsuit. Note that it is possible for the same pair of one individual and one corporation to be involved in more than one lawsuit.

Output

Output $L$ lines, where the $i^\text {th}$ of these lines contains either INDV $A_ i$ or CORP $B_ i$, describing the party Kattis should rule in favor of for the $i^\text {th}$ lawsuit, such that the maximum number of lawsuits any single individual or corporation wins is minimized.

If there are multiple correct answers, you can output any of them.

Sample Input 1 Sample Output 1
5 3 8
1 1
2 1
3 1
4 2
5 2
3 3
4 3
5 3
INDV 1
INDV 2
CORP 1
INDV 4
CORP 2
INDV 3
CORP 3
INDV 5
Sample Input 2 Sample Output 2
1 1 4
1 1
1 1
1 1
1 1
INDV 1
INDV 1
CORP 1
CORP 1

Please log in to submit a solution to this problem

Log in