题目描述

Eugene is reading a boring book. To make this process interesting he is drawing a picture at the same time. He has a piece of graph paper that is divided into square cells. All the cells are empty at the beginning.

Eugene starts by painting over one cell. Then he opens the book at a random page and starts reading.  Whenever he sees the letter u in the text, he moves his pen one cell up and then paints over the cell under his pen. Whenever he sees the letter d, he does the same but moves his pen one cell down instead of up. For letters l and r he moves to the left and to the right, respectively. If he wants to paint a cell that was already painted, he paints it again.

You have found a piece of paper and the text of the book. Now you want to understand if the picture o_n the paper could be drawn by Eugene at some point of his book reading. Remember that Eugene could use some substring of the text.

输入格式

The first line of the input contains an integer $l$ -- the length of the text $(1 \le l \le 100 000)$ . The $second line$ contains a string of length $l$ -- the text. It contains only lowercase English letters, spaces, commas and periods. The text neither begins nor ends with a space.

The third line contains two positive integers $n$ and $m$ -- the picture dimensions $(2 \le n \times m \le 100 000)$ .

Each of the following $n$ lines contains a string of length $m$ . Painted cells are denoted by X, while empty cells -- by . . It is guaranteed that there are at least two painted cells in the picture.

The first of these $n$ lines corresponds to the top of the picture and the last one corresponds to the bottom of it.

输出格式

If the picture could be painted by Eugene, output YES on the first line. On the second line print two integers b and $e$ such that if Eugene read all letters from $b$ to $e$ , inclusive, he would draw exactly $the same$ picture as described in the input $(1 \le b \le e \le l)$ . If there are several solutions, output any of them.

If the picture couldn't be drawn by Eugene, output NO.

题目大意

题目描述

Eugene正在读一本无聊的书。为了使阅读更有趣，他在阅读的同时同时作画。 他有一张方格纸。 所有的方格一开始都是空的。

Eugene一开始在一个方格上作画。让后他随机翻开一页并开始阅读。当他遇到字母 u 时, 他把笔向上移动一格并在这格上画画。 当他看到 d时, 他会做同样的操作，但是向下移动一格而不是向上移动一格。 l ,r分别是向左和向右一格。 如果这个单元格已经画过了他会再画一次。

现在你有一张纸与这本书中的内容。 现在你想知道这张纸上的图片是否可能被Eugene在某一时刻画过。 记住：Eugene可以只使用用这个内容的子字符串。

输入格式

第一行是一个整数$l(1 \le l \le 10^5)$--表示这个内容的长度。

第二行是一个长度为$l$的字符串$a$。它只包含小写英文字母、空格、逗号和句号。$a$既不会以空格开头也不会以空格结尾。

第三行是两个整数$n$ 与 $m$--图的大小$(2 \le n \times m \le 10^5)$ 。

第$4$~$3+n$行，每行一个长度为$m$的字符串。画过的格子用x表示，没画过的用.表示。保证一幅图中至少有两个格子已被涂色。

这 $n$ 行字符串中的第一行对应于图片的顶部，最后一行对应于图片的底部。

输出格式

如果可能被绘制，第一行输出YES，第二行输出用空格隔开的两个整数$b$和$e$,表示Eugene从第$b$个字母开始读，到第$e$个字母结束(包含$b$和$e$)。

如果不能，输出NO。

样例 #1

样例输入 #1

43
you should read statement really carefully.
3 6
...XX.
..XXX.
...XXX

样例输出 #1

YES
3 42

样例 #2

样例输入 #2

43
you should read statement really carefully.
3 2
XX
XX
XX

样例输出 #2

NO

说明/提示

时限: 2 s, 内存限制: 256 MB.

43
you should read statement really carefully.
3 6
...XX.
..XXX.
...XXX

YES
3 42

43
you should read statement really carefully.
3 2
XX
XX
XX

NO

提示

Time limit: 2 s, Memory limit: 256 MB.