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

using namespace std;

typedef long long LL;

const int N = 3;

int n, m;

void mul(int c[], int a[], int b[][N])
{
    int temp[N] = {0};
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            temp[i] = (temp[i] + (LL)a[j] * b[j][i]) % m;

    memcpy(c, temp, sizeof temp);
}

void mul(int c[][N], int a[][N], int b[][N])
{
    int temp[N][N] = {0};
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            for (int k = 0; k < N; k ++ )
                temp[i][j] = (temp[i][j] + (LL)a[i][k] * b[k][j]) % m;

    memcpy(c, temp, sizeof temp);
}

int main()
{
    cin >> n >> m;

    int f1[N] = {1, 1, 1};
    int a[N][N] = {
        {0, 1, 0},
        {1, 1, 1},
        {0, 0, 1}
    };

    n -- ;
    while (n)
    {
        if (n & 1) mul(f1, f1, a);  // res = res * a
        mul(a, a, a);  // a = a * a
        n >>= 1;
    }

    cout << f1[2] << endl;

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 300000;
const double PI = acos(-1);

struct Complex
{
    double x, y;
    Complex operator+ (const Complex& t) const
    {
        return {x + t.x, y + t.y};
    }
    Complex operator- (const Complex& t) const
    {
        return {x - t.x, y - t.y};
    }
    Complex operator* (const Complex& t) const
    {
        return {x * t.x - y * t.y, x * t.y + y * t.x};
    }
}a[N], b[N];
char s1[N], s2[N];
int res[N];
int rev[N], bit, tot;

void fft(Complex a[], int inv)
{
    for (int i = 0; i < tot; i ++ )
        if (i < rev[i])
            swap(a[i], a[rev[i]]);
    for (int mid = 1; mid < tot; mid *= 2)
    {
        auto w1 = Complex({cos(PI / mid), inv * sin(PI / mid)});
        for (int i = 0; i < tot; i += mid * 2)
        {
            auto wk = Complex({1, 0});
            for (int j = 0; j < mid; j ++, wk = wk * w1)
            {
                auto x = a[i + j], y = wk * a[i + j + mid];
                a[i + j] = x + y, a[i + j + mid] = x - y;
            }
        }
    }
}

int main()
{
    scanf("%s%s", s1, s2);
    int n = strlen(s1) - 1, m = strlen(s2) - 1;
    for (int i = 0; i <= n; i ++ ) a[i].x = s1[n - i] - '0';
    for (int i = 0; i <= m; i ++ ) b[i].x = s2[m - i] - '0';
    while ((1 << bit) < n + m + 1) bit ++ ;
    tot = 1 << bit;
    for (int i = 0; i < tot; i ++ )
        rev[i] = ((rev[i >> 1] >> 1)) | ((i & 1) << (bit - 1));
    fft(a, 1), fft(b, 1);
    for (int i = 0; i < tot; i ++ ) a[i] = a[i] * b[i];
    fft(a, -1);

    int k = 0;
    for (int i = 0, t = 0; i < tot || t; i ++ )
    {
        t += a[i].x / tot + 0.5;
        res[k ++ ] = t % 10;
        t /= 10;
    }

    while (k > 1 && !res[k - 1]) k -- ;
    for (int i = k - 1; i >= 0; i -- ) printf("%d", res[i]);

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>

#define x first
#define y second

using namespace std;

typedef long double LD;
typedef pair<int, int> PII;
typedef pair<LD, LD> PDD;
const int N = 10010;
const LD eps = 1e-18;

int n, cnt;
struct Line
{
    PDD st, ed;
    vector<int> ids;
}line[N];
int ki[N], vi[N];
int q[N], ans[N];

PDD operator-(PDD a, PDD b)
{
    return {a.x - b.x, a.y - b.y};
}

int sign(LD x)
{
    if (fabs(x) < eps) return 0;
    if (x < 0) return -1;
    return 1;
}

int dcmp(LD x, LD y)
{
    if (fabs(x - y) < eps) return 0;
    if (x < y) return -1;
    return 1;
}

LD cross(PDD a, PDD b)
{
    return a.x * b.y - a.y * b.x;
}

LD area(PDD a, PDD b, PDD c)
{
    return cross(b - a, c - a);
}

LD get_angle(const Line& a)
{
    return atan2(a.ed.y - a.st.y, a.ed.x - a.st.x);
}

bool cmp(const Line& a, const Line& b)
{
    LD A = get_angle(a), B = get_angle(b);
    if (!dcmp(A, B)) return area(a.st, a.ed, b.ed) < 0;
    return A < B;
}

PDD get_line_intersection(PDD p, PDD v, PDD q, PDD w)
{
    auto u = p - q;
    LD t = cross(w, u) / cross(v, w);
    return {p.x + v.x * t, p.y + v.y * t};
}

PDD get_line_intersection(Line& a, Line& b)
{
    return get_line_intersection(a.st, a.ed - a.st, b.st, b.ed - b.st);
}

// 判断bc的交点是否在a的右侧
bool on_right(Line& a, Line& b, Line& c)
{
    auto o = get_line_intersection(b, c);
    return area(a.st, a.ed, o) < 0;
}

void half_plane_intersection()
{
    sort(line, line + cnt, cmp);
    int hh = 0, tt = -1;
    for (int i = 0; i < cnt; i ++ )
    {
        if (i && !dcmp(get_angle(line[i - 1]), get_angle(line[i]))) continue;
        while (hh + 1 <= tt && on_right(line[i], line[q[tt - 1]], line[q[tt]])) tt -- ;
        while (hh + 1 <= tt && on_right(line[i], line[q[hh]], line[q[hh + 1]])) hh ++ ;
        q[ ++ tt] = i;
    }
    while (hh + 1 <= tt && on_right(line[q[hh]], line[q[tt - 1]], line[q[tt]])) tt -- ;
    while (hh + 1 <= tt && on_right(line[q[tt]], line[q[hh]], line[q[hh + 1]])) hh ++ ;

    int k = 0;
    for (int i = hh; i <= tt; i ++ )
        for (auto id: line[q[i]].ids)
            ans[k ++ ] = id;
    sort(ans, ans + k);

    printf("%d\n", k);
    for (int i = 0; i < k; i ++ ) printf("%d ", ans[i]);
    puts("");
}

int main()
{
    map<PII, vector<int>> ids;
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &ki[i]);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &vi[i]);
    for (int i = 1; i <= n; i ++ )
        ids[{ki[i], vi[i]}].push_back(i);

    line[cnt ++ ] = {{0, 10000}, {0, 0}};
    line[cnt ++ ] = {{0, 0}, {10000, 0}};
    for (auto& [k, v]: ids)
        line[cnt ++ ] = {{0, k.x}, {1, k.x + k.y}, v};

    half_plane_intersection();
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

#define x first
#define y second

using namespace std;

typedef pair<double,double> PDD;
const int N = 510;
const double eps = 1e-8;

int cnt;
struct Line
{
    PDD st, ed;
}line[N];
PDD pg[N], ans[N];
int q[N];

int sign(double x)
{
    if (fabs(x) < eps) return 0;
    if (x < 0) return -1;
    return 1;
}

int dcmp(double x, double y)
{
    if (fabs(x - y) < eps) return 0;
    if (x < y) return -1;
    return 1;
}

double get_angle(const Line& a)
{
    return atan2(a.ed.y - a.st.y, a.ed.x - a.st.x);
}

PDD operator-(PDD a, PDD b)
{
    return {a.x - b.x, a.y - b.y};
}

double cross(PDD a, PDD b)
{
    return a.x * b.y - a.y * b.x;
}

double area(PDD a, PDD b, PDD c)
{
    return cross(b - a, c - a);
}

bool cmp(const Line& a, const Line& b)
{
    double A = get_angle(a), B = get_angle(b);
    if (!dcmp(A, B)) return area(a.st, a.ed, b.ed) < 0;
    return A < B;
}

PDD get_line_intersection(PDD p, PDD v, PDD q, PDD w)
{
    auto u = p - q;
    double t = cross(w, u) / cross(v, w);
    return {p.x + v.x * t, p.y + v.y * t};
}

PDD get_line_intersection(Line a, Line b)
{
    return get_line_intersection(a.st, a.ed - a.st, b.st, b.ed - b.st);
}

// bc的交点是否在a的右侧
bool on_right(Line& a, Line& b, Line& c)
{
    auto o = get_line_intersection(b, c);
    return sign(area(a.st, a.ed, o)) <= 0;
}

double half_plane_intersection()
{
    sort(line, line + cnt, cmp);
    int hh = 0, tt = -1;
    for (int i = 0; i < cnt; i ++ )
    {
        if (i && !dcmp(get_angle(line[i]), get_angle(line[i - 1]))) continue;
        while (hh + 1 <= tt && on_right(line[i], line[q[tt - 1]], line[q[tt]])) tt -- ;
        while (hh + 1 <= tt && on_right(line[i], line[q[hh]], line[q[hh + 1]])) hh ++ ;
        q[ ++ tt] = i;
    }
    while (hh + 1 <= tt && on_right(line[q[hh]], line[q[tt - 1]], line[q[tt]])) tt -- ;
    while (hh + 1 <= tt && on_right(line[q[tt]], line[q[hh]], line[q[hh + 1]])) hh ++ ;

    q[ ++ tt] = q[hh];
    int k = 0;
    for (int i = hh; i < tt; i ++ )
        ans[k ++ ] = get_line_intersection(line[q[i]], line[q[i + 1]]);
    double res = 0;
    for (int i = 1; i + 1 < k; i ++ )
        res += area(ans[0], ans[i], ans[i + 1]);
    return res / 2;
}

int main()
{
    int n, m;
    scanf("%d", &n);
    while (n -- )
    {
        scanf("%d", &m);
        for (int i = 0; i < m; i ++ ) scanf("%lf%lf", &pg[i].x, &pg[i].y);
        for (int i = 0; i < m; i ++ )
            line[cnt ++ ] = {pg[i], pg[(i + 1) % m]};
    }
    double res = half_plane_intersection();
    printf("%.3lf\n", res);

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

#define x first
#define y second
using namespace std;

typedef pair<double, double> PDD;
const double eps = 1e-12, PI = acos(-1);
const int N = 50001;

PDD q[N];
int n;
struct circle{
    PDD p;
    double r;
};

int sign(double x){
    if(fabs(x) < eps) return 0;
    if(x < 0) return -1;
    return 1;
}

int dcmp(double x, double y){
    if(fabs(x - y) < eps) return 0;
    if(x < y) return -1;
     return 1;
}

PDD operator+ (PDD a, PDD b){
    return {a.x + b.x, a.y + b.y};
}

PDD operator- (PDD a, PDD b){
    return {a.x - b.x, a.y - b.y};
}

PDD operator* (PDD a, double t){
    return {a.x * t, a.y * t};
}

PDD operator/ (PDD a, double t){
    return {a.x / t, a.y / t};
}

double operator* (PDD a, PDD b){
    return a.x * b.y - a.y * b.x;
}

PDD rotate(PDD a, double b){
    return {a.x * cos(b) + a.y * sin(b), -a.x * sin(b) + a.y * cos(b)};
}

double dist(PDD a, PDD b){
    double dx = a.x - b.x, dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}

PDD line(PDD p, PDD v, PDD q, PDD w){
    auto u = p - q;
    double t = w * u / (v * w);
    return p + v * t;
}

pair<PDD, PDD> get(PDD a, PDD b){
    return {(a + b) / 2, rotate(b - a, PI / 2)};
}

circle circ(PDD a, PDD b, PDD c){
    auto u = get(a, b), v = get(a, c);
    auto p = line(u.x, u.y, v.x, v.y);
    return {p, dist(p, a)};
}

int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%lf%lf", &q[i].x, &q[i].y);
    double a, p;
    scanf("%lf%lf", &a, &p);
    for(int i = 0; i < n; i++){
        q[i] = rotate(q[i], a / 180 * PI);
        q[i].x /= p;
    }
    random_shuffle(q, q + n);
    circle c({q[0], 0});
    for(int i = 1; i < n; i++){
        if(dcmp(c.r, dist(c.p, q[i])) < 0){
            c = {q[i], 0};
            for(int j = 0; j < i; j++){
                if(dcmp(c.r, dist(c.p, q[j])) < 0){
                    c = {(q[i] + q[j]) / 2, dist(q[i], q[j]) / 2};
                    for(int k = 0; k < j; k++){
                        if(dcmp(c.r, dist(c.p, q[k])) < 0){
                            c = circ(q[i], q[j], q[k]);
                        }
                    }
                }
            }
        }
    }
    printf("%.3lf\n", c.r);
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

#define x first
#define y second
using namespace std;

typedef pair<double, double> PDD;
const int N = 1e5 + 1;
const double eps = 1e-12;
const double PI = acos(-1);

int n;
PDD q[N];
struct circle{
    PDD p;
    double r;
};

int sign(double x){
    if(fabs(x) < eps) return 0;
    if(x < 0) return -1;
    return 1;
}

int dcmp(double x, double y){
    return fabs(x - y) < eps ? 0 : (x < y ? -1 : 1);
}

PDD operator- (PDD a, PDD b){
    return {a.x - b.x, a.y - b.y};
}

PDD operator+ (PDD a, PDD b){
    return {a.x + b.x, a.y + b.y};
}

PDD operator* (PDD a, double t){
    return {a.x * t, a.y * t};
}

PDD operator/ (PDD a, double t){
    return {a.x / t, a.y / t};
}

double operator* (PDD a, PDD b){
    return a.x * b.y - a.y * b.x;
}

PDD sect(PDD p, PDD v, PDD q, PDD w){
    auto u = p - q;
    double t = w * u / (v * w);
    return p + v * t;
}

PDD rotate(PDD a, double b){
    return {a.x * cos(b) + a.y * sin(b), -a.x * sin(b) + a.y * cos(b)};
}

pair<PDD, PDD> line(PDD a, PDD b){
    return {(a + b) / 2, rotate(b - a, PI / 2)};
}

double dist(PDD a, PDD b){
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}

circle get(PDD a, PDD b, PDD c){
    auto u = line(a, b), v = line(a, c);
    auto p = sect(u.x, u.y, v.x, v.y);
    return {p, dist(p, a)};
}

int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%lf%lf", &q[i].x, &q[i].y);
    random_shuffle(q, q + n);
    circle c = {q[0], 0};
    for(int i = 1; i < n; i++){
        if(dcmp(c.r, dist(c.p, q[i])) < 0){
            c = {q[i], 0};
            for(int j = 0; j < i; j++){
                if(dcmp(c.r, dist(c.p, q[j])) < 0){
                    c = {(q[i] + q[j]) / 2, dist(q[i], q[j]) / 2};
                    for(int k = 0; k < j; k++){
                        if(dcmp(c.r, dist(c.p, q[k])) < 0){
                            c = get(q[i], q[j], q[k]);
                        }
                    }
                }
            }
        }
    }
    printf("%.10lf\n", c.r);
    printf("%.10lf %.10lf", c.p.x, c.p.y);
    return 0;
}

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

using namespace std;

// 注意这里视频中的写法是 M = 150010，数组会越界，可以改成M = N * 3 + 10。
const int N = 50010, M = N * 3 + 10;

int n;
int h[N], e[M], w[M], ne[M], idx;
int dist[N];
int q[N];
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void spfa()
{
    memset(dist, -0x3f, sizeof dist);
    dist[0] = 0;
    st[0] = true;
    int hh = 0, tt = 1;
    q[0] = 0;

    while (hh != tt)
    {
        int t = q[hh ++ ];
        if (hh == N) hh = 0;
        st[t] = false;

        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] < dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j])
                {
                    q[tt ++ ] = j;
                    if (tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }
}

