Dima and lines
Dima, a young boy, is learning about algorithms that find occurrences of one string within another. Specifically, he wants to identify pairs of indices (i, j) such that the substring of string t, starting at index i and ending at index j, matches string s.
Dima is developing a new, efficient algorithm to tackle this problem. His approach involves comparing only specific characters, which significantly reduces the number of potential index pairs. Having performed several comparisons, Dima now wishes to determine how many index pairs remain valid solutions that do not conflict with the data he has gathered.
Keep in mind, Dima is still quite young, so there might be errors in his measurements. If the input data is contradictory, you should output 0.
The alphabet Dima uses consists of exactly 10^100 letters.
Input
The first line contains three integers n, l_s, l_t (0 ≤ n ≤ 100, 1 ≤ l_s ≤ l_t ≤ 10^9). Here, n is the number of comparisons made, l_s is the length of string s, and l_t is the length of string t. The following n lines provide details of each comparison. Each line includes the number i, 1 ≤ i ≤ l_s, followed by a space, the symbol "=" or "!", another space, and the number j, 1 ≤ j ≤ l_t. If the symbol "=" is present, it indicates s_i = t_j, and if the symbol "!" is used, it indicates s_i ≠ t_j.
Output
Output a single number — the answer to Dima's question.