Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3904
Birthday Gift

Time Limit: 8 Seconds      Memory Limit: 65536 KB

Bob wants to chase alice while alice is hard to get. If Bob wants to make a date with alice, Bob has to answer a alice's math problem firstly.

The problem is quite simple. Alice will give m constraints about an array of n positive integers representing as a[1], a[2] .. a[n]. The i-th of the m constraints consists 3 integers li, ri, qi, which means a[li] | a[li+1] | a[li+2] |...| a[ri] = qi. Here operator "|" represent as bitwise or. What Bob needs to do is to guess out the largest and smallest arrays in dictionary order which satisfy the m constraints and each element in the arrays should be positive and less than 2^30 (0

Input

The first line of input is an integer T, indicating the number of test cases. For each test case, the first line contains 2 integers: n, m (1<=n<=10^6,1<=m<=10^5). n is the size of the array, m is the number of constraints.Then follows m lines, the i-th line contains 3 integers li, ri, qi (1<=li<=ri<=n, 0<=qi<2^30) describing the i-th limit.

Output

For each cases, if answers is exists, in the first line print "come on, nice girl!"(without qoutes) then follows 2 lines, the first line contains n integers which represents the smallest array in dictionary order, and the second line conains n integers which represents the largest array in dictionary order. If answers is not exists, just print a line with a sentence "I am a poor guy!"(without qoutes)

Sample Input

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

Sample Ouput

come on, nice girl!
0 0 0 2 1
3 3 2 2 3
I am a poor guy!

Author: LIN, Binghui
Source: ZOJ Monthly, October 2015
Submit    Status