QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 1024 MB
[0]

# 3703. Range Query

Statistics

frog has a permutation p(1),p(2),,p(n) of {1,2,,n}. She also has m1+m2 records (ai,bi,ci) of the permutation.

  • For 1im1, (ai,bi,ci) means min{p(ai),p(ai+1),,p(bi)}=ci;
  • For m1<im1+m2, (ai,bi,ci) means max{p(ai),p(ai+1),,p(bi)}=ci.

Find a permutation which is consistent with above records, or report the records are self-contradictory. If there are more than one valid permutations, find the lexicographically least one.

Permutation p(1),p(2),,p(n) is lexicographically smaller than q(1),q(2),,q(n) if and only if there exists 1in which p(i)<q(i) and for all 1j<i, p(j)=q(j).

Input

The input consists of multiple tests. For each test:

The first line contains 3 integers n,m1,m2 (1n50,0m1+m250). Each of the following (m1+m2) lines contains 3 integers ai,bi,ci (1aibin,1cin).

Output

For each test, write n integers p(1),p(2),,p(n) which denote the lexicographically least permutation, or ``-1'' if records are self-contradictory.

Sample Input

5 1 1
1 5 1
1 5 5
3 1 1
1 2 2
1 2 2

Sample Output

1 2 3 4 5
-1