Great Sequence

A great sequence S is a sequence contains N decimal integers, i.e. S = (x[1], x[2], ..., x[N]). S should also satisfy following rules:
a[i] ≤ x[i] ≤ b[i]
ds[i] c[i] ds[i+1], where ds[i] is the digit sum of x[i] and c[i] is one of the following relational operators: "=", "<", "<=", ">", ">=" and "!=".
Obviously, there are a lot of great sequences. You are asked to find the K-th least great sequence in lexicographic order.

There are multiple test cases. Process to the End of File.
The first line of each test case contains two integers 1 ≤ N ≤ 100, 1 ≤ K ≤ 10¹⁶, as described above.
In the next N-1 lines, each line contains three elements, a[i], b[i] and c[i], where a[i] and b[i] are integers (1 ≤ a[i] ≤ b[i] ≤ 10¹⁸) while c[i] is one of the following strings: "=", "<", "<=", ">", ">=" and "!=".
The last line of each test cases contains only two integers, a[N] and b[N] (1 ≤ a[N] ≤ b[N] ≤ 10¹⁸).

For each test case, if the total number of great sequences is less than K, output "OUT OF RANGE" (without quotes); otherwise, output the K-th least great sequence in one line. Numbers in the sequence are separated by a single space.

3 15
9 10 <=
99 100 =
1 300
3 20
9 10 <=
99 100 =
1 300

10 100 100
OUT OF RANGE

Zejun Wu (watashi)

2013 Multi-University Training Contest 9