凋零
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

花儿有花期，故事会故去。
他和她走出了公园，凋零的花朵随风飘荡。
公园前的广场是一块 n \cdot n 的平地。
初始时，广场上有 m 朵花，位置为 (x_i,y_i) 。
每秒钟，花朵都会朝着固定方向 c_i 飞一格。
花朵之间相互独立，不会互相冲撞和停止。
如果花朵飞出了边界，会直接消失。
给定 q 次询问，每次询问给出 t,x,y 。
请你输出，第 t 秒后，格子 (x,y) 共有几朵花。

输入描述:

第一行输入三个整数 n\ (\ 1 \leq n \leq 100\ ) , m\ (\ 1 \leq m \leq n \cdot n\ ) , q\ (\ 1 \leq q \leq 10^5\ ) 。
随后 m 行，每行两个整数 x_i,y_i\ (\ 1 \leq x_i,y_i \leq n\ ) 和一个字母 c_i\ (\ c_i \in \{U,D,L,R\}\ ) ，UDLR代表上(-1,0)下(1,0)左(0,-1)右(0,1)。
随后 q 行，每行三个整数 t\ (\ 1 \leq t \leq 10^5\ ) 和 x,y\ (\ 1 \leq x,y \leq n\ ) 。

输出描述:

输出 q 行，每行一个整数，代表花朵数量。
示例1

输入

复制 
5 2 7
3 2 R
4 3 U
1 3 3
1 3 2
1 4 3
2 3 3
2 3 4
2 3 5
3 1 1

输出

复制 
2
0
0
0
1
0
0

说明

示例2

输入

复制 
3 4 7
1 1 R
1 3 D
3 3 L
3 1 U
1 2 2
1 2 1
1 1 2
1 3 2
1 2 3
7 1 1
2 1 1

输出

复制 
0
1
1
1
1
0
1

备注:

Chapter Three

他：还有什么要执行的手续吗？
她：清理一下照片吧。

流星的交汇只在一瞬，然后分离。
或许没有人做错了什么，只是一场绚丽的意外。
友人是什么，恋人又是什么。
最终成为互相不照面的陌生人。
要拥有必先懂失去怎接受。
故事到此结束，时间继续流淌。
而他和她，大抵不会再见面。