cf----2019-10-06（Slime，Shashlik Cooking，Mysterious Crime）

城市黎明的灯火，总有光环在陨落，模仿者一个又一个，无人问津的角色，你选择去崇拜谁呢，怨恨谁呢？

 

There are nn slimes in a row. Each slime has an integer value (possibly negative or zero) associated with it.

Any slime can eat its adjacent slime (the closest slime to its left or to its right, assuming that this slime exists).

When a slime with a value xx eats a slime with a value yy, the eaten slime disappears, and the value of the remaining slime changes to x−yx−y.

The slimes will eat each other until there is only one slime left.

Find the maximum possible value of the last slime.

Input

The first line of the input contains an integer nn (1≤n≤5000001≤n≤500000) denoting the number of slimes.

The next line contains nn integers aiai (−109≤ai≤109−109≤ai≤109), where aiai is the value of ii-th slime.

Output

Print an only integer — the maximum possible value of the last slime.

Examples

input

Copy

4
2 1 2 1

output

Copy

4

input

Copy

5
0 -1 -1 -1 -1

output

Copy

4

Note

In the first example, a possible way of getting the last slime with value 44 is:

• Second slime eats the third slime, the row now contains slimes 2,−1,12,−1,1
• Second slime eats the third slime, the row now contains slimes 2,−22,−2
• First slime eats the second slime, the row now contains 44

In the second example, the first slime can keep eating slimes to its right to end up with a value of 44.

There are nn slimes in a row. Each slime has an integer value (possibly negative or zero) associated with it.

Any slime can eat its adjacent slime (the closest slime to its left or to its right, assuming that this slime exists).

When a slime with a value xx eats a slime with a value yy, the eaten slime disappears, and the value of the remaining slime changes to x−yx−y.

The slimes will eat each other until there is only one slime left.

Find the maximum possible value of the last slime.

Input

The first line of the input contains an integer nn (1≤n≤5000001≤n≤500000) denoting the number of slimes.

The next line contains nn integers aiai (−109≤ai≤109−109≤ai≤109), where aiai is the value of ii-th slime.

Output

Print an only integer — the maximum possible value of the last slime.

Examples

input

Copy

4
2 1 2 1

output

Copy

4

input

Copy

5
0 -1 -1 -1 -1

output

Copy

4

Note

In the first example, a possible way of getting the last slime with value 44 is:

• Second slime eats the third slime, the row now contains slimes 2,−1,12,−1,1
• Second slime eats the third slime, the row now contains slimes 2,−22,−2
• First slime eats the second slime, the row now contains 44

In the second example, the first slime can keep eating slimes to its right to end up with a value of 44.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <ctime>
#include <cctype>
#include <bitset>
#include <utility>
#include <sstream>
#include <complex>
#include <iomanip>
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
int n,flag = 0;
ll p[500010],jg = 0,mi = inf,mx = -inf;
int main()
{
    scanf("%d",&n);
    for(int i=0; i<n; i++)
    {
        scanf("%lld",&p[i]);
        jg += abs(p[i]);
        mi = min(mi, p[i]);
        mx = max(mx, p[i]);
    }
    if(n == 1)
        cout<<p[0]<<endl;
    else if(n == 2)
        cout<<max(p[0] - p[1],p[1] - p[0])<<endl;
    else
    {
        if(mi > 0)
            jg -= 2 * mi;
        else if(mx < 0)
            jg -= 2 * abs(mx);
        cout<<jg<<endl;
    }
    return 0;
}

Long story short, shashlik is Miroslav's favorite food. Shashlik is prepared on several skewers simultaneously. There are two states for each skewer: initial and turned over.

This time Miroslav laid out nn skewers parallel to each other, and enumerated them with consecutive integers from 11 to nn in order from left to right. For better cooking, he puts them quite close to each other, so when he turns skewer number ii, it leads to turning kk closest skewers from each side of the skewer ii, that is, skewers number i−ki−k, i−k+1i−k+1, ..., i−1i−1, i+1i+1, ..., i+k−1i+k−1, i+ki+k (if they exist).

For example, let n=6n=6 and k=1k=1. When Miroslav turns skewer number 33, then skewers with numbers 22, 33, and 44 will come up turned over. If after that he turns skewer number 11, then skewers number 11, 33, and 44 will be turned over, while skewer number 22 will be in the initial position (because it is turned again).

As we said before, the art of cooking requires perfect timing, so Miroslav wants to turn over all nn skewers with the minimal possible number of actions. For example, for the above example n=6n=6 and k=1k=1, two turnings are sufficient: he can turn over skewers number 22 and 55.

