E. Earnings Report
time limit per test
1.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You're working on a financial reporting platform. Your task is to calculate earnings obtained during certain time ranges, based on the salary information of different jobs. You'll be given N jobs and Q queries. Each query has a range of dates [L, R] and you must calculate the total earnings obtained in that range among all job salaries.

Each job has the following data:

  • Amount: Salary amount
  • StartDate: Start date of the job
  • EndDate: End date of the job (or its absence, indicating that the job is still ongoing)
  • Type: Salary type
There are three types of salaries, which determine when the payment is made and what dates are valid for the start of a job:
  • "weekly": The payment is made every Friday. A job of this type can only start on a Monday, that is, the first business day after the payday.
  • "bi-weekly": The payment is made on the 15th and the last day of each month. A job of this type can only start on the 1st or 16th of a month, that is, the day after the payday.
  • "monthly": The payment is made on the last day of each month. A job of this type can only start on the first day of a month, that is, the day after the payday.

If there's no end date, it means the job is still ongoing.

If there's an end date, and it falls within a query range, payments made on, or before that end date are included in the total.

If a payment is made a day after the end date, it's not included in the total.

Input

In the first line of input, there will be two integers N, Q $$$(1 \leq N \leq 10^3; ~1 \leq Q \leq 10^5)$$$, representing the number of jobs in the database, and the number of queries, respectively.

The next N lines will contain the data of one job in the format: "Amount StartDate EndDate Type" without the double quotes, where Amount is an integer $$$(1 \leq Amount \leq 10^9)$$$, StartDate and EndDate are in the format: DD/MM/YYYY $$$(01 \leq DD \leq 31; ~01 \leq MM \leq 12; ~2000 \leq YYYY \leq 9999)$$$, Type will be a string representing one of the salary types described before.

The EndDate could be "None", indicating that the job is still ongoing.

Afterward, there are Q lines, each with a query in the format: DD/MM/YYYY DD/MM/YYYY.

Output

For each query, print in a single line the total earnings obtained in that range among all job salaries.

Example
Input
3 2
2 01/10/8467 25/09/9231 monthly
5 13/06/7064 08/01/7520 weekly
4 01/05/6875 None bi-weekly
01/01/2000 31/12/9999
22/07/8260 28/01/9241
Output
437152
112462
Note
  • How to Determine a Leap Year:

    A year is a leap year if it satisfies the following conditions: The year is evenly divisible by 4; and, If the year can be evenly divided by 100, it is NOT a leap year, unless; The year is also evenly divisible by 400. Then it is a leap year.

  • Weekday of 01/01/2000:

    The 1st of January 2000 fell on a Saturday.

  • Days per month from Jan to Dec in a non-leap year: [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]