#G0048. 烟雾

烟雾

当前没有测试数据。

题目描述

有一个无限大的二维网格,在坐标 (0,0)(0,0) 处有一个篝火。

在时间 t=0t=0 ,烟雾仅存在于单元格 (0,0)(0,0)

您将得到一个长度为 NN 的字符串 SS ,由“n”、“w”、“s”和“e”组成, 表示风的吹向。

在时间 t=1,2,,Nt=1,2,\dots,N ,按顺序发生以下情况:

1、 风吹的时候,所有烟雾如下移动:

  • 如果 SS 的第 tt 个字符是 “n”,单元格 (r,c)(r,c) 中的烟雾移动到单元格 (r1,c)(r-1,c)

  • 如果是“W”,则单元格 (r,c)(r,c) 中的烟雾移动到单元格 (r,c1)(r,c-1)

  • 如果是“S”,则单元格 (r,c)(r,c) 中的烟雾移动到单元格 (r+1,c)(r+1,c)

  • 如果是“E”,则单元格 (r,c)(r,c) 中的烟雾移动到单元格 (r,c+1)(r,c+1)

2、 如果单元格 (0,0)(0,0) 中没有烟雾,则在单元格 (0,0)(0,0) 中产生新的烟雾。

Bob 站在 (R,C)(R,C) 的位置,对于每个整数 1tN1 \le t \le N ,确定时间 t+0.5t+0.5 时单元格 (R,C)(R,C) 处是否存在烟雾。

输入格式

  • NN 是介于 11200000200000 之间的整数,包括 11200000200000

  • SS 是长度为 NN 的字符串,由“n”、“w”、“s”和“e”组成。

  • RRCCN-NNN 之间的整数,包括 N-NNN

  • (R,C)(0,0)(R,C) \neq (0,0)

输出格式

打印由 “0” 和 “1” 组成的 NN -字符串。

tt 个字符( 1tN1 \le t \le N )应为:

  • “1”,如果在时间 t+0.5t+0.5 时在单元 (R,C)(R,C) 处存在烟雾

  • “0”,否则。

6 -2 1
NNEEWS
001010

###示例输出1

001010

有时 1.5,2.5,4.5,6.51.5,2.5,4.5,6.5 ,单元 (2,1)(-2,1) 没有烟雾。有时 3.5,5.53.5,5.5 ,单元 (2,1)(-2,1) 处有烟雾。

因此,输出'001010'。下图中,以带有营火的单元格 (0,0)(0,0) 为参照,绘制单元格 (r,c)(r,c)

  • r-r 个单元格,如果 r < 0

-如果 r0r \ge 0 ,则 rr 单元格关闭,

-如果 c < 0 ,则剩余 c-c 个单元格,

  • cc 个单元格位于 c0c \ge 0 的右侧。

时间 0.50.5 的网格如下所示:

时间 1.51.5 处的网格如下所示:

时间 2.52.5 处的网格如下所示:

时间 3.53.5 处的网格如下所示:

时间 4.54.5 的网格如下所示:

时间 5.55.5 的网格如下所示:

时间 6.56.5 处的网格如下所示:

数据规模与约定

0x,y1050\leq x,y\leq 10^5

注意数据溢出