CodeForces Round #557 Div.2

A. Zoning Restrictions Again

You are planning to build housing on a street. There are nn spots available on the street on which you can build a house. The spots are labeled from 11 to nn from left to right. In each spot, you can build a house with an integer height between 00 and hh.

In each spot, if a house has height aa, you will gain a2a2 dollars from it.

The city has mm zoning restrictions. The ii-th restriction says that the tallest house from spots lili to riri (inclusive) must be at most xixi.

You would like to build houses to maximize your profit. Determine the maximum profit possible.

Input

The first line contains three integers nn, hh, and mm (1≤n,h,m≤501≤n,h,m≤50) — the number of spots, the maximum height, and the number of restrictions.

Each of the next mm lines contains three integers lili, riri, and xixi (1≤li≤ri≤n1≤li≤ri≤n, 0≤xi≤h0≤xi≤h) — left and right limits (inclusive) of the ii-th restriction and the maximum possible height in that range.

Output

Print a single integer, the maximum profit you can make.

Examples

input

Copy

3 3 3
1 1 1
2 2 3
3 3 2

output

Copy

14

input

Copy

4 10 2
2 3 8
3 4 7

output

Copy

262

Note

In the first example, there are 33 houses, the maximum height of a house is 33, and there are 33 restrictions. The first restriction says the tallest house between 11 and 11 must be at most 11. The second restriction says the tallest house between 22 and 22 must be at most 33. The third restriction says the tallest house between 33 and 33 must be at most 22.

In this case, it is optimal to build houses with heights [1,3,2][1,3,2]. This fits within all the restrictions. The total profit in this case is 12+32+22=1412+32+22=14.

In the second example, there are 44 houses, the maximum height of a house is 1010, and there are 22 restrictions. The first restriction says the tallest house from 22 to 33 must be at most 88. The second restriction says the tallest house from 33 to 44 must be at most 77.

In this case, it's optimal to build houses with heights [10,8,7,7][10,8,7,7]. We get a profit of 102+82+72+72=262102+82+72+72=262. Note that there are two restrictions on house 33 and both of them must be satisfied. Also, note that even though there isn't any explicit restrictions on house 11, we must still limit its height to be at most 1010 (h=10h=10).

代码：

#include <bits/stdc++.h>
using namespace std;

const int maxn = 100;
int N, H, M;
int a[maxn];

