Prism Phase Locks

Time limit: 4000 msMemory limit: 256 MB

A planetarium contains $N$ rotating prisms. Each prism points to a phase mark on a circular dial containing the marks $0,1,\ldots,C-1$ in clockwise order.

Prism $i$ has two mechanical locks. It must be placed at exactly one of the phases $A_i$ and $B_i$ . Let its selected phase be $P_i$ .

For two phase marks $x$ and $y$ , define their clockwise phase advance as

d_C(x,y)=(y-x)\bmod C,

where the result is the unique integer in the range $0$ through $C-1$ . In particular, $d_C(x,x)=0$ .

There are $M$ directed light channels. Channel $k$ starts at prism $U_k$ and ends at prism $V_k$ . It functions if and only if

L_k \le d_C(P_{U_k},P_{V_k}) \le R_k.

Choose one of the two locks for every prism so that all directed light channels function. If this is impossible, report that no valid selection exists.

Input

The first line contains three integers $N$ , $M$ , and $C$ ( $1 \le N \le 2 \times 10^5$ , , ), the number of prisms, the number of directed channels, and the number of phase marks.

Output

If no selection satisfies every channel, print IMPOSSIBLE.

Otherwise, print $N$ integers $S_1, S_2, \ldots, S_N$ , each equal to or . If , prism is locked at phase . If , it is locked at phase .

Samples

Sample 1

Input

Output

1 1 1

The printed selection uses phases $1$ , $3$ , and $5$ . The clockwise advances of the three channels are $2$ , $2$ , and $8$ , respectively, so every required interval is met.

Prism Phase Locks

Input

Output

Samples

Sample 1

Submit

Submissions

Sample 2