1169_C. Increasing by Modulo_36643
Toad Zitz has an array of integers, each integer is between 0 and m-1 inclusive. The integers are a_1, a_2, …, a_n.

In one operation Zitz can choose an integer k and k indices i_1, i_2, …, i_k such that 1 ≤ i_1 < i_2 < … < i_k ≤ n. He should then change a_{i_j} to ((a_{i_j}+1) mod m) for each chosen integer i_j. The integer m is fixed for all operations and indices.

Here x mod y denotes the remainder of the division of x by y.

Zitz wants to make his array non-decreasing with the minimum number of such operations. Find this minimum number of operations.

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 300 000) — the number of integers in the array and the parameter m.

The next line contains n space-separated integers a_1, a_2, …, a_n (0 ≤ a_i < m) — the given array.

Output

Output one integer: the minimum number of described operations Zitz needs to make his array non-decreasing. If no operations required, print 0.

It is easy to see that with enough operations Zitz can always make his array non-decreasing.

Examples

Input


5 3
0 0 0 1 2


Output


0


Input


5 7
0 6 1 3 2


Output


1

Note

In the first example, the array is already non-decreasing, so the answer is 0.

In the second example, you can choose k=2, i_1 = 2, i_2 = 5, the array becomes [0,0,1,3,3]. It is non-decreasing, so the answer is 1.
#include <bits/stdc++.h>
using namespace std;
void TxtRead() {
  freopen("sleepy.in", "r", stdin);
  freopen("sleepy.out", "w", stdout);
}
void TheTime() {
  ios_base::sync_with_stdio(false);
  cin.tie();
}
const int N = 3e5 + 5;
const long long INF = 1e9 + 5;
const int MOD = 1e9 + 7;
const double PI = 3.141592653589793116;
int n, m;
int ar[N];
bool _can(int x) {
  int br[N];
  memset(br, 0, sizeof(br));
  for (int i = 1; i <= n; i++) {
    br[i] = ar[i];
    if (br[i] > br[i - 1] && br[i] + x >= m && (br[i] + x) % m >= br[i - 1])
      br[i] = br[i - 1];
    else if (br[i] < br[i - 1] && br[i] + x >= br[i - 1])
      br[i] = br[i - 1];
    if (br[i] < br[i - 1]) return false;
  }
  return true;
}
int main() {
  TheTime();
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", &ar[i]);
  int l = 0, r = m, mid;
  while (l < r - 1) {
    mid = (l + r) / 2;
    if (_can(mid))
      r = mid;
    else
      l = mid;
  }
  if (_can(l))
    printf("%d\n", l);
  else
    printf("%d\n", r);
}

5 3
0 0 0 1 2
 5 7
0 6 1 3 2
 2 2
0 1
 100 10
8 4 4 9 0 7 9 5 1 1 2 3 7 1 8 4 8 8 6 0 8 7 8 3 7 0 6 4 8 4 2 7 0 0 3 8 4 4 2 0 0 4 7 2 4 7 9 1 3 3 6 2 9 6 0 6 3 5 6 5 5 3 0 0 8 7 1 4 2 4 1 3 9 7 9 0 6 6 7 4 2 3 7 1 7 3 5 1 4 3 7 5 7 5 0 5 1 9 0 9
 10 10
5 0 5 9 4 6 4 5 0 0
 6 4
1 3 0 2 1 0
 10 10
1 2 3 4 5 6 7 8 9 0
 10 1000
981 824 688 537 969 72 39 734 929 718
 1 1
0
 100 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 2 1
0 0
 100 1000
980 755 745 448 424 691 210 545 942 979 555 783 425 942 495 741 487 514 752 434 187 874 372 617 414 505 659 445 81 397 243 986 441 587 31 350 831 801 194 103 723 166 108 182 252 846 328 905 639 690 738 638 986 340 559 626 572 808 442 410 179 549 880 153 449 99 434 945 163 687 173 797 999 274 975 626 778 456 407 261 988 43 25 391 937 856 54 110 884 937 940 205 338 250 903 244 424 871 979 810
 10 300000
111862 91787 271781 182224 260248 142019 30716 102643 141870 19206
 4 6
0 3 5 1
 2 2
1 0
 100 2
