有多少人能像 wcysai 一样成功？

R 公司是由 wcysai 创立的一家印钞公司，年营收超过 1 亿。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$），分别表示员工人数、道路数量、经理的工作小时数以及工人的工作小时数。

下一行包含一个长度为 $n$ 且仅由 “A” 和 “B” 组成的字符串。第 $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