You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

B 宇宙是个一维空间，B 宇宙现在有 $n$ 颗流星，第 $i$ 颗流星位于 $x_i$，每颗流星有一个固定的移动方向（向左或向右，右边是正方向）。每一个单位时间，每颗流星都会向它的移动方向移动 $0.5$ 个单位的距离。当两颗流星位置重合的时候，它们就会产生碰撞然后消失。容易证明流星碰撞的时间必然是整数。

B 宇宙的天文学家 b 想知道，对于每颗流星，它们会在第几个单位时间的结尾消失，或者它永远都不会消失。

输入格式

第一行一个数 $n$，表示 B 宇宙的流星总数。

第二行 $n$ 个数 $x_1, x_2, \cdots, x_n$，表示每颗流星当前的坐标。

第三行是一个长度为 $n$，只包含 $\mathrm{L}$ 和 $\mathrm{R}$ 的字符串，描述每颗流星的移动方向，$\mathrm{L}$ 表示向左（坐标减小），$\mathrm{R}$ 表示向右（坐标增大）。

输出格式

一行 $n$ 个数，第 $i$ 个数表示第 $i$ 颗流星消失的时刻，如果这颗流星永远不会消失，则输出 -1。

样例

样例输入 1

5
1 3 5 6 9
RLRRL

样例输出 1

2 2 -1 3 3

数据范围

• 对 $60 \%$ 的数据，$x_n \leq 5000$。
• 对 $100 \%$ 的数据，$2 \leq n \leq 10^5$。
• 均匀分布着 $\frac{1}{2}$ 的数据，保证最终所有流星都会消失。
• 对于所有数据，保证 $1 \leq x_1 \lt x_2 \lt \cdots x_n \leq 10^9$。