Թաքցված խնդիր
|Այս խնդիրը թաքցված է խմբագրական խրհրդի անդամի կողմից քանի որ կամ այն ոչ ճիշտ լեզվով է գրված,|կամ թեստային տվյալներն են սխալ, կամ խնդրի ձևակերպումը պարզ չէ։|

ACM_0013 - HACK

   Однажды грабитель проник в квартиру. Но он столкнулся трудностью: всё ценное хранится в сейфе с кодовым замком. Устройство кодового замка нехитрое, колесо с числами от 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 чисел ci – описание поворотов (1 ≤ сi  ≤ 50).

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

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

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

stdin

stdout

1

3

7 7 2 3

3 5 4

7 7 7 3

3 5 4

5 1 1 6

1 1 1 1 1 1

2 DDD

0

20 DDDUUU


Ավելացրեց.Հրանտ Հովհաննիսյան
Ամսաթիվ.2013-12-08
Ժամանակի սահմանափակումը.1s
Ծրագրի տեքստի սահմանափակումը.50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Լեզուներ.Բոլորը բացի ASM32 ASM64 GAWK CLPS CLOJURE D ERL FSHARP FORTRAN GOSU HASK ICON ICK NEM NIM OBJC-CLANG PICO PIKE PYPY PY_NBC RUST SCM guile CHICKEN SED TCL WHITESPACE
Աղբյուրը.East Sibirean QF 2013.E

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.