#include<iostream>
#include<cmath>
using namespace std;
const int N = 110;
const double esp = 1e-6;
int n;
double a[N][N];
int gauss()
{
    int r = 0, c = 0;
    for(; c < n; c++)
    {
        int t = r;
        for(int i = r; i < n; i++)
            if(fabs(a[i][c]) > fabs(a[t][c]))
                t = i;
        if(fabs(a[t][c]) < esp) continue;
        for(int i = c; i <= n; i++)
            swap(a[r][i], a[t][i]);
        for(int i = n; i >= c; i--)
            a[r][i] /= a[r][c];
        for(int i = r + 1; i < n; i++)
            if(fabs(a[i][c]) > esp)
                for(int j = n; j >= c; j--)
                    a[i][j] -= a[r][j] * a[i][c];
        r++;
    }
    if(r < n)
    {
        for(int i = r; i < n; i++)
            if(fabs(a[i][n]) > esp)
                return 0;
        return 2;
    }
    for(int i = n - 1; i >= 0; i--)
        for(int j = i + 1; j < n; j++)
            a[i][n] -= a[j][n] * a[i][j];
    return 1;
}
int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
        for(int j = 0; j <= n; j++)
            cin >> a[i][j];
    int t = gauss();
    if(t == 0) cout << "No solution";
    else if(t == 1)
    {
        for(int i = 0; i < n; i++)
            printf("%.2lf\n", a[i][n]);
    }
    else cout << "Infinite group solutions";
    return 0;
}

#include<iostream>
using namespace std;
const int N = 55;
int n, m, a[N][N], dp[N + N][N][N];
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin >> a[i][j];
    for(int i = 2; i <= n + m; i++)
        for(int j = 1; j < i; j++)
            for(int k = 1; k < i; k++)
            {
                int &s = dp[i][j][k];
                int j1 = i - j, k1 = i - k, t = a[j][j1];
                if(j != k) t += a[k][k1];
                s = max(s, dp[i - 1][j - 1][k - 1] + t);
                s = max(s, dp[i - 1][j - 1][k] + t);
                s = max(s, dp[i - 1][j][k - 1] + t);
                s = max(s, dp[i - 1][j][k] + t);
            }
    cout << dp[n + m][n][n];
    return 0;
}

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 15;
int a[N][N], dp[N + N][N][N], n;
int main()
{
    cin >> n;
    int x, y, z;
    while(cin >> x >> y >> z, x || y || z) a[x][y] = z;
    for(int i = 2; i <= n + n; i++)
        for(int j = 1; j <= n; j++)
            for(int k = 1; k <= n; k++)
            {
                int &s = dp[i][j][k];
                int j1 = i - j, k1 = i - k, t = a[j][j1];
                if(j != k) t += a[k][k1];
                s = max(s, dp[i - 1][j - 1][k - 1] + t);
                s = max(s, dp[i - 1][j - 1][k] + t);
                s = max(s, dp[i - 1][j][k - 1] + t);
                s = max(s, dp[i - 1][j][k] + t);
            }
    cout << dp[n + n][n][n];
    return 0;
}

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 5010;

int s[N][N];

int main()
{
    int n, R;
    scanf("%d%d", &n, &R);
    R = min(R, 5001);

    for (int i = 0; i < n; i ++ )
    {
        int x, y, w;
        scanf("%d%d%d", &x, &y, &w);
        x ++, y ++ ;
        s[x][y] += w;
    }

    for (int i = 1; i <= 5001; i ++ )
        for (int j = 1; j <= 5001; j ++ )
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];

    int res = 0;
    for (int i = R; i <= 5001; i ++ )
        for (int j = R; j <= 5001; j ++ )
            res = max(res, s[i][j] - s[i - R][j] - s[i][j - R] + s[i - R][j - R]);

    printf("%d\n", res);

    return 0;
}

