409329: GYM103485 K Tributes to the Pharaohs

As the Greek historian Herodotus rightly said with "Egypt is a gift of the Nile", the Nile River played a key role in the development of the Egyptian civilization.

In yet another of its contributions, it is said that at the beginning of a distant year of Ancient Egypt, it was decided to make an audacious plan, using the Nile River, to honor all the $$$n$$$ pharaohs that the world had seen until then. For each pharaoh, it would be dedicated a harvest festival from a specific region along the Nile River.

Mainly due to the different crops planted and the different available labor forces in each region, times were estimated possibly different between regions for the two stages involved in each plantation: planting followed by harvest. The harvest festival would take place on the last day of the harvest. So the time until the day of the harvest festival in honor of a given pharaoh would be the sum of the time of the planting stage with the time of the harvest stage of the region dedicated to him.

However, to extol all the greatness of each pharaoh, the organizers would like two conditions to be met:

• Each harvest party takes place in one of the first $$$n$$$ days of a year from that year that was starting, that is, in someday in $$$\{0, \dots, n - 1\}$$$ (yes, the Egyptians indexed their zero days!). The egyptian years have $$$k$$$ days (days in $$$\{0, \dots, k - 1\}$$$). Note that it is not necessary that all parties occur in the same year, it is enough that each party occurs in $$$\{0, \dots, n - 1\}$$$ of some year.

• there must not have two festivals on the same day so that each Pharaoh is uniquely honored. There cannot be two parties on the same day even if in different years. For example, one party on the $$$0$$$ day of the $$$1$$$ year and another party on the $$$0$$$ day of the $$$3$$$ year cannot occur.

While the Egyptians can solve this problem, they preferred to focus on the festival in honor of their pharaohs. So they wanted you to analyze and decide if such tribute can be done as they wish.

The first line contains two positive integers $$$n$$$ and $$$k$$$ — the number of pharaohs to be honored and the number of days that made up the calendar of them, respectively.

The next two lines have two integer lists $$$p$$$ and $$$c$$$ of size $$$n$$$, where $$$p_i$$$ is the time needed to plant in region $$$i$$$ and $$$c_i$$$ is the time needed to harvest in region $$$i$$$ for each $$$i \in \{0, \dotsc, n - 1\}$$$.

Constraints

• $$$1 \leq n \leq 10^6$$$ 
• $$$n \leq k \leq 10^9$$$ 
• $$$0 \leq p[i], c[i] \leq 10^{9}$$$ for each $$$i$$$ in $$$\{0, 1, \dots, n - 1\}$$$.

You must answer "S" (no quotes) if it is possible to honor each pharaoh as desired or "N" (no quotes), otherwise.

2 2
0 1
1 0

N

3 3
2 0 1
1 2 0

S

3 4
0 2 5
1 0 3

S

In the first test, the answer is "N" since both the harvest festival in the $$$0$$$ region and the harvest festival in the $$$1$$$ region will both occur on the $$$1$$$ day.

In the second test, the answer is "S" since the festivals of 0, 1, and 2 regions will take place on days 0, 2, and 1, respectively, that is, all pharaohs will be honored in the days 0, 1, and 2 and separately from each other.

In the third test, the answer is "S" since the festivals of 0, 1, and 2 regions will take place on days 1, 2, and 0, respectively, that is, all pharaohs will be honored in the days 0, 1, and 2 and separately from each other.