Taking the Stairs

Ron, Percy and Charlie Wesley went back to Hogwarts to participate as team RPC in Hogwarts’ Staircase Race. The goal is to reach Gryffindor Tower, moving through the Grand Staircase Tower as quickly as possible. We will not discuss the tower’s complex topology in detail; suffice it to say that the race takes place in a structure with many floors where participants have to go from the far left to the far right. The tower has a number of staircases that can connect two adjacent floors but, as you probably know if you’re familiar with Hogwarts, these staircases move all the time. Percy, being the clever one, observes the timings of the staircases and prepares a plan by noticing that it is a good idea to always take a staircase whenever you come across one during the race, since this guarantees that you won’t reach a point where you are forced to either wait for a staircase or go back. He decides to make a program to tell him, given his starting floor and the expected location of the staircases according to his calculations, the floor on which he will reach the far right of the tower, assuming that he always follows his strategy of taking every staircase. For example, let us say that the tower has 5 floors. The following figure illustrates the results in two different scenarios, one with 2 staircases and one with 7 staircases. Start End Start End EEEA DCDD CDCC BABB ABAE Floor 5 4 3 2 1 Figure 1: A couple of 5-floor setups, with 2 and 7 stairs As you can see, the floors are enumerated 1,2,3,..., where 1 is the first floor, and the paths are enumerated A, B, C, . . ., where A is the path that starts on the 1st floor, B on the 2nd floor, and so on. Input The input starts with an integer T, the number of test cases. Every test case starts with 3 integer numbers, H,W,N, indicating the size of the building—H is the height (number of floors), W is the width in meters of the tower, and N is the number of staircases. The following N lines have two integers x,y indicating the location of each staircase. x is the horizontal location in meters, while y is the floor on which the bottom end of the staircase is located (this means that the staircase connects floors y and y + 1). It can be safely assumed that there is one and only one possible way to get to every floor on the far right of the tower. T ≤ 100; 2 ≤ H ≤ 10; 3 ≤ W ≤ 1000; N ≤ 500; 1 < x < W ; 1 ≤ y < H

2/2 Output For each test case print one line of output, containing the resulting sequence of paths, as seen from the bottom floor to the top. Sample Input 3 5 30 2 10 3 20 1 5 30 7 44 83 12 2 16 1 20 2 24 3 28 4 5 30 2 10 2 20 1 Sample Output BADCE EBCDA CABDE