#include<iostream>
#include<vector>
using namespace std;
const int N = 14, M = 1 << 12, mod = 1e8;
int n, m, dp[N][M], g[N];
vector<int> h[M], st;
bool check(int s)
{
    for(int i = 0; i < m; i++)
        if(s >> i & 1 && s >> i + 1 & 1)
            return false;
    return true;
}
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 0; j < m; j++)
        {
            int a;
            cin >> a;
            g[i] += !a << j;
        }
    for(int i = 0; i < 1 << m; i++)
        if(check(i)) st.push_back(i);
    for(int i = 0; i < st.size(); i++)
        for(int j = 0; j < st.size(); j++)
        {
            int a = st[i], b = st[j];
            if((a & b) == 0)
                h[i].push_back(j);
        }
    dp[0][0] = 1;
    for(int i = 1; i <= n + 1; i++)
        for(int j = 0; j < st.size(); j++)
            for(auto k : h[j])
            {
                if(st[j] & g[i]) continue;
                dp[i][j] = (dp[i][j] + dp[i - 1][k]) % mod;
            }
    cout << dp[n + 1][0];
    return 0;
}

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 12, M = N * N;
vector<int> h[1 << N], st;
int n, m, cnt[1 << N];
ll dp[N][M][1 << N];
bool check(int s)
{
    for(int i = 0; i < n; i++)
        if((s >> i & 1) && (s >> i + 1 & 1))
            return false;
    return true;
}
int count(int s)
{
    int res = 0;
    for(int i = 0; i < n; i++)
        res += (s >> i & 1);
    return res;
}
int main()
{
    cin >> n >> m;
    for(int i = 0; i < 1 << n; i++)
        if(check(i))
        {
            st.push_back(i);
            cnt[i] = count(i);
        }
    for(int i = 0; i < st.size(); i++)
        for(int j = 0; j < st.size(); j++)
        {
            int a = st[i], b = st[j];
            if((a & b) == 0 && check(a | b))
                h[i].push_back(j);
        }
    dp[0][0][0] = 1;
    for(int i = 1; i <= n + 1; i++)
        for(int j = 0; j <= m; j++)
            for(int k = 0; k < st.size(); k++)
                for(auto b : h[k])
                {
                    int c = cnt[st[k]];
                    if(j >= c)
                        dp[i][j][k] += dp[i - 1][j - c][b];
                }
    cout << dp[n + 1][m][0];
    return 0;
}

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N = 1e3 + 5;
char a[N][N];
int d[N][N], n, m;
int dx[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
struct point {int x, y;};
queue<point> q;
int main()
{
    cin >> n >> m;
    memset(d, 0x3f, sizeof d);
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
        {
            if(a[i][j] == '1')
            {
                q.push({i, j});
                d[i][j] = 0;
            }
        }
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        for(int i = 0; i < 4; i++)
        {
            int x = t.x + dx[i][0], y = t.y + dx[i][1];
            if(x < 0 || x >= n || y < 0 || y >= m) continue;
            if(d[x][y] > d[t.x][t.y] + 1)
            {
                d[x][y] = d[t.x][t.y] + 1;
                q.push({x, y});
            }
        }
    }
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
            cout << d[i][j] << ' ';
        cout << endl;
    }
    return 0;
}

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 10000;
int a[N];
int main()
{
    int t, m, n, x;
    cin >> t;
    while(t--)
    {
        int cnt = 0;
        cin >> m >> n;
        int k = n + 1 >> 1;
        cout << m << ' ' << k << endl;
        priority_queue<int, vector<int>, greater<int>> r;
        priority_queue<int> l;
        for(int i = 1; i <= n; i++)
        {
            cin >> x;
            if(r.empty() || r.top() < x) r.push(x);
            else l.push(x);
            if(r.size() > l.size() + 1)
            {
                l.push(r.top());
                r.pop();
            }
            if(l.size() > r.size())
            {
                r.push(l.top());
                l.pop();
            }
            if(i & 1) 
            {
                cout << r.top() << ' ';
                cnt++;
                if(cnt % 10 == 0 && i != n) cout << endl;
            }

        }
        if(t >= 1) cout << endl;
    }
    return 0;
}

#include<iostream>
#include<cmath>
using namespace std;
int a[100005];
int main()
{
    int n, i;
    cin >> n;
    for(i = 1; i <= n; i++) cin >> a[i];
    long long p = 0, q = 0;
    for(i = 2; i <= n; i++)
    {
        int x = a[i] - a[i - 1];
        if(x > 0) p += x;
        else q -= x;
    }
    cout << max(p, q) << endl << abs(p - q) + 1;
    return 0;
}

#include<iostream>
using namespace std;
int main()
{
    long long a, b, p, res = 0;
    cin >> a >> b >> p;
    while(b)
    {
        if(b & 1) res = (res + a) % p;
        a = (a + a) % p;
        b >>= 1;
    }
    cout << res % p;
    return 0;
}