1 1 0 1 0 1 0 0 0 1 0 1 0 0 1 1 1 1 1 0 1 1 1 1 1 1 0 0 0 1 1 0 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 0 1 0 0 1 0 0 1 0 1 0 1 1 1 0 1 1 0 1 1 0 1 0 0 0 1 0 1 1 0 1 1 0 1 0 1 0 0 0 0 0 1 0 0 0 0 1 1 1
 2 2
1 1
 100 10
8 4 4 9 0 7 9 5 1 1 2 3 7 1 8 4 8 8 6 0 8 7 8 3 7 0 6 7 8 4 2 7 0 0 3 8 4 4 2 0 0 4 7 2 4 7 9 1 3 3 6 2 9 6 0 6 3 5 6 5 5 3 0 0 8 7 1 4 2 4 1 3 9 7 9 0 6 6 7 4 2 3 7 1 7 3 5 1 4 3 7 5 7 5 0 5 1 9 0 9
 10 10
5 0 5 9 4 6 4 3 0 0
 6 4
1 3 -1 2 1 0
 10 1100
981 824 688 537 969 72 39 734 929 718
 10 300000
111862 91787 2609 182224 260248 142019 30716 102643 141870 19206
 2 3
1 0
 10 18
5 0 5 9 4 6 4 3 0 0
 10 1100
360 824 688 537 969 72 39 734 929 718
 10 300000
111862 91787 2609 298156 260248 142019 30716 102643 141870 19206
 10 1100
277 824 688 537 969 72 39 734 929 718
 10 1100
146 824 688 537 969 72 39 734 929 718
 10 300000
111862 91787 2609 298156 260248 142019 30716 197020 141870 14092
 10 501973
111862 91787 2609 298156 260248 142019 30716 197020 141870 14092
 6 8
1 3 0 2 1 0
 10 1000
981 824 688 537 969 72 39 102 929 718
 100 1000
980 755 745 448 424 691 210 545 942 979 555 783 425 942 495 741 487 514 752 434 187 874 372 617 414 505 659 445 81 397 262 986 441 587 31 350 831 801 194 103 723 166 108 182 252 846 328 905 639 690 738 638 986 340 559 626 572 808 442 410 179 549 880 153 449 99 434 945 163 687 173 797 999 274 975 626 778 456 407 261 988 43 25 391 937 856 54 110 884 937 940 205 338 250 903 244 424 871 979 810
 10 10
1 1 3 4 5 6 7 8 9 0
 2 2
0 0
 100 2
1 1 0 1 0 1 0 0 0 1 0 1 0 0 1 1 1 1 1 0 1 1 1 1 1 1 0 1 0 1 1 0 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 0 1 0 0 1 0 0 1 0 1 0 1 1 1 0 1 1 0 1 1 0 1 0 0 0 1 0 1 1 0 1 1 0 1 0 1 0 0 0 0 0 1 0 0 0 0 1 1 1
 5 3
1 0 0 1 2
 5 7
0 5 1 3 2
 100 10
8 4 4 9 0 7 9 5 1 1 2 3 7 1 8 4 8 8 6 0 8 7 8 3 7 0 6 7 8 4 2 7 0 0 3 8 4 4 2 0 0 4 7 2 4 7 9 1 3 3 6 2 9 6 0 6 3 5 4 5 5 3 0 0 8 7 1 4 2 4 1 3 9 7 9 0 6 6 7 4 2 3 7 1 7 3 5 1 4 3 7 5 7 5 0 5 1 9 0 9
 6 4
1 3 -1 2 0 0
 10 10
1 1 3 4 5 6 7 8 7 0
 100 2
1 1 0 1 0 1 0 0 0 1 0 1 0 0 1 1 1 1 1 0 1 1 1 1 1 1 0 1 0 1 1 0 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 0 1 0 0 1 0 0 1 0 1 0 1 1 1 0 1 1 0 1 1 0 1 0 0 0 1 0 1 1 0 1 1 0 1 0 1 0 0 0 0 0 1 0 0 0 -1 1 1 1
 5 3
1 0 -1 1 2
 5 7
0 2 1 3 2
 100 10
8 4 4 9 0 7 9 5 1 1 2 3 7 1 8 4 8 8 6 0 8 7 8 3 7 0 6 7 8 4 2 7 0 0 3 8 4 4 2 0 0 4 7 2 4 7 9 1 3 3 1 2 9 6 0 6 3 5 4 5 5 3 0 0 8 7 1 4 2 4 1 3 9 7 9 0 6 6 7 4 2 3 7 1 7 3 5 1 4 3 7 5 7 5 0 5 1 9 0 9
 10 18
