QOJ.ac

QOJ

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

# 3703. Range Query

统计

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;
  • For m_1 < i \leq m_1 + m_2, (a_i, b_i, c_i) means \max\{p(a_i), p(a_i + 1), \dots, p(b_i)\} = c_i.

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), \dots, p(n) is lexicographically smaller than q(1), q(2), \dots, q(n) if and only if there exists 1 \leq i \leq n which p(i) < q(i) and for all 1 \leq j < i, p(j) = q(j).

Input

The input consists of multiple tests. For each test:

The first line contains 3 integers n, m_1, m_2 (1 \leq n \leq 50, 0 \leq m_1 + m_2 \leq 50). Each of the following (m_1 + m_2) lines contains 3 integers a_i, b_i, c_i (1 \leq a_i \leq b_i \leq n, 1 \leq c_i \leq n).

Output

For each test, write n integers p(1), p(2), \dots, 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