題干：

Running with barriers on the circle track is very popular in the country where Dasha lives, so no wonder that on her way to classes she saw the following situation:

The track is the circle with length?L, in distinct points of which there are?nbarriers. Athlete always run the track in counterclockwise direction if you look on him from above. All barriers are located at integer distance from each other along the track.

Her friends the parrot Kefa and the leopard Sasha participated in competitions and each of them ran one lap. Each of the friends started from some integral point on the track. Both friends wrote the distance from their start along the track to each of the?n?barriers. Thus, each of them wrote?n?integers in the ascending order, each of them was between?0?and?L?-?1, inclusively.

?Consider an example. Let?L?=?8, blue points are barriers, and green points are Kefa's start (A) and Sasha's start (B). Then Kefa writes down the sequence?[2,?4,?6], and Sasha writes down?[1,?5,?7].

There are several tracks in the country, all of them have same length and same number of barriers, but the positions of the barriers can differ among different tracks. Now Dasha is interested if it is possible that Kefa and Sasha ran the same track or they participated on different tracks.

Write the program which will check that Kefa's and Sasha's tracks coincide (it means that one can be obtained from the other by changing the start position). Note that they always run the track in one direction — counterclockwise, if you look on a track from above.

Input

The first line contains two integers?n?and?L?(1?≤?n?≤?50,?n?≤?L?≤?100) — the number of barriers on a track and its length.

The second line contains?n?distinct integers in the ascending order — the distance from Kefa's start to each barrier in the order of its appearance. All integers are in the range from?0?to?L?-?1?inclusively.

The second line contains?n?distinct integers in the ascending order — the distance from Sasha's start to each barrier in the order of its overcoming. All integers are in the range from?0?to?L?-?1?inclusively.

Output

Print "YES" (without quotes), if Kefa and Sasha ran the coinciding tracks (it means that the position of all barriers coincides, if they start running from the same points on the track). Otherwise print "NO" (without quotes).

Examples

Input

3 8 2 4 6 1 5 7

Output

YES

Input

4 9 2 3 5 8 0 1 3 6

Output

YES

Input

2 4 1 3 1 2

Output

NO

Note

The first test is analyzed in the statement.

題目大意：

? ?有兩個(gè)人分別在周長為L的圓上，圓上有n個(gè)障礙物，兩個(gè)人分別以逆時(shí)針的方向告訴你他們各自距離各個(gè)障礙物的距離，問他們是否在同一個(gè)圓上

解題報(bào)告：

? ? 構(gòu)造一個(gè)方法來判斷是否可以兩個(gè)圈重合。

? ?方法是：求出每兩個(gè)障礙物之間的坐標(biāo)差，記為ca數(shù)組和cb數(shù)組，然后o(n)遍歷起點(diǎn)，看有沒有一種起點(diǎn)，使得ca和cb數(shù)組的值均相同。

?

AC代碼：

#include<bits/stdc++.h>using namespace std; int a[55],b[55]; int ca[55],cb[55]; int main() {int n,mod,flag = 1;scanf("%d%d",&n,&mod); for(int i = 1; i<=n; i++) scanf("%d",&a[i]);for(int i = 1; i<=n; i++) scanf("%d",&b[i]);ca[0] = a[1] + mod-a[n];cb[0] = b[1] + mod-b[n];for(int i = 2; i<=n; i++) {ca[i-1] = a[i]-a[i-1];cb[i-1] = b[i]-b[i-1];}for(int k = 0; k<n; k++) {int j = k,cnt=n;flag=1;for(int i = 0; i<n; i++) {if(ca[i] != cb[j]){flag=0;break;}j=(j+1)%n;}if(flag == 1) break;}if(flag == 1) {printf("YES\n");return 0;}for(int k = 0; k<n; k++) {int j = k,cnt=n;flag=1;for(int i = n-1; i>=0; i--) {if(ca[i] != cb[j]){flag=0;break;}j=(j+1)%n;}if(flag == 1) break;}if(flag == 1) {printf("YES\n");return 0;}printf("NO\n");return 0 ;}

總結(jié)一下：

? ?注意這樣用的話涉及取模操作，凡是涉及取模操作的，都需要從0開始，我們這里也是注意到了這個(gè)問題。

?還有一種判斷二者相同的方法，可以代替這種o(n)遍歷起點(diǎn)的方法，就是：類似字符串匹配處理中的技巧，將ca數(shù)組復(fù)制一份（即長度變?yōu)閮杀?#xff09;，然后用一個(gè)長度為n的窗口，掃一遍看有沒有和cb完全重復(fù)的（轉(zhuǎn)成字符串可以也能用kmp）（我記得有一個(gè)字符串的題就是需要復(fù)制一份然后直接strstr掃一遍就出答案了那種）

代碼如下：

總結(jié)

以上是生活随笔為你收集整理的【CodeForces - 761B】Dasha and friends （思维，模拟，构造）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。