Universal Cup Judging System

Universal Cup

时间限制: 4.0 s 内存限制: 1024 MB 总分: 100 可 Hack ✓
统计

How many people can be as successful as wcysai?

Company R is a money-printing company founded by wcysai, with an annual revenue of over 100 million. There are $n$ employees working at Company R, and each employee lives in a house. Some employees' houses are connected by bidirectional roads. It is guaranteed that starting from any employee's house, one can reach any other employee's house through the roads.

Employees are divided into two types: managers (type A) and workers (type B). A manager works $a$ hours per day, while a worker works $b$ hours per day. Obviously, workers must work longer than managers, so $a < b$. Each employee has a starting work time $s_i$. If this employee needs to work $m$ hours ($m = a$ or $m = b$), then their ending time is $t_i = s_i + m$.

However, employees never want to be the most overworked one. Therefore, when they start work, they will check whether any of their neighbors (that is, employees whose houses are directly connected by roads) have already started working. Similarly, when they finish work, they will check whether any of their neighbors have not yet finished working. If both observations are positive, they will feel satisfied. Formally, an employee is satisfied if and only if there exists a neighbor whose starting time is strictly earlier than theirs, and there exists a neighbor whose ending time is strictly later than theirs (these two neighbors may be the same person or different people). Otherwise, the employee will be dissatisfied because they feel they are the most overworked one.

Now, as wcysai's capable assistant, you may freely arrange the starting time of each employee. You want to schedule all employees reasonably so that the number of dissatisfied people is minimized. Note that you may assign starting times to any non-negative real numbers (see the output format for details).

Input

The first line contains an integer $T$ ($1 \le T \le 10^5$), the number of test cases.

For each test case, the first line contains four non-negative integers $n$, $m$, $a$, and $b$ ($1 \le n, m \le 5 \cdot 10^5$, $1 \le a < b \le 10^6$), representing the number of employees, the number of roads, the working hours of managers, and the working hours of workers, respectively.

The next line contains a string of length $n$ consisting only of A and B. The $i$-th character represents the type of the $i$-th employee.

The next $m$ lines each contain two non-negative integers $u, v$ ($1 \le u, v \le n$), representing a road.

It is guaranteed that if the employees' houses are regarded as vertices and the roads as edges, the graph has no multiple edges or self-loops, and is connected.

It is guaranteed that the sum of $n$ and the sum of $m$ over all test cases do not exceed $5 \cdot 10^5$.

Output

For each test case, output one line containing $n$ non-negative integers $s'_i$ ($0 \le s'_i \le 10^{18}$). Specifically, let $s_i$ denote the time when the $i$-th employee starts working, then $s_i = \frac{s'_i}{10^6}$. If there are multiple optimal schedules that minimize the number of dissatisfied people, output any of them.

Example

Input 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

Output 1

0 1
1 0 2
2 1 0 3 4
2 3 1 4 4000005 0
3000003 3000004 3000002 3000005 3000006 1 0

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.