Story

⛄❄

matcharate君とwhiteさんは、割ってしまったチョコレートをもとの姿に直すことができました。 なのに、なぜかwhiteさんは悲しい顔をしています。matcharate君は慰めましたが、それでもダメでした。 なので気分転換に、外を探検してみようとしました。

「グリーンさん、whiteさんとちょっくら外行ってくるわー！店頼んだよー」

greenrate君は怪訝そうな顔をしながら頷きました。matcharate君は優しい面もありますが、大分無責任な人ですね。

:

matcharate君はwhiteさんに、こう言いました。

「一緒に雪だるま作らない？」

whiteさんは「作りたいですっ！！」と楽しそうに言いながら、一緒におっきな雪玉を作ろうとしました。

ただ…この街も社会の闇があって、大きな雪玉を作らせないような街があるようですね。

問題

無限に広がる座標平面上に、看板が $N$ 個置かれています。それぞれ看板には $1,2,\dots N$ の番号が付いています。
また看板 $i\ (1\le i\le N)$ には数値 $A_i$ が書かれており、座標 $(X_i,Y_i)$ にあります。

今からrate君は $K$ 回の行動を行います。この行動の情報は L, R, U, D からなる長さ $K$ の文字列 $S$ で与えられます。
これは、rate君の今いる座標 $(x,y)$ として、$k\ (1\le k\le K)$ 回目の行動で以下のように移動します。

• $S_k=$ L のとき、$(x,y)$ から $(x-1,y)$ へ移動する
• $S_k=$ R のとき、$(x,y)$ から $(x+1,y)$ へ移動する
• $S_k=$ U のとき、$(x,y)$ から $(x,y+1)$ へ移動する
• $S_k=$ D のとき、$(x,y)$ から $(x,y-1)$ へ移動する

この行動は一度通過した座標に再び通過することがあります。

今、rate君は座標 $(0,0)$ に大きさ $0$ の雪玉を持って立っています。rate君は座標が $1$ 進む度に、雪玉の大きさを $1$ だけ大きくなります。

ただし行動をしている最中に看板(看板 $i$ とします)が立っている座標に止まった時、rate君が持っている雪玉の大きさが $A_i$ 以下でなければなりません。
もし大きさが $A_i$ 以下でないなら、今の雪玉の大きさ $s$ とし、その座標に大きさ $(s-A_i)$ の雪玉を置かなければいけなくなりません。そうして置いた後、今の雪玉の大きさは $A_i$ になります。

$K$ 回の行動が終わった後、今いる座標に持っている雪玉をそのまま置きます。
このとき、どこか座標に置いたすべての雪玉について、その雪玉の大きさを行動順に求めてください。

ただし二度以上通過した、看板がある座標において、一度置いた雪玉はそのまま置くものとして、再び通過した後にその雪玉を再び利用して大きくさせることはできないものとします。

入力

入力は以下の形式で与えられる。

制約

• $0\le N\le 10^3$
• $1\le K\le 10^3$
• $S$ は L,R,U,D からなる長さ $K$ の文字列
• $|X_i|,|Y_i|\le 10^3$
• $i\ne j\Rightarrow (X_i,Y_i)\ne (X_j,Y_j)$
• $1\le A_i\le 10^3$
• $N,K,A_i,X_i,Y_i$ は整数

出力

次の形式で出力せよ。

ただし $P$ はrate君が置いた雪玉の個数を表し、$W_p\ (1\le p\le P)$ は行動順に置いた雪玉の大きさを表す。

入出力例

2 5
RRRRD
2 3 0
2 4 -1

3
1 2 2

• $1,2,3$ 回目の行動で $(0,0),(1,0),(2,0),(3,0)$ と移動します。よって $1$ つ目の看板にたどり着きます。
  この時大きさ $3$ の雪玉であるので、大きさ $(3-2=)1$ の雪玉を置く必要があります。現在の雪玉の大きさは $2$ となります。

• $4,5$ 回目の行動で $(3,0),(4,0),(4,-1)$ と移動します。よって $2$ つ目の看板にたどり着きます。
  この時 $3$ 回目の行動で大きさ $2$ の雪玉を持っているので、この時点で大きさ $(2+2=)4$ の雪玉を持っています。
  なのでこの座標で大きさ $(4-2=)2$ の雪玉を置く必要があります。

• すべての行動を終えた後、$(4,-1)$ に残った大きさ $2$ の雪玉を置きます。

以上から行動順にrate君が置いた雪玉の大きさは順に $1,2,2$ となり、$3$ 個の雪玉を置いたことになります。

0 12
DUDUDUDUDUDU

1
12

看板は一つもありません。座標 $1$ 移動する毎に雪玉の大きさが $1$ ずつ増えていくことに注意してください。

1 4
LLLL
10 -1 0

1
4

$2$ 回目の行動で看板の座標に辿り着きますが、大きさ $2$ の雪玉なので置く必要はありません。よって行動後に残った雪玉は $1$ つだけです。

6 20
RLLLLLDLLLRRRRUUUUUU
4 -3 0
3 -4 -1
2 -2 -1
6 0 -1
8 0 5
100 100 100

5
1 3 6 1 9

一度通過した看板のある座標に再び通過することがあることに注意してください。