Robot va chạm

Có $n$ robot di chuyển trên trục $Ox$. Có hai bức tường: một tại tọa độ $0$ và một tại tọa độ $m$.

Robot thứ $i$ bắt đầu tại tọa độ nguyên $x_i$ ($0<x_i<m$) và di chuyển sang trái (về phía $0$) hoặc sang phải với tốc độ $1$ đơn vị mỗi giây. Không có hai robot nào bắt đầu ở cùng một tọa độ.

Mỗi khi một robot chạm vào một bức tường, nó lập tức quay đầu và tiếp tục di chuyển theo chiều ngược lại với cùng tốc độ.

Mỗi khi hai hoặc nhiều robot gặp nhau tại cùng một tọa độ nguyên, chúng va chạm và nổ tung. Khi một robot đã nổ, nó không còn va chạm với bất kỳ robot nào khác nữa. Lưu ý rằng nếu nhiều robot gặp nhau tại một tọa độ không nguyên thì không có gì xảy ra.

Với mỗi robot, hãy xác định xem nó có bao giờ nổ hay không. Nếu có, in ra thời gian nổ; nếu không, in ra $-1$.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $t$ ($1\le t\le 1000$) — số bộ test.

Tiếp theo là mô tả của $t$ bộ test.

Dòng đầu tiên của mỗi bộ test chứa hai số nguyên $n$ và $m$ ($1\le n\le 3·{10}^5$; $2\le m\le {10}^8$) — số robot và tọa độ của bức tường bên phải.

Dòng thứ hai chứa $n$ số nguyên $x_1,x_2,\dots ,x_n$ ($0<x_i<m$) — tọa độ ban đầu của các robot.

Dòng thứ ba chứa $n$ ký tự 'L' hoặc 'R' cách nhau bởi dấu cách — chiều di chuyển ban đầu của các robot ('L' là sang trái, 'R' là sang phải).

Mọi tọa độ $x_i$ trong cùng một bộ test là phân biệt.

Tổng $n$ trên tất cả các bộ test không vượt quá $3·{10}^5$.

Dữ liệu ra

Với mỗi bộ test, in ra $n$ số nguyên — với robot thứ $i$, in thời gian nó nổ (nếu có), ngược lại in $-1$.

Ràng buộc

• $1\le t\le 1000$
• $1\le n\le 3·{10}^5$
• $2\le m\le {10}^8$
• $0<x_i<m$
• Tổng $n$ không vượt quá $3·{10}^5$

Ví dụ