图灵机是一种通过读取纸带执行命令，模拟计算的抽象机器，为现代计算机提供了理论基础。现在有一个运行逻辑十分简单粗暴的图灵机，我们称之为"进击的图灵机"。

这种图灵机可以在二维平面上沿平行于坐标轴的方向行走，为了便于讨论，我们假设二维平面可以用坐标系来描述，图灵机初始在坐标系的点。

该图灵机所识别的纸带上有四种可能的命令，其含义分别为：

：沿向量的方向行走一单位长度；

：沿向量的方向行走一单位长度；

：沿向量的方向行走一单位长度；

：沿向量的方向行走一单位长度；

例如，若图灵机读取到命令序列，则其坐标变化的序列为。

现在，操作者有一条长度为的纸带，他每次让图灵机读取并执行这条纸带上连续的一段命令，一共进行次，对于每次执行命令，图灵机都会从坐标系的点出发，请你回答图灵机在这次执行命令过程中会回到坐标原点几次（最开始图灵机在原点的一次不计入考虑）。

输入第一行包含两个整数，表示纸带长度与执行命令次数。

第二行是一个长为的字符串，表示你手中的纸带，保证该字符串中只含有大写的。

接下来行，每行两个数字，表示这次执行命令读取的是纸带上第个字母到第个字母之间（含端点）的部分。

输出行，每行一个非负整数，表示在这一次命令中，图灵机回到过多少次坐标原点。

7 6
UUDLRDU
1 3
2 5
4 7
1 6
6 7
7 7

0
2
2
1
1
0