6 0 5 9 4 6 4 3 0 0
 6 4
2 3 -1 2 0 0
 10 10
1 1 3 4 9 6 7 8 7 0
 10 300000
111862 91787 2609 298156 260248 142019 30716 102643 141870 14092
 100 2
1 1 0 1 0 1 0 0 0 1 0 1 0 0 1 1 1 1 1 0 1 1 1 1 1 1 0 1 0 1 1 0 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 0 1 0 0 1 0 0 1 0 1 0 1 1 1 0 1 1 0 0 1 0 1 0 0 0 1 0 1 1 0 1 1 0 1 0 1 0 0 0 0 0 1 0 0 0 -1 1 1 1
 100 10
8 4 4 9 0 7 9 5 1 1 2 3 7 1 8 4 8 8 6 0 8 7 8 3 7 0 6 7 8 4 2 7 0 0 3 8 4 4 2 0 0 4 7 2 4 7 9 1 3 3 1 2 9 6 0 6 3 5 4 5 5 3 0 0 8 7 1 4 2 4 1 3 9 7 9 0 0 6 7 4 2 3 7 1 7 3 5 1 4 3 7 5 7 5 0 5 1 9 0 9
 10 18
6 0 5 9 4 6 4 2 0 0
 6 4
2 3 -2 2 0 0
 100 2
1 1 0 1 0 1 0 0 0 1 0 1 0 0 1 1 1 1 1 0 1 1 1 1 1 1 0 1 0 1 1 0 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 0 1 0 0 1 0 0 1 0 1 0 1 1 1 0 1 1 0 0 2 0 1 0 0 0 1 0 1 1 0 1 1 0 1 0 1 0 0 0 0 0 1 0 0 0 -1 1 1 1
 100 10
8 4 4 9 0 7 9 5 1 1 2 3 7 1 8 4 8 8 6 0 8 7 8 3 7 0 6 7 8 4 2 7 0 0 3 8 4 4 2 0 0 4 7 2 4 7 9 1 3 3 1 2 9 6 0 6 5 5 4 5 5 3 0 0 8 7 1 4 2 4 1 3 9 7 9 0 0 6 7 4 2 3 7 1 7 3 5 1 4 3 7 5 7 5 0 5 1 9 0 9
 10 1100
146 824 688 537 969 72 39 734 1238 718
 100 2
1 1 0 1 0 1 0 0 0 1 0 1 0 0 1 1 1 1 1 0 1 1 1 1 1 1 0 1 0 1 1 0 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 0 1 0 0 1 0 0 1 0 1 0 1 1 1 0 1 1 0 0 2 0 1 0 0 0 1 0 1 1 0 1 1 0 1 0 1 0 -1 0 0 0 1 0 0 0 -1 1 1 1
 100 10
8 4 4 9 0 7 9 5 1 1 2 3 7 1 8 4 8 8 6 0 8 7 8 3 7 0 6 7 8 4 2 7 0 0 3 8 4 4 2 0 0 4 7 2 4 7 9 1 3 3 1 2 9 6 0 6 5 5 4 5 5 3 0 0 8 7 1 4 2 4 1 3 9 7 9 0 0 6 7 4 2 3 7 1 7 3 5 1 4 3 7 5 3 5 0 5 1 9 0 9
 10 501973
111862 91787 2609 298156 82558 142019 30716 197020 141870 14092
 100 2
1 1 0 1 0 1 0 0 0 1 0 1 0 0 1 1 1 1 1 0 1 1 1 1 1 1 0 1 0 1 1 0 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 0 1 0 0 1 0 0 1 0 1 0 1 1 1 0 1 1 0 0 2 0 1 0 0 0 1 0 1 1 -1 1 1 0 1 0 1 0 -1 0 0 0 1 0 0 0 -1 1 1 1
 10 501973
111862 83930 2609 298156 82558 142019 30716 197020 141870 14092
 100 2
1 1 0 1 0 1 0 0 0 1 0 1 0 0 1 1 1 1 1 -1 1 1 1 1 1 1 0 1 0 1 1 0 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 0 1 0 0 1 0 0 1 0 1 0 1 1 1 0 1 1 0 0 2 0 1 0 0 0 1 0 1 1 -1 1 1 0 1 0 1 0 -1 0 0 0 1 0 0 0 -1 1 1 1
 100 2
