Dima and lines#2932
Dima is studying algorithms for finding substrings within strings. Specifically, he wants to find all pairs of indices such that the substring of string starting at index and ending at index matches string .
Dima is trying to invent a new, fast algorithm to solve this problem. The main idea is to compare only certain characters, which significantly reduces the number of possible index pairs. He has already performed several comparisons and now wants to know how many pairs of indices remain that are still possible answers and do not contradict the data he gathered.
Remember, Dima is still a young boy, so he could have made mistakes in his measurements. If the input data is contradictory, output 0.
Dima uses an alphabet consisting of exactly 10^{100} letters.
The first line contains three integers , l_s, l_t (0 \leq n \leq 100, 1 \leq l_s \leq l_t \leq 10^9), where is the number of comparisons made, l_s is the length of the string , and l_t is the length of the string .
The next lines describe each comparison. Each line consists of the number (1 \leq i \leq l_s), a space, the symbol "" or "", a space, and the number (1 \leq j \leq l_t). If the symbol "" is used, then s_i = t_j must hold; if the symbol "" is used, then s_i \neq t_j must hold.
Print a single number — the answer to Dima's question.
Example 1