Двоє грають у таку гру. Спочатку є ~N~ (~1 \leqslant N \leqslant 10^5~) паличок. На кожному ході кожен гравець може забирати або одну, або дві, або три палички, але не більше, чим їх є всього. Описані досі ходи (тотожні класичній грі Баше) будемо називати традиційними. Крім них, існують спеціальні ходи: задається кілька пар цілих чисел ~(a_1, b_1)~, ~(a_2, b_2)~, ... , ~(a_t, b_t)~, які означають: якщо кількість паличок дорівнює якомусь із ~a_i~, то гравець може замінити ~a_i~ паличок на ~b_i~. Якщо гравець може зробити спеціальний хід, він сам вирішує, чи робити його, чи якийсь із традиційних, але зробити якийсь один хід треба. Ситуація, коли відразу кілька пар мають однакове значення ~a_i~, можлива; в такій ситуації гравець теж сам вирішує, яким із доступних ходів (спеціальних чи традиційних) скористатися. В будь-якому разі, після кожного ходу черга ходити переходить до іншого гравця, пропускати хід не можна. (Щоправда, користуватися ходом, де ~{b_i\,{=}\,a_i}~, можна, і це в деякому смислі відповідає пропуску ходу; але ж це можливо, лише якщо поточна кількість паличок якраз рівна таким ~b_i~ та ~a_i~, для яких існує такий спеціальний хід.) Закінчується гра тоді, коли лишається 0 паличок (це може статися хоч після традиційного ходу, хоч, якщо існує пара, де ~{b_i\,{=}\,0}~, після спеціального), і той, хто походив у цю позицію, виграв, а той, кому така позиція дісталася, програв.

Однак, ця гра може й не завершуватися, бо завдяки спеціальним ходам з ~{b_i\,{>}\,a_i}~ кількість паличок може так ніколи й не стати 0. Такий результат кожен з гравців розцінює як гірший, чим виграш, але кращий, чим програш.

Напишіть програму, яка визначатиме результат гри при ідеальній грі обох гравців. Щоб відповідь не так легко було вгадати, задачу слід розв'язати, при одній і тій самій сукупності пар ~(a_1, b_1)~, ~(a_2, b_2)~, ... , ~(a_t, b_t)~, для різних початкових кількостей паличок.

Вхідні дані

В першому рядку записане єдине ціле число ~t~ (~0 \leqslant t \leqslant 12345~), яке задає кількість пар, що утворюють спеціальні ходи. Кожен з подальших ~t~ рядків задає один спеціальний хід, у вигляді ~a_i~ ~b_i~ (два числа, розділені пробілом). Наступний ~{(t{+}2)}~-й рядок містить єдине ціле число ~k~ (~1 \leqslant k \leqslant 12345~) задає кількість варіантів початкової кількості паличок, а ще наступний ~{(t{+}3)}~-й рядок містить ~k~ натуральних чисел ~N_1~, ~N_2~, …, ~N_k~ (кожне в межах ~1 \leqslant N_i \leqslant 10^5~) – різні початкові кількості паличок, для яких слід розв'язати задачу.

Результати

Виведіть у один рядок без пропусків рівно ~k~ великих латинських букв W та/або L та/або D, де:

• W позначає, що при відповідній початковій кількості паличок гарантувати собі виграш може 1-й гравець,
• L – що 2-й,
• D – що жоден з гравців не може гарантувати собі виграшу, але 1-й гравець може гарантувати, що або гра триватиме нескінчeнно довго, або якщо 2-й поступиться, то виграє 1-й.

Приклади

Вхід

2
1 1
8 8
12
1 2 3 4 5 6 7 8 9 10 11 12

Результат

WWWLWWWDDDDD

Вхід

12
3 5
5 0
8 9
11 4
14 4
12 0
13 0
18 9
19 9
13 18
18 13
1 4
22
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

Результат

WWWLWWWDDDWWWWLWWWDDDDD

Примітки

У першому прикладі додаткові ходи дозволяють не забирати палички, коли їх у купці або 1, або 8. Якщо в купці 1 паличка, її вигідніше забрати й виграти. Якщо в купці 8 паличок, будь-який зі традиційних ходів веде до програшу, й вигідніше нічого не забирати, що потім повторюється обома гравцями до нескінчeнності. Й так виходить, що з усіх подальших позицій (9, 10, ... паличок) теж вигідніше якось (за один хід чи за кілька) прийти до позиції «8 паличок» і повторювати її до нескінчeнності.

У другому прикладі все набагато складніше.