int main()
{
    scanf("%d", &n);

    memset(h, -1, sizeof h);
    for (int i = 1; i < N; i ++ )
    {
        add(i - 1, i, 0);
        add(i, i - 1, -1);
    }

    for (int i = 0; i < n; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        a ++, b ++ ;
        add(a - 1, b, c);
    }

    spfa();

    printf("%d\n", dist[50001]);

    return 0;
}

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

using namespace std;
typedef long long LL;

const int N = 1e5 + 1, M = N * 3;
int h[N], ne[M], e[M], w[M], cnt[N], q[N];
int n, m, idx;
bool st[N];
LL dist[N];

void add(int u, int v, int c){
    e[idx] = v, w[idx] = c, ne[idx] = h[u], h[u] = idx++;
}

bool spfa(){
    int hh = 0, tt = 1;
    memset(dist, -0x3f, sizeof dist);
    st[0] = true;
    dist[0] = 0;
    q[0] = 0;
    while(hh != tt){
        int t = q[--tt];
        if(hh == N) hh = 0;
        st[t] = false;
        for(int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            if(dist[j] < dist[t] + w[i]){
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if(cnt[j] >= n + 1) return false;
                if(!st[j]){
                    q[tt++] = j;
                    st[j] = true;
                } 
            }
        }
    }
    return true;
}