1 1 0 1 0 1 0 0 0 1 0 1 0 0 1 1 1 1 1 -1 1 1 1 1 1 1 0 1 0 1 1 0 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 0 1 0 0 1 0 0 1 0 1 0 1 1 1 0 1 1 0 0 2 0 1 0 0 0 1 0 1 1 -1 1 1 0 1 0 1 0 -1 0 0 0 1 0 0 0 -1 1 2 1
 100 2
1 1 0 1 0 1 0 0 0 1 0 1 0 0 1 1 1 1 1 -1 1 1 1 1 1 1 0 1 0 1 1 0 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 0 1 0 0 1 0 0 1 0 1 0 1 1 1 0 1 1 0 0 2 0 1 0 0 0 1 0 1 1 -1 1 1 0 1 0 1 0 -1 0 0 0 1 0 0 0 -1 1 0 1
 100 2
1 1 0 1 0 1 0 0 0 1 0 1 0 0 1 1 1 1 1 -1 1 1 1 1 1 1 0 1 0 1 1 0 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 0 1 0 0 1 0 0 1 0 1 0 1 1 1 0 1 1 0 0 2 0 1 0 0 0 1 0 1 1 -1 1 1 0 1 0 1 0 -1 0 1 0 1 0 0 0 -1 1 0 1
 100 2
1 1 0 1 0 1 0 0 0 1 0 1 0 0 1 1 1 1 1 -1 1 1 1 1 1 1 0 1 0 1 1 0 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 0 1 1 0 1 0 0 1 0 0 1 0 1 0 1 1 1 0 1 1 0 0 2 0 1 0 0 0 1 0 1 1 -1 1 1 0 1 0 1 0 -1 0 1 0 1 0 0 0 -1 1 0 1
 100 2
1 1 0 1 0 1 0 0 0 1 0 1 0 0 1 1 1 1 1 -1 1 1 1 1 1 1 0 1 0 1 1 0 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 0 1 1 0 1 0 0 1 0 0 1 0 1 0 1 1 1 0 1 1 0 0 2 0 1 0 0 0 1 0 1 1 -1 1 1 0 1 0 1 0 -1 0 1 0 1 0 0 0 -1 1 -1 1
 100 2
1 1 0 1 0 1 0 0 0 1 0 1 0 0 1 1 1 1 1 -1 1 1 1 1 1 1 0 1 0 1 1 0 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 0 1 1 0 2 0 0 1 0 0 1 0 1 0 1 1 1 0 1 1 0 0 2 0 1 0 0 0 1 0 1 1 -1 1 1 0 1 0 1 0 -1 0 1 0 1 0 0 0 -1 1 -1 1
 100 2
1 1 0 1 0 1 0 0 0 1 0 1 0 0 1 1 1 1 1 -1 1 1 1 1 1 1 0 1 0 1 1 0 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 0 1 1 0 2 0 0 1 0 0 1 0 1 0 1 1 1 0 1 1 0 0 2 0 1 0 0 0 1 0 1 1 -1 1 1 0 1 0 1 0 -1 0 0 0 1 0 0 0 -1 1 -1 1
 100 2
1 1 0 1 0 1 0 0 0 1 0 1 0 0 1 1 1 1 1 -1 1 1 1 1 1 1 0 1 0 1 1 0 1 -1 0 0 0 0 1 1 1 1 1 0 0 0 0 1 0 1 1 0 2 0 0 1 0 0 1 0 1 0 1 1 1 0 1 1 0 0 2 0 1 0 0 0 1 0 1 1 -1 1 1 0 1 0 1 0 -1 0 0 0 1 0 0 0 -1 1 -1 1
 100 2
1 1 0 1 0 1 0 0 0 1 0 1 0 0 1 1 1 1 1 -1 1 1 1 1 1 1 0 1 0 1 1 0 1 -1 0 0 0 0 1 1 1 1 1 0 0 0 0 1 0 1 1 0 2 -1 0 1 0 0 1 0 1 0 1 1 1 0 1 1 0 0 2 0 1 0 0 0 1 0 1 1 -1 1 1 0 1 0 1 0 -1 0 0 0 1 0 0 0 -1 1 -1 1
 100 2
