Problem J
Pay Your Taxes

Image by Barta IV from Pixabay

In the distant island of Hamt, like in many other countries, people complain that they don’t use the math they learned in school for anything. In response to the complaints, the Hamt government decided to change the tax system. Under the new tax system, taxpayers each year receive a formula for the amount that needs to be paid each month.

The formula involves taking the number of the month, raising it to an integer power (possibly multiple times), then multiplying the result with an integer (again possibly multiple times), and finally adding one or more integers.

Mathematically, the formula can be represented in the following format:

where $m$ is the month of the year ($1$ to $12$), and $A_i$, $B_j$, and $C_k$ are positive integer constants ($1 \le i \le n, 1 \le j \le m, 1 \le k \le l$).

You work for the accounting department of a company. Your boss suspects that the company has been paying its taxes wrong and wants you to recalculate the total amount owed in taxes for some intervals before the government notices.

Input

The input consists of a single test case. The first line contains two integers $I$ and $Y$, denoting the number of intervals $I$ that need to be calculated and the number of years $Y$, respectively ($1 \le I \le 500\, 000, 1 \le Y \le 50$). The next $Y$ lines contain the formulas for each of the years from $1$ to $Y$, where each formula is no longer than $500$ characters. The formulas uses “^” to represent power, “*” to represent multiplication and “+” to represent addition. The next $I$ lines each contain $4$ integers $y_1$, $m_1$, $y_2$, $m_2$ that represent the interval from the month $m_1$ of the year $y_1$ to the month $m_2$ of the year $y_2$ ($1 \le y_1, y_2 \le Y, 1 \le m_1, m_2 \le 12$).

Output

For each interval output a line with the amount of taxes owed for that interval. You are guaranteed that this amount is less than $2^{63}$ for each interval in the input.

1 1
m^2*2+2
1 1 1 2

14

4 4
m^0+1
m*0+0
m+20
m
4 11 4 12
1 1 4 12
2 10 3 4
1 12 2 1

535