SPOJ in Gyumri

   Однажды грабитель проник в квартиру. Но он столкнулся трудностью: всё ценное хранится в сейфе с кодовым замком. Устройство кодового замка нехитрое, колесо с числами от 1 до N, которое нужно покрутить туда-сюда несколько раз. Но открывающая сейф комбинация поворотов неизвестна, поэтому грабитель оставил возле сейфа подслушивающее устройство и покинул квартиру, чтобы вернуться позже.

   Когда владелец сейфа открывал замок, подслушивающее устройство зафиксировало количество щелчков при повороте колеса. Теперь грабителю известно, на сколько позиций нужно крутить колесо, но неизвестно, в какую сторону. Грабитель видел, в каком положении было колесо до открытия сейфа, и в каком положении оно осталось после закрытия. Поворот колеса в сторону последовательного увеличения чисел обозначим буквой U (up), а поворот в сторону последовательного уменьшения чисел обозначим буквой D (down). Например, на колесе 7 чисел от 1 до 7, изначально установлено 7, после открытия установлено число 2, и зафиксировано 3 поворота, длиной в 3, 5, 4 чисел. Тогда возможной открывающей комбинацией будет UDU: первое U сменит числа 7→1→2→3, потом D сменит числа 3→2→1→7→6→5, потом U сменит числа 5→6→7→1→2. Стоит заметить, что для данного примера это не единственная возможная последовательность: DDD также превратит 7 в 2: 7→6→5→4, 4→3→2→1→7→6, 6→5→4→3→2.

   Грабитель хочет узнать, сколько существует способов перевести колесо из начального положения в конечное, а также найти среди них лексикографически младший (из вариантов DDD и UDU выбирается DDD, поскольку DDD < UDU). Также возможно, что владелец сейфа обманул грабителя, тогда построить последовательность не получится.

Входные данные

   Первая строка входного файла содержит число тестов T (T ≤ 200).

   Описание каждого теста состоит из двух строк.

   В первой строке четыре целых числа: L - количество чисел на сейфе, S - начальное положение колеса, F - конечное положение колеса, N - количество поворотов (1 ≤ L, N ≤ 50, 1 ≤ S, F ≤ L). В следующей строке N чисел c_i – описание поворотов (1 ≤ с_i  ≤ 50).

Выходные данные

   Для каждого теста в отдельной строке вывести количество способов перевести колесо из начального положения в конечное. И, если оно ненулевое, то через пробел вывести лексикографически младшую последовательность поворотов.

Примеры входных и выходных данных