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 1≤i≤m1, (ai,bi,ci) means min{p(ai),p(ai+1),…,p(bi)}=ci;
- For m1<i≤m1+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 1≤i≤n which p(i)<q(i) and for all 1≤j<i, p(j)=q(j).
Input
The input consists of multiple tests. For each test:
The first line contains 3 integers n,m1,m2 (1≤n≤50,0≤m1+m2≤50). Each of the following (m1+m2) lines contains 3 integers ai,bi,ci (1≤ai≤bi≤n,1≤ci≤n).
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