User's AC Ratio

94.9% (93/98)

Submission's AC Ratio

30.5% (177/580)



In the currently used Gregorian calendar, there are $365$ days and $366$ days for a normal year and a leap year, respectively. The rule for leap years is as follows.
For year $y$ that is exactly divisible by four is a leap year, except for years that are exactly divisible by $100$, but these centurial years are leap years if they are exactly divisible by $400$. For example, the years $1700$, $1800$, and $1900$ are not leap years, but the years $1600$ and $2000$ are.
The days of the week can be represented as weekday numbers: Sunday as $0$, Monday as $1$, Tuesday as $2$ and so on. If we know $y$ and the day $d$ of the January $1$, we can calculate the day of any specific date $x$ by calculating the remainder of $elapsed\_days\_in\_year\_y(x)$ after division by $7$ and shifting $d$ days.
Write a program that reads $y$, $d$ and $x$, and then displays the weekday number of the date $x$.

Input Format

The first line contains two integers $y$ and $d$, separated by a space.
The second line contains two integers to represent month and day of the date $x$, respectively.

Output Format

An integer
If $x$ is a legal date, display the weekday number of $x$. If the month of $x$ is illegal, display $-1$. If the date of $x$ is illegal, display $-2$.

You can assume there is no testdata that the month and the date are both illegal.

Sample Input 1

2020 3
3 22

Sample Output 1



Problem Source


No. Testdata Range Score
1 0~5 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1
1 1000 65536 65536 1
2 1000 65536 65536 1
3 1000 65536 65536 1
4 1000 65536 65536 1
5 1000 65536 65536 1