数据范围n<=500

样例in:

4
RRRD
RULL
DULU
URUL
1 2 2 2
1 2 2 1
2 1 2 1
2 2 2 1

out:

160

n<=1e5,q<=1e6,ai<=1e9

样例in:

9 4
3 1 4 1 5 9 2 6 5
1 8
1 3
4 8
5 7

样例out:

0
1
1
3