Background

This is an output-only problem.

Link: https://pan.baidu.com/s/1D3ytb0626EKZ_emw3gLwVQ
Extraction code: inbj

Problem Description

Dream SMP can be seen as $n$ regions numbered $0,1,\dots,n-1$.

Dream wants to divide these $n$ regions into $8$ countries numbered $0,1,\dots,7$. Each region belongs to exactly one country, but a country may contain no regions.

The regions give $m$ sets of constraints on the partition plan. The $i$-th constraint is represented by four parameters $(u_i,a_i,v_i,b_i)$. A partition plan is valid if and only if for every constraint, region $u_i$ does not belong to country $a_i$ or region $v_i$ does not belong to country $b_i$. Here or is logical OR.

Dream guarantees that there is at least one valid partition plan. You need to construct a valid partition plan.

Input Format

The first line contains two positive integers $n$ and $m$.
The next $m$ lines each contain four positive integers $u_i,a_i,v_i,b_i$.

Output Format

Output a string of length $n$.
The $i$-th character of the string is the country that region $i$ belongs to.

5 600
0 5 1 4
2 3 2 2
0 4 0 4
1 7 4 7
4 6 1 3
4 2 2 4
2 3 0 7
0 3 2 1
4 4 2 1
2 3 0 6
4 5 0 3
1 2 4 6
2 0 1 4
1 6 2 3
2 2 0 6
4 3 1 7
3 6 2 5
3 0 2 6
3 7 1 7
1 2 2 2
1 7 3 7
2 6 4 2
3 0 2 3
1 1 2 0
2 1 2 3
0 5 3 3
4 0 1 1
0 5 3 7
2 6 0 4
3 1 4 3
1 1 2 5
3 6 0 2
0 4 3 1
1 7 2 4
3 4 3 3
1 0 3 7
3 5 0 2
0 4 0 1
3 0 3 6
4 2 0 5
3 3 1 7
1 5 2 3
4 5 0 0
3 0 1 5
1 5 0 3
2 0 2 1
2 6 3 6
2 4 3 2
1 2 2 5
2 1 0 5
1 2 4 1
2 7 4 6
0 5 0 6
3 6 2 2
1 7 1 7
0 1 4 4
1 6 0 2
1 6 1 0
1 4 0 7
0 7 4 5
0 4 2 1
3 7 0 7
3 0 2 1
3 3 3 6
0 2 1 0
0 6 2 2
4 1 2 0
2 7 1 6
1 0 2 1
4 3 3 0
0 7 3 5
1 3 3 5
3 0 4 0
4 6 1 4
2 3 2 7
1 0 3 2
0 3 3 7
0 2 1 2
3 1 0 6
0 1 2 7
3 4 3 0
4 7 3 6
2 5 4 3
3 4 0 7
2 0 0 2
1 4 1 6
0 7 0 3
2 4 2 4
2 2 2 1
4 2 0 4
2 7 3 4
4 6 0 6
2 4 0 4
2 2 1 1
4 7 0 1
4 0 1 0
1 1 1 1
3 4 2 4
0 4 1 0
0 0 0 3
3 3 2 5
1 0 4 0
3 3 2 1
3 7 4 6
0 1 1 2
3 4 0 3
1 1 2 7
2 7 1 7
1 5 4 4
4 4 3 0
2 2 0 3
0 1 0 6
1 2 2 0
0 4 0 5
3 0 0 2
3 6 2 7
1 4 2 1
1 6 3 7
3 1 2 5
2 0 1 3
1 6 3 6
2 1 0 4
4 5 3 5
4 4 3 2
2 5 2 1
3 6 1 0
4 4 0 3
2 0 0 7
2 4 1 4
3 4 2 0
3 6 0 7
0 5 1 5
0 3 0 1
1 2 3 0
0 1 2 4
4 5 2 7
1 5 4 0
0 4 2 3
0 7 3 1
2 5 0 1
3 1 2 3
2 6 2 5
2 1 3 2
3 1 2 6
0 2 4 5
2 7 4 1
0 0 4 7
1 6 1 7
4 4 3 7
1 5 3 7
2 3 0 5
3 0 1 4
3 0 4 6
2 5 4 2
2 7 2 3
0 1 2 6
1 7 0 2
1 1 4 6
3 0 0 4
2 5 3 0
4 6 0 0
2 4 2 3
0 3 4 1
4 5 4 5
1 5 4 3
0 5 4 1
0 3 0 4
4 5 3 0
3 2 1 4
2 6 2 2
0 6 3 6
4 2 1 0
2 1 2 0
3 4 4 7
2 1 2 1
0 5 2 4
2 7 4 3
4 7 1 6
3 6 0 3
0 1 3 4
2 6 2 4
2 2 2 3
4 5 1 5
1 4 0 6
2 6 4 1
2 0 2 7
4 5 2 4
2 7 4 4
3 7 3 2
2 5 1 2
0 2 4 1
4 7 3 4
0 1 1 3
4 1 1 6
1 1 1 4
2 7 1 2
1 4 0 0
2 0 4 2
0 3 2 7
2 5 2 6
0 5 4 4
4 0 2 3
2 4 0 3
4 5 2 1
4 4 4 0
2 5 3 6
3 1 4 5
1 6 4 7
0 2 3 4
0 1 4 7
1 5 3 4
0 6 1 0
2 7 2 2
0 4 2 4
4 2 2 7
4 5 2 3
0 3 1 1
0 3 4 0
0 4 2 7
0 3 2 0
3 0 1 7
0 1 1 1
3 4 0 4
2 3 1 6
4 4 0 2
4 2 2 5
4 4 4 5
1 1 2 4
1 1 0 1
0 7 2 5
0 5 1 3
3 2 4 6
4 0 0 4
3 1 3 2
2 3 1 2
0 1 1 5
4 5 3 7
2 0 3 3
0 2 0 3
1 5 3 1
1 4 2 4
1 5 1 1
1 0 1 4
0 7 2 1
0 5 0 2
3 4 1 3
1 7 3 0
3 3 4 5
3 5 4 2
3 4 3 6
3 4 3 7
3 4 3 4
1 7 2 3
4 4 4 2
1 7 4 4
1 3 1 6
4 3 4 2
1 5 2 1
1 5 2 2
2 5 4 5
1 5 2 4
3 6 0 5
3 2 0 6
4 4 1 4
4 0 4 0
0 4 4 3
2 4 3 5
4 1 3 6
2 4 4 3
4 3 2 0
3 5 3 1
1 7 0 6
0 2 4 7
3 0 0 3
1 4 0 2
4 5 1 7
3 1 0 4
0 1 0 2
4 1 1 3
0 3 3 3
2 2 4 2
4 3 4 1
4 5 2 0
1 6 2 6
1 1 2 1
4 6 2 2
1 7 2 0
0 4 3 0
0 3 2 5
2 2 3 0
3 6 2 3
0 7 3 3
0 5 0 4
3 7 1 5
4 5 0 5
4 1 0 4
1 7 0 7
3 4 1 7
0 0 2 5
1 3 3 0
2 1 3 0
2 6 0 3
0 5 1 7
0 6 1 6
1 1 0 5
2 7 2 5
0 3 4 5
4 0 3 1
3 2 1 0
2 6 0 2
1 4 3 7
1 6 2 5
1 4 4 4
3 5 4 4
1 1 4 3
2 1 1 3
4 2 1 7
4 6 1 0
1 0 3 4
1 1 3 1
1 6 0 6
3 7 1 1
0 0 2 4
4 0 1 5
0 2 2 2
2 0 1 5
1 0 4 5
3 0 1 2
0 1 0 1
0 3 0 2
4 7 3 2
4 4 3 3
1 5 4 7
2 2 0 2
2 4 0 7
4 1 1 4
4 5 4 2
4 4 1 1
1 7 1 2
3 2 3 5
3 6 1 7
4 1 2 2
1 1 3 5
3 1 2 4
3 1 4 0
4 6 0 5
1 5 3 5
3 1 2 1
3 0 3 4
4 4 4 4
1 5 1 0
4 0 4 3
1 4 3 3
4 7 4 0
4 5 4 1
1 5 3 2
0 6 0 1
0 6 3 7
1 3 1 4
4 0 1 4
2 1 3 3
4 1 2 6
1 0 1 3
4 7 0 4
0 0 0 0
2 5 1 0
2 3 0 0
1 6 1 2
0 2 0 5
3 7 4 5
2 3 1 4
2 3 3 1
0 2 3 1
4 7 3 0
4 5 4 0
3 3 4 7
3 4 0 2
2 7 4 2
3 0 4 7
3 0 0 0
0 4 4 7
1 4 3 5
1 1 4 2
2 3 1 0
1 0 0 2
1 1 1 0
3 5 4 3
0 6 4 3
4 4 0 5
4 4 1 0
4 3 1 2
2 4 4 0
0 5 4 0
0 0 4 1
4 2 3 7
4 5 2 5
3 7 1 4
2 1 0 6
3 1 0 5
1 3 2 7
1 3 4 7
1 4 2 5
4 4 1 7
1 1 4 0
0 5 4 2
3 3 1 6
3 1 0 3
1 3 4 1
1 2 3 1
2 1 3 5
0 0 1 7
3 4 2 2
3 6 1 5
2 7 2 7
3 5 1 5
0 4 0 6
3 2 4 7
0 6 1 4
1 0 0 7
3 1 2 0
2 3 4 0
3 1 0 1
3 3 2 0
3 5 4 0
4 7 0 2
1 2 1 0
1 6 2 0
4 2 1 1
0 0 1 1
1 0 1 1
3 7 3 6
2 4 0 1
1 2 2 7
4 3 4 5
4 2 4 6
3 7 3 7
0 7 3 7
4 5 3 3
2 6 1 5
0 3 0 6
4 7 4 7
4 0 4 5
3 4 1 5
0 2 0 7
4 1 3 5
0 5 3 0
0 5 4 5
1 0 2 6
0 4 2 5
1 3 0 3
1 5 0 2
0 0 4 5
3 3 0 5
3 2 3 1
4 1 1 0
2 4 4 1
0 6 4 1
1 1 2 3
4 6 4 3
0 5 0 0
0 4 0 2
2 3 0 4
4 7 1 5
1 6 0 5
1 7 4 2
0 2 0 4
3 5 3 0
4 6 4 1
4 6 3 1
0 0 1 6
4 2 1 6
3 1 1 4
4 7 1 3
1 6 4 0
2 5 2 3
0 2 2 1
3 7 2 0
1 0 4 7
3 5 3 4
0 0 4 6
1 7 1 1
3 5 4 5
3 3 3 7
2 2 2 7
4 2 4 3
3 6 4 0
3 5 3 6
4 6 1 5
2 7 0 3
3 3 4 4
4 2 3 4
3 1 1 3
2 0 4 0
2 3 2 1
1 7 4 0
2 3 2 4
0 4 1 2
1 7 1 4
2 6 3 4
1 3 2 4
1 4 2 3
1 4 1 2
2 0 2 5
0 7 1 0
2 7 0 1
4 1 3 0
4 1 1 5
3 1 3 6
4 4 2 3
3 0 0 1
2 4 4 5
3 1 1 2
4 3 1 6
4 0 3 5
2 4 1 0
1 3 4 4
1 1 1 2
2 6 4 0
0 6 4 4
1 0 4 4
0 4 3 4
4 5 1 2
1 1 4 7
3 2 2 5
4 7 1 2
3 7 0 0
4 4 4 1
2 7 1 3
1 0 0 1
2 1 4 7
2 0 0 5
4 6 2 3
2 5 0 7
1 6 3 3
2 6 1 7
0 1 2 1
0 7 0 0
2 1 0 3
3 0 3 5
4 3 0 4
4 3 3 7
2 6 2 1
2 4 1 1
2 3 4 5
4 3 0 1
2 2 0 4
3 0 1 3
1 2 1 3
1 7 0 3
3 3 0 0
0 6 0 7
3 1 3 0
3 6 2 6
1 1 1 3
0 5 2 7
0 0 2 3
4 0 2 0
0 1 1 4
0 4 1 6
2 2 2 4
2 0 3 6
0 5 1 0
4 1 1 1
3 6 3 4
4 3 3 2
2 3 2 5
3 1 2 2
4 0 3 0
1 3 0 4
0 7 1 6
0 1 1 0
2 6 1 0
4 2 4 7
0 0 4 0
2 5 0 6
3 5 2 7
3 2 3 6
0 0 3 5
1 2 0 2
1 0 4 6
1 4 4 0
3 4 1 0
0 5 2 1
1 3 2 1
4 7 0 6
4 3 1 1
0 6 1 1
2 2 3 1
2 2 1 0
0 2 3 7
2 0 2 4
4 4 4 6
3 4 2 6
1 0 0 5
4 0 1 3
3 4 1 2
2 1 2 4
1 3 3 7
2 1 1 1
0 0 2 6

23333

Hint

Sample 1 Explanation

23322, 23332, and 23333 are all valid plans.

Constraints

For $100\%$ of the data, $1 \le n \le 10^5$, $1 \le m \le 10^6$.
For specific properties, please refer to the input testdata yourself.

Click here to download the input data.

If the download link above does not work, see this one below:

Link: https://pan.baidu.com/s/1D3ytb0626EKZ_emw3gLwVQ
Extraction code: inbj

Notes

Minecraft OI Round 4 Extra
Idea & solution: w33z8kqrqk8zzzx33. Check: tiger2005.

Translated by ChatGPT 5