int main() {
    scanf("%d%d%d", &N, &H, &M);
    for(int i = 1; i <= N; i ++)
        a[i] = H;

    for(int i = 0; i < M; i ++) {
        int l, r, h;
        scanf("%d%d%d", &l, &r, &h);
        for(int j = l; j <= r; j ++)
            a[j] = min(h, a[j]);
    }

    int ans = 0;
    for(int i = 1; i <= N; i ++)
        ans += (a[i] * a[i]);
    printf("%d
", ans);
    return 0;
}

B. Double Matrix

You are given two n×mn×m matrices containing integers. A sequence of integers is strictly increasing if each next number is greater than the previous one. A row is strictly increasing if all numbers from left to right are strictly increasing. A column is strictly increasing if all numbers from top to bottom are strictly increasing. A matrix is increasing if all rows are strictly increasing and all columns are strictly increasing.

For example, the matrix [91110121114][91011111214] is increasing because each individual row and column is strictly increasing. On the other hand, the matrix [1213][1123] is not increasing because the first row is not strictly increasing.

Let a position in the ii-th row (from top) and jj-th column (from left) in a matrix be denoted as (i,j)(i,j).

In one operation, you can choose any two numbers ii and jj and swap the number located in (i,j)(i,j) in the first matrix with the number in (i,j)(i,j) in the second matrix. In other words, you can swap two numbers in different matrices if they are located in the corresponding positions.

You would like to make both matrices increasing by performing some number of operations (possibly none). Determine if it is possible to do this. If it is, print "Possible", otherwise, print "Impossible".

Input

The first line contains two integers nn and mm (1≤n,m≤501≤n,m≤50) — the dimensions of each matrix.

Each of the next nn lines contains mm integers ai1,ai2,…,aimai1,ai2,…,aim (1≤aij≤1091≤aij≤109) — the number located in position (i,j)(i,j) in the first matrix.

Each of the next nn lines contains mm integers bi1,bi2,…,bimbi1,bi2,…,bim (1≤bij≤1091≤bij≤109) — the number located in position (i,j)(i,j) in the second matrix.

Output

Print a string "Impossible" or "Possible".

Examples

input

Copy

2 2
2 10
11 5
9 4
3 12

output

Copy

Possible

input

Copy

2 3
2 4 5
4 5 6
3 6 7
8 10 11

output

Copy

Possible

input

Copy

3 2
1 3
2 4
5 10
3 1
3 6
4 8

output

Copy

Impossible

Note

The first example, we can do an operation on the top left and bottom right cells of the matrices. The resulting matrices will be [9111012][9101112]and [2345][2435].

In the second example, we don't need to do any operations.

In the third example, no matter what we swap, we can't fix the first row to be strictly increasing in both matrices.

代码：

#include <bits/stdc++.h>
using namespace std;

const int maxn = 110;
int N, M;
int a[maxn][maxn], b[maxn][maxn];
int vis[maxn][maxn], viss[maxn][maxn];

int main() {
    bool flag = true;
    scanf("%d%d", &N, &M);
    for(int i = 0; i < N; i ++) {
        for(int j = 0; j < M; j ++)
            scanf("%d", &a[i][j]);
    }
    for(int i = 0; i < N; i ++) {
        for(int j = 0; j < M; j ++)
            scanf("%d", &b[i][j]);
    }

    for(int i = 0; i < N; i ++) {
        if(!flag) break;
        for(int j = 0; j < M; j ++) {
            if(i < N - 1 && min(a[i][j], b[i][j]) >= min(a[i + 1][j], b[i + 1][j])) {
                flag = false;
                break;
            }
            if(i < N - 1 && max(a[i][j], b[i][j]) >= max(a[i + 1][j], b[i + 1][j])) {
                flag = false;
                break;
            }
            if(j < M - 1 && min(a[i][j], b[i][j]) >= min(a[i][j + 1], b[i][j + 1])) {
                flag = false;
                break;
            }
            if(j < M - 1 && max(a[i][j], b[i][j]) >= max(a[i][j + 1], b[i][j + 1])) {
                flag = false;
                break;
            }
        }
    }

    if(flag) printf("Possible
");
    else printf("Impossible
");

    return 0;
}

C. Hide and Seek

Alice and Bob are playing a game on a line with nn cells. There are nn cells labeled from 11 through nn. For each ii from 11 to n−1n−1, cells iiand i+1i+1 are adjacent.

Alice initially has a token on some cell on the line, and Bob tries to guess where it is.

Bob guesses a sequence of line cell numbers x1,x2,…,xkx1,x2,…,xk in order. In the ii-th question, Bob asks Alice if her token is currently on cell xixi. That is, Alice can answer either "YES" or "NO" to each Bob's question.

At most one time in this process, before or after answering a question, Alice is allowed to move her token from her current cell to some adjacent cell. Alice acted in such a way that she was able to answer "NO" to all of Bob's questions.

Note that Alice can even move her token before answering the first question or after answering the last question. Alice can also choose to not move at all.

You are given nn and Bob's questions x1,…,xkx1,…,xk. You would like to count the number of scenarios that let Alice answer "NO" to all of Bob's questions.

Let (a,b)(a,b) denote a scenario where Alice starts at cell aa and ends at cell bb. Two scenarios (ai,bi)(ai,bi) and (aj,bj)(aj,bj) are different if ai≠ajai≠aj or bi≠bjbi≠bj.

Input

The first line contains two integers nn and kk (1≤n,k≤1051≤n,k≤105) — the number of cells and the number of questions Bob asked.

The second line contains kk integers x1,x2,…,xkx1,x2,…,xk (1≤xi≤n1≤xi≤n) — Bob's questions.

Output

Print a single integer, the number of scenarios that let Alice answer "NO" to all of Bob's questions.

Examples

input

Copy

5 3
5 1 4

output

Copy

9

input

Copy

4 8
1 2 3 4 4 3 2 1

output

Copy

0

input

Copy

100000 1
42

output

Copy

299997

Note

The notation (i,j)(i,j) denotes a scenario where Alice starts at cell ii and ends at cell jj.

In the first example, the valid scenarios are (1,2),(2,1),(2,2),(2,3),(3,2),(3,3),(3,4),(4,3),(4,5)(1,2),(2,1),(2,2),(2,3),(3,2),(3,3),(3,4),(4,3),(4,5). For example, (3,4)(3,4) is valid since Alice can start at cell 33, stay there for the first three questions, then move to cell 44 after the last question.

(4,5)(4,5) is valid since Alice can start at cell 44, stay there for the first question, the move to cell 55 for the next two questions. Note that (4,5)(4,5)is only counted once, even though there are different questions that Alice can choose to do the move, but remember, we only count each pair of starting and ending positions once.

In the second example, Alice has no valid scenarios.

In the last example, all (i,j)(i,j) where |i−j|≤1|i−j|≤1 except for (42,42)(42,42) are valid scenarios.

代码：

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;
int N, K;
int st[maxn], en[maxn];

int main() {
    scanf("%d%d", &N, &K);
    for(int i = 1; i <= N; i ++) {
        en[i] = -1;
        st[i] = 1e5 + 10;
    }
    for(int i = 0; i < K; i ++) {
        int x;
        scanf("%d", &x);
        st[x] = min(i, st[x]);
        en[x] = max(i, en[x]);
    }

    int ans = 0;
    for(int i = 1; i <= N; i ++) {
        for(int j = i - 1; j <= i + 1; j ++) {
            if(j < 1 || j > N) continue;
            if(st[i] > en[j]) ans ++;
        }
    }

    printf("%d
", ans);

    return 0;
}

 E. Thanos Nim

Alice and Bob are playing a game with nn piles of stones. It is guaranteed that nn is an even number. The ii-th pile has aiai stones.

Alice and Bob will play a game alternating turns with Alice going first.

On a player's turn, they must choose exactly n2n2 nonempty piles and independently remove a positive number of stones from each of the chosen piles. They can remove a different number of stones from the piles in a single turn. The first player unable to make a move loses (when there are less than n2n2 nonempty piles).

Given the starting configuration, determine who will win the game.

Input

The first line contains one integer nn (2≤n≤502≤n≤50) — the number of piles. It is guaranteed that nn is an even number.

The second line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤501≤ai≤50) — the number of stones in the piles.

Output

Print a single string "Alice" if Alice wins; otherwise, print "Bob" (without double quotes).

Examples

input

Copy

2
8 8

output

Copy

Bob

input

Copy

4
3 1 4 1

output

Copy

Alice

Note

In the first example, each player can only remove stones from one pile (22=122=1). Alice loses, since Bob can copy whatever Alice does on the other pile, so Alice will run out of moves first.

In the second example, Alice can remove 22 stones from the first pile and 33 stones from the third pile on her first move to guarantee a win.

代码：

#include <bits/stdc++.h>
using namespace std;

const int inf = 0x3f3f3f3f;
int N;
int a[110];
int One;
set<int> s;

int main() {
    scanf("%d", &N);
    int minn = inf;
    One = 0;
    for(int i = 0; i < N; i ++) {
        scanf("%d", &a[i]);
        minn = min(minn, a[i]);
        s.insert(a[i]);
    }

    minn -= 1;
    for(int i = 0; i < N; i ++) {
        a[i] -= minn;
        if(a[i] == 1) One ++;
    }

    bool flag = false;
    if((int)s.size() == 1) {
        if(N % 2) flag = true;
        else flag = false;
    } else {
        if(One <= (N / 2)) flag = true;
        else flag = false;
    }

    if(flag) printf("Alice
");
    else printf("Bob
");

    return 0;
}