Ilu ludzi może odnieść taki sukces jak wcysai?
Firma R to maszynka do robienia pieniędzy założona przez wcysai, o rocznych przychodach przekraczających 100 milionów. W Firmie R pracuje $n$ pracowników, a każdy z nich mieszka w swoim domu. Domy niektórych pracowników są połączone dwukierunkowymi drogami. Gwarantuje się, że wyruszając z domu dowolnego pracownika, można dotrzeć drogami do domu każdego innego pracownika.
Pracownicy dzielą się na dwa typy: menedżerów (typ A) i robotników (typ B). Menedżer pracuje $a$ godzin dziennie, natomiast robotnik pracuje $b$ godzin dziennie. Oczywiście robotnicy muszą pracować dłużej niż menedżerowie, więc $a < b$. Każdy pracownik ma czas rozpoczęcia pracy $s_i$. Jeśli ten pracownik musi przepracować $m$ godzin ($m = a$ lub $m = b$), to czas zakończenia jego pracy wynosi $t_i = s_i + m$.
Pracownicy nigdy jednak nie chcą być tymi najbardziej przepracowanymi. Dlatego rozpoczynając pracę, sprawdzają, czy którykolwiek z ich sąsiadów (czyli pracowników, których domy są bezpośrednio połączone drogami) już zaczął pracę. Podobnie kończąc pracę, sprawdzają, czy którykolwiek z ich sąsiadów jeszcze jej nie skończył. Jeśli obie obserwacje są pozytywne, czują się usatysfakcjonowani. Formalnie pracownik jest usatysfakcjonowany wtedy i tylko wtedy, gdy istnieje sąsiad, którego czas rozpoczęcia pracy jest ostro wcześniejszy niż jego własny, oraz istnieje sąsiad, którego czas zakończenia pracy jest ostro późniejszy niż jego własny (ci dwaj sąsiedzi mogą być tą samą osobą lub różnymi osobami). W przeciwnym razie pracownik będzie niezadowolony, ponieważ poczuje, że jest najbardziej przepracowany.
Teraz, jako zdolny asystent wcysai, możesz dowolnie ustalić czas rozpoczęcia pracy każdego pracownika. Chcesz zaplanować pracę wszystkich pracowników w rozsądny sposób, tak aby zminimalizować liczbę niezadowolonych osób. Zauważ, że jako czasy rozpoczęcia możesz przypisać dowolne nieujemne liczby rzeczywiste (szczegóły w formacie wyjścia).
Wejście
Pierwszy wiersz zawiera liczbę całkowitą $T$ ($1 \le T \le 10^5$), oznaczającą liczbę przypadków testowych.
Dla każdego przypadku testowego pierwszy wiersz zawiera cztery nieujemne liczby całkowite $n$, $m$, $a$ oraz $b$ ($1 \le n, m \le 5 \cdot 10^5$, $1 \le a < b \le 10^6$), oznaczające odpowiednio liczbę pracowników, liczbę dróg, liczbę godzin pracy menedżerów oraz liczbę godzin pracy robotników.
Następny wiersz zawiera napis o długości $n$ składający się wyłącznie ze znaków A oraz B. $i$-ty znak oznacza typ $i$-tego pracownika.
Kolejne $m$ wierszy zawiera po dwie nieujemne liczby całkowite $u, v$ ($1 \le u, v \le n$), oznaczające drogę.
Gwarantuje się, że jeśli potraktujemy domy pracowników jako wierzchołki, a drogi jako krawędzie, to graf nie ma krawędzi wielokrotnych ani pętli własnych i jest spójny.
Gwarantuje się, że suma $n$ oraz suma $m$ we wszystkich przypadkach testowych nie przekraczają $5 \cdot 10^5$.
Wyjście
Dla każdego przypadku testowego wypisz jeden wiersz zawierający $n$ nieujemnych liczb całkowitych $s'_i$ ($0 \le s'_i \le 10^{18}$). Dokładniej, niech $s_i$ oznacza czas, w którym $i$-ty pracownik rozpoczyna pracę — wówczas $s_i = \frac{s'_i}{10^6}$. Jeśli istnieje wiele optymalnych harmonogramów minimalizujących liczbę niezadowolonych osób, wypisz dowolny z nich.
Przykład
Wejście 1
5 2 1 1 5 AA 1 2 3 3 1 5 ABA 1 2 1 3 2 3 5 4 2 4 BABBB 1 2 1 5 2 3 2 4 6 9 1 5 BABBAB 1 2 1 3 1 4 2 6 3 4 3 5 3 6 4 5 5 6 7 7 2 5 BBAAABB 1 2 1 3 1 5 2 4 3 6 3 7 6 7
Wyjście 1
0 1 1 0 2 2 1 0 3 4 2 3 1 4 4000005 0 3000003 3000004 3000002 3000005 3000006 1 0