Kuinka moni voi menestyä yhtä hyvin kuin wcysai?
Yritys R on wcysain perustama rahaa tahkoava yritys, jonka vuotuinen liikevaihto on yli 100 miljoonaa. Yritys R:ssä työskentelee $n$ työntekijää, ja jokainen työntekijä asuu talossa. Joidenkin työntekijöiden talot on yhdistetty kaksisuuntaisilla teillä. On taattu, että kenen tahansa työntekijän talosta lähtien voidaan päästä kenen tahansa muun työntekijän talolle teitä pitkin.
Työntekijät on jaettu kahteen tyyppiin: johtajiin (tyyppi A) ja työläisiin (tyyppi B). Johtaja työskentelee $a$ tuntia päivässä, kun taas työläinen työskentelee $b$ tuntia päivässä. Luonnollisesti työläisten täytyy työskennellä pidempään kuin johtajien, joten $a < b$. Jokaisella työntekijällä on työn aloitusaika $s_i$. Jos tämän työntekijän täytyy työskennellä $m$ tuntia ($m = a$ tai $m = b$), niin hänen lopetusaikansa on $t_i = s_i + m$.
Työntekijät eivät kuitenkaan koskaan halua olla kaikkein ylityöllistetyimpiä. Siksi aloittaessaan työt he tarkistavat, onko joku heidän naapureistaan (eli työntekijöistä, joiden talot ovat suoraan yhteydessä teillä) jo aloittanut työskentelyn. Vastaavasti lopettaessaan työt he tarkistavat, onko joku heidän naapureistaan vielä lopettamatta työskentelyä. Jos molemmat havainnot ovat myönteisiä, he ovat tyytyväisiä. Muodollisesti työntekijä on tyytyväinen jos ja vain jos on olemassa naapuri, jonka aloitusaika on aidosti aikaisempi kuin hänen omansa, ja on olemassa naapuri, jonka lopetusaika on aidosti myöhäisempi kuin hänen omansa (nämä kaksi naapuria voivat olla sama henkilö tai eri henkilöitä). Muussa tapauksessa työntekijä on tyytymätön, koska hän tuntee olevansa kaikkein ylityöllistetyin.
Nyt wcysain pätevänä avustajana voit vapaasti järjestää jokaisen työntekijän aloitusajan. Haluat aikatauluttaa kaikki työntekijät järkevästi niin, että tyytymättömien ihmisten määrä minimoituu. Huomaa, että voit asettaa aloitusajoiksi mitä tahansa ei-negatiivisia reaalilukuja (katso yksityiskohdat tulostemuodosta).
Syöte
Ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 10^5$), testitapausten lukumäärän.
Jokaisessa testitapauksessa ensimmäinen rivi sisältää neljä ei-negatiivista kokonaislukua $n$, $m$, $a$ ja $b$ ($1 \le n, m \le 5 \cdot 10^5$, $1 \le a < b \le 10^6$), jotka vastaavat työntekijöiden lukumäärää, teiden lukumäärää, johtajien työtunteja ja työläisten työtunteja.
Seuraava rivi sisältää pituudeltaan $n$ olevan merkkijonon, joka koostuu vain merkeistä A ja B. $i$:s merkki kertoo $i$:nnen työntekijän tyypin.
Seuraavat $m$ riviä sisältävät kukin kaksi ei-negatiivista kokonaislukua $u, v$ ($1 \le u, v \le n$), jotka kuvaavat tietä.
On taattu, että jos työntekijöiden taloja pidetään solmuina ja teitä kaarina, verkossa ei ole rinnakkaisia kaaria eikä silmukoita ja se on yhtenäinen.
On taattu, että lukujen $n$ summa ja lukujen $m$ summa yli kaikkien testitapausten eivät ylitä $5 \cdot 10^5$.
Tuloste
Tulosta jokaista testitapausta kohden yksi rivi, joka sisältää $n$ ei-negatiivista kokonaislukua $s'_i$ ($0 \le s'_i \le 10^{18}$). Tarkemmin sanottuna, jos $s_i$ merkitsee aikaa, jolloin $i$:s työntekijä aloittaa työskentelyn, niin $s_i = \frac{s'_i}{10^6}$. Jos on olemassa useita optimaalisia aikatauluja, jotka minimoivat tyytymättömien ihmisten määrän, tulosta mikä tahansa niistä.
Esimerkki
Syöte 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
Tuloste 1
0 1 1 0 2 2 1 0 3 4 2 3 1 4 4000005 0 3000003 3000004 3000002 3000005 3000006 1 0