Help Miroslav turn over all nn skewers.

Input

The first line contains two integers nn and kk (1≤n≤10001≤n≤1000, 0≤k≤10000≤k≤1000) — the number of skewers and the number of skewers from each side that are turned in one step.

Output

The first line should contain integer ll — the minimum number of actions needed by Miroslav to turn over all nn skewers. After than print llintegers from 11 to nn denoting the number of the skewer that is to be turned over at the corresponding step.

Examples

input

Copy

7 2

output

Copy

2
1 6

input

Copy

5 1

output

Copy

2
1 4

Note

In the first example the first operation turns over skewers 11, 22 and 33, the second operation turns over skewers 44, 55, 66 and 77.

In the second example it is also correct to turn over skewers 22 and 55, but turning skewers 22 and 44, or 11 and 55 are incorrect solutions because the skewer 33 is in the initial state after these operations.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <ctime>
#include <cctype>
#include <bitset>
#include <utility>
#include <sstream>
#include <complex>
#include <iomanip>
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
int n,k,a[1010],ct;
int main()
{
    scanf("%d%d",&n,&k);
    if(!k)
    {
        ct=n;
        for(int i=1; i<=n; i++)
            a[i]=i;
    }
    else if(n<=(2*k+1))
    {
        ct=1;
        a[1]=n/2+1;
    }
    else if(n>(2*k+1))
    {
        if(n%(2*k+1)>k||!(n%(2*k+1)))
        {
            ct=0;
            for(int i=k+1; i<=n; i+=(2*k+1))
                a[++ct]=i;
        }
        else
        {
            ct=0;
            for(int i=1; i<=n; i+=(2*k+1))
                a[++ct]=i;
        }
    }
    printf("%d\n",ct);
    for(int i=1; i<=ct; i++)
        printf("%d ",a[i]);
    return 0;
}

Acingel is a small town. There was only one doctor here — Miss Ada. She was very friendly and nobody has ever said something bad about her, so who could've expected that Ada will be found dead in her house? Mr Gawry, world-famous detective, is appointed to find the criminal. He asked mm neighbours of Ada about clients who have visited her in that unlucky day. Let's number the clients from 11 to nn. Each neighbour's testimony is a permutation of these numbers, which describes the order in which clients have been seen by the asked neighbour.

However, some facts are very suspicious – how it is that, according to some of given permutations, some client has been seen in the morning, while in others he has been seen in the evening? "In the morning some of neighbours must have been sleeping!" — thinks Gawry — "and in the evening there's been too dark to see somebody's face...". Now he wants to delete some prefix and some suffix (both prefix and suffix can be empty) in each permutation, so that they'll be non-empty and equal to each other after that — some of the potential criminals may disappear, but the testimony won't stand in contradiction to each other.

In how many ways he can do it? Two ways are called different if the remaining common part is different.

Input

The first line contains two integers nn and mm (1≤n≤1000001≤n≤100000, 1≤m≤101≤m≤10) — the number of suspects and the number of asked neighbors.

Each of the next mm lines contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤n1≤ai≤n). It is guaranteed that these integers form a correct permutation (that is, each number from 11 to nn appears exactly once).

Output

Output a single integer denoting the number of ways to delete some prefix and some suffix of each permutation (possibly empty), such that the remaining parts will be equal and non-empty.

Examples

input

Copy

3 2
1 2 3
2 3 1

output

Copy

4

input

Copy

5 6
1 2 3 4 5
2 3 1 4 5
3 4 5 1 2
3 5 4 2 1
2 3 5 4 1
1 2 3 4 5

output

Copy

5

input

Copy

2 2
1 2
2 1

output

Copy

2

Note

In the first example, all possible common parts are [1][1], [2][2], [3][3] and [2,3][2,3].

In the second and third examples, you can only leave common parts of length 11.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <ctime>
#include <cctype>
#include <bitset>
#include <utility>
#include <sstream>
#include <complex>
#include <iomanip>
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
int n,m;
int a[15][100010],p[100010];
ll jg,ct;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1; i<=m; i++)
    {
        for(int j=1; j<=n; j++)
        {
            scanf("%d",&p[j]);
            a[i][p[j]]=p[j-1];
        }
    }
    for(int i=2; i<=n; i++)
    {
        int j;
        for(j=1; j<m; j++)
        {
            if(a[m][p[i]]!=a[j][p[i]])
                break;
        }
        if(j==m)
        {
            ct++;
            jg+=ct;
        }
        else
            ct=0;
    }
    printf("%lld\n",jg+n);
    return 0;
}