과연 몇 명이나 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$)가 주어진다.
다음 줄에는 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