Truth or Lie: Classification of Island Tribes

After drifting for days, Akira Crusoe Maeda washes ashore on a foggy island. According to legend, the island is inhabited by two tribes: the divine tribe whose members always tell the truth and the devilish tribe whose members always lie. The legend also provides the exact populations of both tribes, which have been constant over millennia.

To avoid a cursed fate, Akira must classify the inhabitants based solely on a series of yes/no inquiries. In each inquiry, one inhabitant is asked whether another person is divine. Their reply adheres strictly to their nature:

• If the respondent is divine (truth-teller), they answer yes if the target is divine and no if the target is devilish.
• If the respondent is devilish (liar), they answer the opposite: no if the target is divine and yes if the target is devilish.

Formally, let \( x_i = 1 \) if the i-th inhabitant is divine and \( x_i = 0 \) if devilish. For an inquiry where inhabitant \( i \) is asked about inhabitant \( j \) and answers \( A \) (either yes or no), the condition is:

\[ \text{if } x_i=1:\quad A = \begin{cases} yes, & \text{if } x_j = 1\\ no, & \text{if } x_j = 0 \end{cases} \quad\text{; if } x_i=0:\quad A = \begin{cases} no, & \text{if } x_j = 1\\ yes, & \text{if } x_j = 0 \end{cases} \]

You are given the total number of inhabitants \( n \) and the number of divine tribe members \( D \) (with the remainder being devilish), together with \( m \) inquiries. Each inquiry is given in the format: an integer i, an integer j and a string answer (either yes or no). Inhabitants are numbered from 1 to \( n \).

Your task is to determine a valid classification (assignment of divine or devilish for each inhabitant) that satisfies all inquiries and the population constraint.

inputFormat

The input consists of multiple lines:

• The first line contains two integers: \( n \) (the total number of inhabitants) and \( D \) (the number of divine inhabitants).
• The second line contains an integer \( m \) representing the number of inquiries.
• The following \( m \) lines each contain an inquiry in the format: i j answer, where i and j are indices (1-indexed) and answer is either yes or no.

You may assume that a unique valid classification exists for the given input.

outputFormat

Output a single line containing \( n \) space-separated integers. The \( i \)-th integer should be 1 if the \( i \)-th inhabitant is divine, and 0 if devilish.

sample

3 2
2
1 2 yes
2 3 no

1 1 0