European Space Agency has N telescopes observing distant planets. The classified M different types of events. They noticed that every day on each planet there is exactly one type of event. They measure events in days because they discovered each event lasts at least one day, and at most 365 days. Events last only complete number of days, they never last fractional part of day. Each event of the same type lasts exactly the same number of days every time it occurs, regardless of the planet it occurs on.

After many years of observation they want to analyze data. The telescopes logged all observations, but unfortunately they forgot to write down the year the observations took place! Each telescope entry consists of start date, end date and number of each type of events observed. Given all observations on all planets, calculate the duration of each type of event. Note that the telescopes are super precise and they start working exactly when the event starts and end when an event ends, not necessarily the same one.

Note: for this task, each year has exactely 365 days.

입력

?D1D1 M1M1 D2D2 M2M2 F1 F2 ... FM“

Where D1D1 M1M1 (01 ≤ DD ≤ 31, 01 ≤ MM ≤ 12) are start date, D2D2 M2M2 end date, and Fi (0 ≤ Fi ≤ 200) number of times event type I was observed.

출력

입출력 예

input

1 1
26 02 03 03 1

output

5

input

1 1
26 02 03 03 2

output

185

input

3 3
22 03 01 10 9 10 10
05 05 16 12 1 7 10
20 06 15 01 4 9 10

output

102
204
125

First sample description:

출처: COCI 2009/2010 contest3 6/6