1 1 0 1 0 1 0 0 0 1 0 1 0 0 1 1 1 1 1 -1 1 1 1 1 1 1 0 1 0 1 1 0 1 -1 0 0 0 0 1 1 1 1 1 0 0 0 0 1 0 1 1 0 2 -1 0 1 0 0 1 0 1 0 1 1 1 -1 1 1 0 0 2 0 1 0 0 0 1 0 1 1 -1 1 1 0 1 0 1 0 -1 0 0 0 1 0 0 0 -1 1 -1 1
 100 2
1 1 0 1 0 1 0 0 0 1 0 1 0 0 1 1 1 1 1 -1 1 1 1 1 1 1 0 1 0 1 1 0 1 -1 0 0 0 0 1 1 1 0 1 0 0 0 0 1 0 1 1 0 2 -1 0 1 0 0 1 0 1 0 1 1 1 -1 1 1 0 0 2 0 1 0 0 0 1 0 1 1 -1 1 1 0 1 0 1 0 -1 0 0 0 1 0 0 0 -1 1 -1 1
 100 2
1 1 0 1 0 1 0 0 0 1 0 1 0 0 1 1 1 1 1 -1 1 1 1 1 1 1 0 1 0 1 1 0 1 -1 0 0 0 0 1 1 1 0 1 0 0 1 0 1 0 1 1 0 2 -1 0 1 0 0 1 0 1 0 1 1 1 -1 1 1 0 0 2 0 1 0 0 0 1 0 1 1 -1 1 1 0 1 0 1 0 -1 0 0 0 1 0 0 0 -1 1 -1 1
 100 2
1 1 0 1 0 2 0 0 0 1 0 1 0 0 1 1 1 1 1 -1 1 1 1 1 1 1 0 1 0 1 1 0 1 -1 0 0 0 0 1 1 1 0 1 0 0 1 0 1 0 1 1 0 2 -1 0 1 0 0 1 0 1 0 1 1 1 -1 1 1 0 0 2 0 1 0 0 0 1 0 1 1 -1 1 1 0 1 0 1 0 -1 0 0 0 1 0 0 0 -1 1 -1 1
 100 2
1 1 0 1 0 2 0 0 0 1 0 1 0 0 1 1 1 1 1 -1 1 1 1 1 1 1 0 1 0 1 1 0 1 -1 0 0 0 0 1 1 1 0 1 0 0 1 0 1 0 1 1 0 2 -1 0 1 0 0 1 0 1 0 1 1 1 -1 1 1 0 0 2 0 1 0 0 0 1 0 1 2 -1 1 1 0 1 0 1 0 -1 0 0 0 1 0 0 0 -1 1 -1 1
 100 2
1 1 0 1 0 2 0 0 0 1 0 1 0 0 1 1 1 1 1 -1 1 1 1 1 1 1 0 1 0 1 1 0 1 -1 0 0 0 0 1 1 1 0 1 0 0 1 0 1 0 1 1 0 2 -1 0 1 0 0 1 0 1 0 1 1 1 -1 1 1 0 0 2 0 1 0 0 0 1 0 1 0 -1 1 1 0 1 0 1 0 -1 0 0 0 1 0 0 0 -1 1 -1 1
 100 2
1 1 0 1 0 2 0 0 0 1 0 1 0 0 1 1 1 1 1 -1 1 1 1 1 1 1 0 1 0 1 1 0 1 -1 0 0 0 0 1 1 1 0 1 0 0 1 0 1 0 1 1 0 2 -1 0 1 0 0 1 0 1 0 1 1 2 -1 1 1 0 0 2 0 1 0 0 0 1 0 1 0 -1 1 1 0 1 0 1 0 -1 0 0 0 1 0 0 0 -1 1 -1 1
 100 2
1 1 0 1 0 2 0 0 0 1 0 1 0 0 1 1 1 1 1 -1 1 1 1 1 1 1 0 1 0 1 1 0 1 0 0 0 0 0 1 1 1 0 1 0 0 1 0 1 0 1 1 0 2 -1 0 1 0 0 1 0 1 0 1 1 2 -1 1 1 0 0 2 0 1 0 0 0 1 0 1 0 -1 1 1 0 1 0 1 0 -1 0 0 0 1 0 0 0 -1 1 -1 1
 100 2