int main(){
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    while(m--){
        int x, a, b;
        scanf("%d%d%d", &x, &a, &b);
        if(x == 1) add(a, b, 0), add(b, a, 0);
        else if(x == 2) add(a, b, 1);
        else if(x == 3) add(b, a, 0);
        else if(x == 4) add(b, a, 1);
        else add(a, b, 0);
    }
    for(int i = 1; i <= n; i++) add(0, i, 1);

    if(!spfa()) puts("-1");
    else{
        LL res = 0;
        for(int i = 1; i <= n; i++) res += dist[i];
        printf("%lld\n", res);
    }
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 25, M = 10;
int n, m;
int w[N], s[M];
double ans = 1e8;

double calc(){
    memset(s, 0, sizeof s);
    for(int i = 0; i < n; i++){
        int k = 0;
        for(int j = 0; j < m; j++){
            if(s[j] < s[k])
                k = j;
        }
        s[k] += w[i];
    }

    double avg = 0;
    for(int i = 0; i < m; i++) avg += s[i] * 1.0 / m;
    double res = 0;
    for(int i = 0; i < m; i++) res += (s[i] - avg) * (s[i] - avg);
    res = sqrt(res / m);
    ans = min(ans, res);
    return res;
}

void ysy(){
    random_shuffle(w, w + n);

    for(double t = 1e6; t >= 1e-6; t *= 0.99){
        int a = rand() % n, b = rand() % n;
        double x = calc();
        swap(w[a], w[b]);
        double y = calc();
        double delta = y - x;
        if(exp(-delta / t) < (double)rand() / RAND_MAX) swap(w[a], w[b]);
    }
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < n; i++) cin >> w[i];
    for(int i = 0; i < 100; i++) ysy();
    printf("%.2lf\n", ans);
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <ctime>

using namespace std;
#define x first
#define y second

typedef pair<int, int> PII;
const int N = 55;
PII q[N], p[N];
int n, m, ans;

int calc(){
    int res = 0;
    for(int i = 0; i < m; i++){
        res += q[i].x + q[i].y;
        if(i < n){
            if(q[i].x == 10) res += q[i + 1].x + q[i + 1].y;
            else if(q[i].x + q[i].y == 10) 
                res += q[i + 1].x;
        }
    }
    ans = max(ans, res);
    return res;
}

void simulate(){
    for(double t = 1e4; t > 1e-4; t *= 0.99){
        int a = rand() % m, b = rand() % m;
        int x = calc();
        swap(q[a], q[b]);
        if(n + (q[n - 1].x == 10) == m){
            int y = calc();
            int delta = y - x;
            if(exp(delta / t) < (double)rand() / RAND_MAX) swap(q[a], q[b]);
        } 
        else swap(q[a], q[b]);
    }
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i++) cin >> q[i].x >> q[i].y;
    if(q[n - 1].x == 10) m = n + 1, cin >> q[n].x >> q[n].y;
    else m = n;
    while((double)clock() / CLOCKS_PER_SEC < 0.8) simulate();
    cout << ans << endl;
    return 0;
}