wcysai сияқты табысты бола алатын қанша адам бар?
R компаниясы — wcysai негізін қалаған, жылдық табысы 100 миллионнан асатын ақша басып шығаратын компания. R компаниясында $n$ қызметкер жұмыс істейді және әр қызметкер өз үйінде тұрады. Кейбір қызметкерлердің үйлері екі бағытты жолдармен байланысқан. Кез келген қызметкердің үйінен шығып, жолдар арқылы басқа кез келген қызметкердің үйіне жетуге болатынына кепілдік беріледі.
Қызметкерлер екі түрге бөлінеді: менеджерлер (A түрі) және жұмысшылар (B түрі). Менеджер күніне $a$ сағат, ал жұмысшы күніне $b$ сағат жұмыс істейді. Әрине, жұмысшылар менеджерлерден ұзағырақ жұмыс істеуі керек, сондықтан $a < b$. Әр қызметкердің жұмысты бастау уақыты $s_i$ бар. Егер бұл қызметкерге $m$ сағат ($m = a$ немесе $m = b$) жұмыс істеу керек болса, онда оның жұмысты аяқтау уақыты $t_i = s_i + m$ болады.
Дегенмен, қызметкерлер ешқашан ең көп жұмыс істейтін адам болғысы келмейді. Сондықтан олар жұмысты бастаған кезде көршілерінің (яғни үйлері жолдармен тікелей байланысқан қызметкерлердің) біреуі жұмысты бастап қойған-қоймағанын тексереді. Сол сияқты, жұмысты аяқтаған кезде олар көршілерінің біреуі жұмысты әлі аяқтамағанын тексереді. Егер екі бақылау да оң нәтиже берсе, олар қанағаттанады. Формальды түрде, қызметкер қанағаттанады сонда және тек сонда ғана, егер жұмысты бастау уақыты онікінен қатаң ертерек болатын көршісі табылса және жұмысты аяқтау уақыты онікінен қатаң кешірек болатын көршісі табылса (бұл екі көрші бір адам немесе әртүрлі адамдар болуы мүмкін). Әйтпесе, қызметкер өзін ең көп шаршаған адам ретінде сезініп, наразы болады.
Енді wcysai-дың білікті көмекшісі ретінде сіз әр қызметкердің жұмысты бастау уақытын еркін белгілей аласыз. Сіз наразы адамдар саны ең аз болатындай етіп барлық қызметкерлердің кестесін ұтымды құрғыңыз келеді. Бастау уақыты ретінде кез келген теріс емес нақты сандарды тағайындауға болатынын ескеріңіз (толығырақ шығыс деректер форматынан қараңыз).
Кіріс деректер
Бірінші жолда бір бүтін сан $T$ ($1 \le T \le 10^5$) — тест жағдайларының саны берілген.
Әрбір тест жағдайы үшін бірінші жолда сәйкесінше қызметкерлер санын, жолдар санын, менеджерлердің жұмыс сағатын және жұмысшылардың жұмыс сағатын білдіретін төрт теріс емес бүтін сан $n$, $m$, $a$ және $b$ ($1 \le n, m \le 5 \cdot 10^5$, $1 \le a < b \le 10^6$) берілген.
Келесі жолда тек A және B таңбаларынан тұратын ұзындығы $n$ жол берілген. $i$-ші таңба $i$-ші қызметкердің түрін білдіреді.
Келесі $m$ жолдың әрқайсысында жолды білдіретін екі теріс емес бүтін сан $u, v$ ($1 \le u, v \le n$) берілген.
Егер қызметкерлердің үйлерін төбелер, ал жолдарды қырлар деп қарастырсақ, графта еселік қырлар немесе ілмектер жоқ және ол байланысқан болатынына кепілдік беріледі.
Барлық тест жағдайлары бойынша $n$ қосындысы мен $m$ қосындысы $5 \cdot 10^5$-нен аспайтынына кепілдік беріледі.
Шығыс деректер
Әрбір тест жағдайы үшін $n$ теріс емес бүтін саннан $s'_i$ ($0 \le s'_i \le 10^{18}$) тұратын бір жолды шығарыңыз. Нақтырақ айтқанда, $s_i$ арқылы $i$-ші қызметкердің жұмысты бастау уақытын белгілесек, онда $s_i = \frac{s'_i}{10^6}$. Егер наразы адамдар санын барынша азайтатын бірнеше оңтайлы кесте болса, олардың кез келгенін шығарыңыз.
Мысал
Кіріс деректер 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
Шығыс деректер 1
0 1 1 0 2 2 1 0 3 4 2 3 1 4 4000005 0 3000003 3000004 3000002 3000005 3000006 1 0