A school exam is coming. But the TA in charge encounters a problem! He finds that the number of seats in the room is not enough. So he should divide the students into two parts, where one part of students have to move to another room. Hence, all the students whose student ID's last two digits is less than some particular number(an integer which is not greater than 100) have to move to another room. But which number must he select?
Now given the two room's size (how many students it can contain) and all students' student ID. The student ID is combined by one capital letters and 8 digits. (ex: B96201044)
Because the number of students is very large, the student IDs is given by a list of groups of of student IDs as arithmetic sequence (Sequence where the adjacent numbers have same difference). Here the "difference of two student IDs" simply means their difference regarding to their numerical part. A group of student IDs is expressed by three parts. First part is one student ID denoting the first student ID of the group. The second part is one number denoting the difference of the group of student IDs. The last part is the number of elements in the group.
For example, group "B97902001 5 5" means IDs B97902001,B97902006,B97902011,B97902016,B97902021.
The first line of input contains T, denoting the number of test cases.
The first line of each test contain three integers r1, r2, g, denoting the size of original room, the size of the other room, and the number of groups of student IDs, respectively. Then there are g lines, each line contains one group of description of student ID, as described above.
T<=100
1<=r1,r2<=2147483647
g<=200000
all students IDs in a test case are different and valid.
the original room's size is less than the number of students.
For each test case, you have to print two lines. The first line of output contain pi, the number of possible numbers the TA can specify. Then the next line contain these pi possible numbers separated by exact one space. you have to list these numbers in increasing order.
2 70 70 2 B97902001 2 67 B97901001 3 73 100 100 2 B97902001 2 67 B97901001 3 73
1 40 47 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
Migrated from old NTUJ.
dreamoon
| No. | Testdata Range | Score |
|---|