J. Jealous Youngsters
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
Picture by Bryon Lippincott on Flickr, cc by

It is chaos playtime at kindergarten again, and teacher Tom is having some difficulties. You see, kids often have disagreements about who should play with which toy. Whenever a kid perceives any form of injustice in the allocation of toys to kids, they start crying uncontrollably. The kids are clearly poor decision makers, so today Tom has a new plan: rather than letting the kids choose toys by themselves, he will assign toys to them in a way that prevents any crying.

Tom has been studying the behavior of the kids and now understands exactly under what circumstances they start crying. First, a child will cry if they have no toy to play with. Second, even having a toy, a child $$$A$$$ will cry if there is some other child $$$B$$$ playing with some toy $$$T$$$ such that $$$A$$$ envies $$$B$$$ for playing with $$$T$$$, and $$$A$$$ would rather play with $$$T$$$ than with $$$A$$$'s current toy. Additionally, Tom has observed the following four behavioural properties of children:

  1. Envious: children envy those who have played more than them with any given toy. If child $$$A$$$ played strictly more with toy $$$T$$$ yesterday than child $$$B$$$ did, then $$$B$$$ will be envious of $$$A$$$ for playing with $$$T$$$ today.
  2. Inflexible: a child would rather play with some toy it played with yesterday, and the earlier they first played with it yesterday, the more they want to play with it today. All toys that a child did not play with at all yesterday are equally (un)desirable to the child.
  3. Cannot multitask: a child never plays with more than one toy at a time.
  4. Uncooperative: children are bad at sharing, and two children never play with the same toy at the same time.
Tom has recorded which toys were played with by which kid yesterday, taking note of when each kid started playing with a toy. Using this information, Tom aims to make one fixed assignment of toys for all of today that, if possible, prevents any crying.
Input

The first line of input contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n,m \leq 1\,000$$$), the number of kids and the number of toys. The kids are numbered from $$$1$$$ to $$$n$$$ and the toys from $$$1$$$ to $$$m$$$. Then follows a line containing two integers $$$d$$$ and $$$e$$$ ($$$1 \leq d \leq 10^9$$$ and $$$0 \leq e \leq 10^6$$$), the total duration of yesterday's playtime in microseconds and the number of events Tom recorded yesterday.

Then follow $$$e$$$ lines giving the events Tom recorded yesterday. Each event is described by a line containing three integers $$$s$$$, $$$k$$$ and $$$t$$$ ($$$0 \le s \lt d$$$, $$$1 \le k \le n$$$, and $$$0 \le t \le m$$$), indicating that kid $$$k$$$ started playing with toy $$$t$$$ at time $$$s$$$ (in microseconds since the start of yesterday's playtime). If $$$t = 0$$$ then kid $$$k$$$ stopped playing with any toy at time $$$s$$$.

The events are given in non-decreasing order of time (i.e., the values of $$$s$$$ are non-decreasing). All toy changes for all kids prior to playtime ending have been recorded by Tom (in particular if one kid $$$k_1$$$ steals a toy from some other kid $$$k_2$$$, there is also an event indicating $$$k_2$$$'s change of toy at the same microsecond, even if $$$k_2$$$ stops playing with any toy). At the start of the playtime, no kid is playing with any toy (but they can start playing with a toy at time $$$0$$$). At time $$$d$$$ all kids still playing with toys stopped playing with them but Tom did not record these events. Kids do not switch toys more than once per microsecond.

Output

If there is an assignment of toys to kids such that no kid will start crying today, output $$$n$$$ distinct integers, the $$$i^{\text{th}}$$$ of which is the toy that kid $$$i$$$ should play with. If there are multiple possible solutions, output any one of them. Otherwise, if there is no such assignment, output "impossible".

Examples
Input
2 3
6 7
0 1 1
0 2 2
1 1 3
2 1 2
2 2 1
3 2 3
4 2 1
Output
1 2
Input
2 1
20 3
0 1 1
10 1 0
10 2 1
Output
impossible
Input
1 3
3 3
0 1 1
1 1 2
2 1 3
Output
2