学年刚刚开始,但课程和奥赛已经占据了所有的空闲时间。今天奥尔加在文学上睡着了,这并不奇怪。她做了一个梦,梦见自己在楼梯上。
楼梯由 n 级台阶组成。台阶从下到上编号,这意味着最低的台阶编号为 1,最高的台阶编号为 n。每个上方都有一个指针,指示奥尔加应从此步骤移动的方向(向上或向下)。一旦奥尔加进入下一步,指针的方向(在她离开的步骤之上)就会改变。这意味着“上”方向变为“下”方向,“下”方向变为“上”方向。
Olga 始终按照步骤上方指针所示的方向移动到下一步。
如果奥尔加超出楼梯,她会跌倒并醒来。越过楼梯就是从第一步向下移动或从最后一步(即第n步)向上移动。
在一秒内,奥尔加根据指针的方向向上或向下移动一级,该指针位于奥尔加在这一秒开始时所在的台阶上方。
对于每一步,如果奥尔加在梦开始时处于这一步,请找出梦的持续时间。
奥尔加的跌倒也需要一秒的时间,所以如果她在第一步就跌倒了,下一秒就会醒来。
输入
第一行包含单个整数 n (1 ≤ n ≤ 106) — 楼梯上的台阶数。
第二行包含一个长度为 n 的字符串 s — 它表示楼梯上指针的初始方向。字符串 s 的第 i 个字符表示第 i 个步骤上方指针的方向,可以是“U”(表示该指针指向上方),也可以是“D”(表示该指针指向下方)。
指针按从下到上的顺序给出。
输出
打印 n 个数字,其中第 i 个数字要么等于 Olga 的梦的持续时间,要么等于 - 1(如果 Olga 从未超出楼梯),如果在睡眠开始时她在第 i 级台阶上。
示例
输入 #1
3 UUD
输出 #1
5 6 3
输入 #2
10 UUDUDUUDDU
输出 #2
5 12 23 34 36 27 18 11 6 1