1 1 0 1 0 2 0 0 0 1 0 1 0 0 1 1 1 1 1 -1 1 1 1 1 1 1 0 1 0 1 1 0 1 0 0 0 0 0 1 1 1 0 1 0 0 1 0 1 0 1 1 0 2 -1 0 1 0 0 1 0 1 0 1 1 2 -1 1 2 0 0 2 0 1 0 0 0 1 0 1 0 -1 1 1 0 1 0 1 0 -1 0 0 0 1 0 0 0 -1 1 -1 1
 100 2
1 1 0 1 0 2 0 0 0 1 0 1 0 0 1 1 1 1 1 -1 1 1 1 1 1 1 0 1 0 1 1 0 1 0 0 0 0 0 1 1 1 0 1 0 0 1 0 1 0 1 1 0 2 -1 0 1 0 0 1 0 1 0 1 1 2 -1 1 2 0 0 2 0 1 0 1 0 1 0 1 0 -1 1 1 0 1 0 1 0 -1 0 0 0 1 0 0 0 -1 1 -1 1
 100 2
1 1 0 1 0 2 0 0 0 1 0 1 0 0 1 1 1 1 1 -1 1 1 1 1 1 1 0 1 0 1 1 0 1 0 0 0 0 0 1 1 1 0 1 0 0 1 0 1 0 1 1 0 2 -1 0 1 0 0 1 0 1 0 1 1 2 -1 1 2 0 0 2 0 1 0 1 0 1 0 1 0 -1 1 1 0 1 0 1 0 -1 0 0 1 1 0 0 0 -1 1 -1 1
 100 2
1 1 0 0 0 2 0 0 0 1 0 1 0 0 1 1 1 1 1 -1 1 1 1 1 1 1 0 1 0 1 1 0 1 0 0 0 0 0 1 1 1 0 1 0 0 1 0 1 0 1 1 0 2 -1 0 1 0 0 1 0 1 0 1 1 2 -1 1 2 0 0 2 0 1 0 1 0 1 0 1 0 -1 1 1 0 1 0 1 0 -1 0 0 1 1 0 0 0 -1 1 -1 1
 100 2
1 1 0 0 0 2 0 0 0 1 0 1 0 0 1 1 1 1 1 -1 1 1 1 1 1 1 0 1 0 1 1 0 1 0 0 0 0 0 1 1 1 0 1 0 0 1 0 1 0 1 1 0 2 -1 0 1 0 0 1 0 1 0 0 1 2 -1 1 2 0 0 2 0 1 0 1 0 1 0 1 0 -1 1 1 0 1 0 1 0 -1 0 0 1 1 0 0 0 -1 1 -1 1
 100 10
8 4 4 9 0 7 9 5 1 1 2 3 7 1 8 4 8 8 6 0 8 7 8 3 7 0 6 4 8 4 1 7 0 0 3 8 4 4 2 0 0 4 7 2 4 7 9 1 3 3 6 2 9 6 0 6 3 5 6 5 5 3 0 0 8 7 1 4 2 4 1 3 9 7 9 0 6 6 7 4 2 3 7 1 7 3 5 1 4 3 7 5 7 5 0 5 1 9 0 9
 10 10
5 0 5 9 4 6 3 5 0 0
 10 10
1 2 3 4 5 6 4 8 9 0
 10 300000
111862 91787 271781 182224 260248 142019 30716 102643 109238 19206
 100 2
1 1 0 1 0 1 0 0 0 1 0 1 0 0 1 1 1 1 1 0 1 1 1 1 1 1 0 0 0 1 1 0 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 0 1 0 0 1 0 0 1 0 1 0 1 1 1 0 1 1 0 1 0 0 1 0 0 0 1 0 1 1 0 1 1 0 1 0 1 0 0 0 0 0 1 0 0 0 0 1 1 1
 5 7
1 6 1 3 2

0
 1
 0
 8
 6
 2
 9
 463
 0
 0
 0
 860
 208213
 3
 1
 1
 0
 8
 6
 2
 563
 208213
 1
 9
 740
 151614
 689
 668
 182928
 284064
 3
 463
 860
 8
 0
 1
 1
 2
 8
 2
 8
 1
 2
 1
 8
 9
 2
 8
 151614
 1
 8
 9
 2
 1
 8
 668
 1
 8
 284064
 1
 284064
 1
 1
 1
 1
 1
 1
 1
 1
 1
 1
 1
 1
 1
 1
 1
 1
 1
 1
 1
 1
 1
 1
 1
 8
 6
 8
 208213
 1
 2
