akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace Tasks
{
    public class D
    {
        static void Main(string[] args)
        {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            Solve();
            Console.Out.Flush();
        }

        public static void Solve()
        {
            var (N, K) = Scanner.Scan<int, long>();
            var A = Scanner.ScanEnumerable<int>().Select(x => x - 1).ToArray();
            var dict = new Dictionary<int, int>();
            var current = 0;
            var loopStart = -1;
            var loopEnd = -1;
            var order = new List<int>();
            for (var i = 0; i <= K; i++)
            {
                if (dict.ContainsKey(current))
                {
                    loopStart = dict[current];
                    loopEnd = i;
                    break;
                }
                order.Add(current + 1);
                dict[current] = i;
                current = A[current];
            }

            if (loopStart == -1)
            {
                Console.WriteLine(order.Last());
                return;
            }


            K -= loopStart;
            K %= loopEnd - loopStart;
            var answer = order[loopStart + (int)K];
            Console.WriteLine(answer);
        }

        public static class Scanner
        {
            private static Queue<string> queue = new Queue<string>();
            public static T Next<T>()
            {
                if (!queue.Any()) foreach (var item in Console.ReadLine().Trim().Split(" ")) queue.Enqueue(item);
                return (T)Convert.ChangeType(queue.Dequeue(), typeof(T));
            }
            public static T Scan<T>() => Next<T>();
            public static (T1, T2) Scan<T1, T2>() => (Next<T1>(), Next<T2>());
            public static (T1, T2, T3) Scan<T1, T2, T3>() => (Next<T1>(), Next<T2>(), Next<T3>());
            public static (T1, T2, T3, T4) Scan<T1, T2, T3, T4>() => (Next<T1>(), Next<T2>(), Next<T3>(), Next<T4>());
            public static (T1, T2, T3, T4, T5) Scan<T1, T2, T3, T4, T5>() => (Next<T1>(), Next<T2>(), Next<T3>(), Next<T4>(), Next<T5>());
            public static IEnumerable<T> ScanEnumerable<T>() => Console.ReadLine().Trim().Split(" ").Select(x => (T)Convert.ChangeType(x, typeof(T)));
        }
    }
}


Measured memory_bytes: 58640
#include "bits/stdc++.h"
using namespace std;
//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1325
inline bool check(int p, int q, int m, int n) {
	return (m*p + n*q + m*m+n*n) % (m*m + n*n) == 0 && (m*q - n *p +m*m+n*n) % (m*m + n*n) == 0;
}

int main() {
	cin.tie(0); ios::sync_with_stdio(false);
	int N; cin >> N;
	for (int i = 0;i < N;i++) {
		int p, q; cin >> p >> q;
		int cnt = 0;
		int G = p * p + q * q;
		for (int m = 0; m*m <= G;m++) {
			for (int n = 0; m*m + n*n <= G;n++) {
				if (m*m + n*n == 0) continue;

				if (check(p, q, m, n)) cnt++;
				if (n != 0 && check(p, q, m, -n)) cnt++;
				if (m != 0 && check(p, q, -m, n)) cnt++;
				if (m != 0 && n != 0 && check(p, q, -m, -n))cnt++;
			}
		}

		if (cnt == 8) cout << "P" << endl;
		else cout << "C" << endl;

	}
}

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(long i = 0; i < n; i++)
#define erep(i, n) for(long i = 1; i <= n; i++)
const long MOD = 1000000007;

int main() {string s;
cin >> s;
long N = s.size();
long x = 0; long y = 0;
rep(i, N){
    if(s.at(i) == 'g') x++;
    else y++;
}
long ans;
if((x + y) % 2 == 0){
    ans = (x + y) / 2 - y;
}
else{
    ans = (x + y - 1) / 2 - y;
}

cout << ans << endl;
  return 0;
 
}



Measured memory_bytes: 512
#料理が2個の時を考え、どちらを取れば良いか考える　これで得られた基準でソート
import sys
input = sys.stdin.readline

N = int(input())
AB = [tuple(map(int, input().split())) for _ in range(N)]
AB.sort(key=lambda k: k[0]+k[1], reverse=True)
takahashi, aoki = 0, 0

for i in range(N):
    if i%2==0:
        takahashi += AB[i][0]
    else:
        aoki += AB[i][1]

print(takahashi-aoki)

Measured memory_bytes: 58460
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	int num=0;
	cin>>n;
	int x1,x2;
	for(int i=1;i<=n;i++){
		cin>>x1>>x2;
		if(x1==x2){
			num++;
		}
		else{
			num=0;
		}
		if(num>=3){
			cout<<"Yes";
			return 0;
		}
	}
	cout<<"No";
}

Measured memory_bytes: 3584
<?php
list($n, $blue, $red) = explode(' ', trim(fgets(STDIN)));

$count = $blue + $red;
if($count == 0 || $blue == 0){
 echo 0;
 exit;
}

$p = (int)floor($n / $count);

$m = $n - ($p * $count);

$sum = $p * $blue;

if($m > $blue){
 $sum += $blue;
}else{
 $sum += $m;
}

echo $sum;
?>


Measured memory_bytes: 4856
#ifdef LOCAL
  #define debug_echo(expr) cout << expr;
#else
  #define debug_echo(expr)
#endif

#define rep(i, n) for (int i = 0; i < n; i++)

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
using namespace std;

template<class T>
ostream& operator <<(ostream& out, const vector<T>& v) {
    out << "[";
    bool isfirst = false;
    for (const T& e : v) {
        out << (isfirst ? ", " : "") << e;
        isfirst = true;
    }
    out << "]";
    return out;
}
template<class T>
ostream& operator <<(ostream& out, const set<T>& s) {
    out << "{";
    bool isfirst = false;
    for (const T& e : s) {
        out << (isfirst ? ", " : "") << e;
        isfirst = true;
    }
    out << "}";
    return out;
}
template<class A, class B>
ostream& operator <<(ostream& out, const pair<A, B>& p) {
    out << "(" << p.first << ", " << p.second << ")";
    return out;
}
template<class K, class V>
ostream& operator <<(ostream& out, const map<K, V>& s) {
    out << "{";
    bool isfirst = false;
    for (const auto& e : s) {
        out << (isfirst ? ", " : "") << e;
        isfirst = true;
    }
    out << "}";
    return out;
}

//
// Implementation
//

vector<int> pointsA(4);
vector<int> pointsB(2);

int main() {
    rep (i, 4) {
        cin >> pointsA[i];
    }
    rep (i, 2) {
        cin >> pointsB[i];
    }
    sort(pointsA.begin(), pointsA.end());
    sort(pointsB.begin(), pointsB.end());
    cout << pointsA[3] + pointsA[2] + pointsA[1] + pointsB[1] << endl;
}

Measured memory_bytes: 3156
from sys import exit

n = int(input())
l = [list(map(int, input().split())) for _ in range(n)]

l.insert(0, [0, 0, 0])
for i in range(n):
    t1, x1, y1 = l[i]
    t2, x2, y2 = l[i+1]
    d = abs(x2 - x1) + abs(y2 - y1)
    t = t2 - t1
    if d > t or (d + t) % 2 == 1:
        print('No')
        exit()

print('Yes')

Measured memory_bytes: 90304
#include <iostream>

bool is_vowel(char c)
{
    switch (c)
    {
        case 'a':
        case 'e':
        case 'i':
        case 'o':
        case 'u':   return true;
        default:    return false;
    }
}

int main(void)
{
    char c;
    std::cin >> c;
    bool vowel = is_vowel(c);
    std::cout << (vowel ? "vowel" : "consonant") << std::endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, srt, end) for (long long i = (srt); i < (long long)(end); i++)

int main(){
    ll k;
    vector<ll> a(5);
    rep(i, 0, 5) cin >> a[i];
    cin >> k;
    rep(i, 0, 4){
        rep(j, i+1, 5){
            if(a[j]-a[i] > k){
                cout << ":(" << endl;
                return 0;
            }
        }
    }
    cout << "Yay!" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)

int INF = 100000000;

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

  int ans = INF;
  for (int i = 1; i <= n / 2; i++) {
    vector<int> id(6);
    vector<int> jd(6);
    int k = i, j = n - i;

    rep (m, 6) {
      id[m] = k % 10;
      k /= 10;
      jd[m] = j % 10;
      j /= 10;
    }

    int sum = 0;
    rep (m, 6) sum += id[m] + jd[m];
    ans = min(ans, sum);
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

//Code Short
#define REP(i,n) for(int i = 0;i < n;++i)
#define PB(s) push_back(s)
#define DSORT(n) sort(n.begin(),n.end())
#define QECHO(n) cout << n
#define QECHOS(n) cout << n << " "

//Define Math
const double EPS = 1e-10;
const double PI  = acos(-1.0);

using namespace std;
typedef long long ll;
/* prototype */
int EDSum(ll);//各桁の和
vector<int> SOE(int,int);//素数 (Min,Max)
int MinCM(int,int);//最小公倍数(num1,num2)
int MaxCD(int,int);//最大公約数(num1,num2)
vector<int> igets(int);//cin * N
ll nPr(ll,ll); //(n,r)
ll nE(ll); //(n)
ll nCr(ll,ll); //(n,r)

void solve(){
    //START
    int a,b;
    cin >> a >> b;
    if(a==2)a=0;else if(a==4||a==6||a==9||a==11)a=1;else a=2;
    if(b==2)b=0;else if(b==4||b==6||b==9||b==11)b=1;else b=2;
    if(a == b)cout << "Yes" << endl; else cout << "No" << endl;
}

int main(void){cin.tie(0);ios::sync_with_stdio(false);solve();}
int EDSum(ll number) {
  int ans = 0;
  while (1) {
    ans += number % 10;
    number /= 10;
    if (number == 0) break;
  }
  return ans;
}

vector < int > SOE(int min, int max) {
  if (min < 2) min = 2;
  vector < int > int_array;
  for (int i = min; i <= max; i++) int_array.push_back(i);
  vector < int > sosu;
  double stop = sqrt(max);
  while (true) {
    sosu.push_back(int_array.front());
    int_array.erase(int_array.begin());
    if (stop < (double)(sosu.back())) break;
    for (int i = 0; i < (int) int_array.size(); i++) {
      if (int_array[i] % sosu.back() == 0)
        int_array.erase(int_array.begin() + i);
    }
  }
  sosu.insert(sosu.end(), int_array.begin(), int_array.end());
  return sosu;
}

int MinCM(int a, int b) {
  int c = a * b;
  if (a < b)
    swap(a, b);
  int r = a % b;
  while (r != 0) {
    a = b;
    b = r;
    r = a % b;
  }
  return c / b;
}

int MaxCD(int a, int b) {
  if (a < b)
    swap(a, b);
  int r = a % b;
  while (r != 0) {
    a = b;
    b = r;
    r = a % b;
  }
  return b;
}
vector < int > igets(int N) {
  vector < int > A;
  int temp;
  for (int i = 0; i < N; ++i) {
    cin >> temp;
    A.push_back(temp);
  }
  return A;
}

ll nPr(ll n, ll r) {
  ll ans = 1;
  r = n - r;
  while (n != r) {
    ans *= n;
    --n;
  }
  return ans;
}

ll nE(ll n) {
  return nPr(n, n);
}

ll nCr(ll n, ll r) {
  if (r == 0) return -1;
  else {
    if (0 != n - r && n - r < r) r = n - r;
    return nPr(n, r) / nE(r);
  }
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;

int main()
{
	string x;
	int sum = 0;

	while (true)
	{
		getline(cin, x);
		for (int i = 0; i < x.size(); i++)
		{
			sum += int(x[i]) - int('0');
		}
		if (x[0] == '0') break;
		if (sum != 0) cout << sum << endl;
		sum = 0;
	}

	
}


Measured memory_bytes: 3164
#include <bits/stdc++.h>

using namespace std;

#define INF 1001000100010001000
#define MOD 1000000007
#define EPS 1e-10
#define int long long
#define rep(i, N) for (int i = 0; i < N; i++)
#define Rep(i, N) for (int i = 1; i < N; i++)
#define For(i, a, b) for (int i = (a); i < (b); i++)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define vvi vector<vi >
#define vb vector<bool>
#define vvb vector<vb >
#define vp vector< pii >
#define all(a) (a).begin(), (a).end()
#define Int(x) int x; cin >> x;
#define int2(x, y) Int(x); Int(y);
#define int3(x, y, z) Int(x); int2(y, z);
#define in(x, a, b) ((a) <= (x) && (x) < (b))
#define fir first
#define sec second
#define ffir first.first
#define fsec first.second
#define sfir second.first
#define ssec second.second
#define Decimal fixed << setprecision(10)

//int dxy[5] = {0, 1, 0, -1, 0};
// cmd

signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    string st;
    cin >> st;
    
    sort(all(st));

    if (st[0] == st[1] && st[1] != st[2] &&
            st[2] == st[3]) {
        std::cout << "Yes" << std::endl;
    } else {
        std::cout << "No" << std::endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

string S;
string t[4] = {"maerd",
               "remaerd",
               "esare",
               "resare"};

int main()
{
    cin >> S;
    reverse(S.begin(), S.end());
    for (int i = 0; i < S.size();)
    {
        bool dividable = false;
        for (int j = 0; j < 4; j++)
        {
            if (S.substr(i, t[j].size()) == t[j])
            {
                dividable = true;
                i += t[j].size();
                break;
            }
        }
        if (!dividable)
        {
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;

    return 0;
}


Measured memory_bytes: 512
# -*- coding:utf-8 -*-
import numpy as np


def solve():
    H, W = list(map(int, input().split()))
    grid = []
    for i in range(H):
        s = input()
        grid.append(list(s))
    grid = (np.array(grid) == ".") * 1  # ランプを置ける:1, 置けない:0

    L = np.zeros((H,W), dtype=int)
    R = np.zeros((H,W), dtype=int)
    U = np.zeros((H,W), dtype=int)
    D = np.zeros((H,W), dtype=int)

    # 左を照らせる数を数える
    for w in range(W):
        if w == 0:
            L[:, w] = grid[:, w]
        else:
            L[:, w] = (L[:, w-1]+1) * grid[:, w]

    # 右
    for w in range(W-1, -1, -1):
        if w == W-1:
            R[:, w] = grid[:, w]
        else:
            R[:, w] = (R[:, w+1]+1) * grid[:, w]

    # 上
    for h in range(H):
        if h == 0:
            U[h] = grid[h]
        else:
            U[h] = (U[h-1]+1) * grid[h]

    # 下
    for h in range(H-1, -1, -1):
        if h == H-1:
            D[h] = grid[h]
        else:
            D[h] = (D[h+1]+1) * grid[h]

    # 答え
    ans = np.max(L+R+U+D-3)
    print(ans)


if __name__ == "__main__":
    solve()


Measured memory_bytes: 266612
#include <bits/stdc++.h>
#include <cmath>

using namespace std;

int main(){
  
  double a,b,x,tang;
  const double PI=3.14159265358979323846;
  
  cin>>a>>b>>x;

  
  if(x>a*a*b/2)	{
	// 側面が台形
    tang=a*a*a/((2*a*a*b)-2*x);
  }else{
    //側面が三角形
    tang=2*x/(a*b*b);
  }

  double cot=double(90-180*(atan(tang)/acos(-1)));
  printf("%2.9lf\n ",cot);
	    
    
}


Measured memory_bytes: 256
n = int(input())
a = input().split()
b = input().split()
for i in range(len(a)):a[i]=int(a[i])
for i in range(len(b)):b[i]=int(b[i])
m = 0
for i in range(n):
    m+=min([a[i],b[i]])
    p,q=a[i],b[i]
    a[i]=max([0,p-q])
    b[i]=max([0,q-p])
    if b[i]>0:
        m+=min([a[i+1],b[i]])
        p,q=a[i+1],b[i]
        a[i+1]=max([0,p-q])
        b[i]=max([0,q-p])
print(m)

Measured memory_bytes: 18624
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;

vector<int> prime;
bool is_prime[1000010];
int sieve(int n) {
  fill(is_prime + 2, is_prime + 1000010, true);
  for (int i = 2; i <= n; i++) {
    if (is_prime[i]) {
      prime.emplace_back(i);
      for (int j = 2 * i; j <= n; j += i) is_prime[j] = false;
    }
  }
  return prime.size();
}

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  int Q;
  cin >> Q;
  sieve(100000);
  int cum[100010] = {};
  for (int i = 1; i <= 100000; i++) {
    cum[i] = (is_prime[i] && is_prime[(i + 1) / 2]) + cum[i - 1];
  }
  for (int i = 0; i < Q; i++) {
    int l, r;
    cin >> l >> r;
    cout << cum[r] - cum[l - 1] << endl;
  }

  return 0;
}

Measured memory_bytes: 2176
fun main(args:Array<String>) {
	val (h,w,bb,aa) = readLine()!!.split(" ").map {it.toInt()}
	val a = Math.min(aa,h-aa)
	val b = Math.min(bb,w-bb)

	val r = Array(h) {CharArray(w) {'0'}}
	for(i in 0 until a)
		for(j in 0 until b)
			r[i][j] = '1'
	for(i in a until h)
		for(j in b until w)
			r[i][j] = '1'
	r.forEach {println(it)}
}


Measured memory_bytes: 39712
#include<bits/stdc++.h>

using namespace std;

#define ll  long long
#define ld  double

#define all(x)  x.begin(),x.end()
#define sz(x)   (int)x.size()

#define pb  emplace_back
#define X   first
#define Y   second

const int   N   = 2e5 + 5;

typedef pair<int,int>   ii;

vector<int> g[N];

int par[N];
int deg[N];

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;  cin >> n;
    int m;  cin >> m;

    for(int i = 1 ; i < n + m ; ++i)    {
        int x;  cin >> x;
        int y;  cin >> y;

        g[x].pb(y);
        deg[y]++;
    }
    queue<int>  qu;
    vector<int> tp;

    for(int i = 1 ; i <= n ; ++i)
        if(!deg[i]) qu.push(i);

    while (qu.size())   {
        int u = qu.front(); qu.pop();

        tp.pb(u);

        for(int v : g[u])   {
            deg[v]--;
            if(!deg[v])
                qu.push(v);
        }
    }
    for(int x : tp)
    for(int v : g[x])
        par[v] = x;

    for(int i = 1 ; i <= n ; ++i)
        cout << par[i] << "\n";
}


Measured memory_bytes: 9976
#include <bits/stdc++.h>
using namespace std;
int a[12];
int b[12];
int main(void)
{
    int n;
    cin>>n;
    memset(b,0,sizeof(b));
    int ans=1;
    int temp=1;
    for(int i=0;i<n;++i)
    {
        ans*=3;
        cin>>a[i];
        if(a[i]&1)
        {
            b[i]=1;
        }
        else
        {
            b[i]=2;
        }
        temp*=b[i];
    }
    cout <<ans-temp<<endl;

    return 0;
}


Measured memory_bytes: 384
import sys
N, M = list(map(int, input().split()))
broken_set = set([
    int(input())
    for _ in range(M)
])

f = [0] * (N + 1)

f[0] = 1
f[1] = int(1 not in broken_set)

for i in range(2, N+1):
    if i in broken_set:
        f[i] = 0
    else:
        f[i] = (f[i-1] + f[i-2]) % 1000000007

print(f[N])



Measured memory_bytes: 13192
# 上下左右どこでもいける
# BFS
from queue import Queue
h, w = map(int, input().split())
MAZE = ['#'*(w+2)]
for _ in range(h):
    MAZE.append("#"+input()+"#")
else:
    MAZE.append('#'*(w+2))

INF = 10**3
directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]


def bfs(init_x, init_y):
    dp = [[INF]*(w+2) for _ in range(h+2)]
    resisterd = [[0]*(w+2) for _ in range(h+2)]
    q = Queue()
    q.put((init_x, init_y))
    dp[init_x][init_y] = 0
    MAX = 0
    while not q.empty():
        x, y = q.get()
        for i, j in directions:
            if MAZE[x+i][y+j] == '#':
                continue
            if resisterd[x+i][y+j]:
                continue
            resisterd[x+i][y+j] = 1
            q.put((x+i, y+j))
        dp[x][y] = min(dp[x][y], min(dp[x+v][y+w]+1 for v, w in directions))
        MAX = max(MAX, dp[x][y])
    return MAX


ans = 0
for i in range(1, h+1):
    for j in range(1, w+1):
        if MAZE[i][j] == '#':
            continue
        ans = max(ans, bfs(i, j))
print(ans)

Measured memory_bytes: 3944
N = int(input())
p = list(map(int,input().split()))
cnt = 0
bol = 0
for i in range(N-1):
    if bol == 1:
        bol = 0
        continue
    if p[i] == i+1 and p[i+1] == i+2:
        cnt += 1
        bol = 1
    elif p[i] == i+1:
        cnt += 1
if bol == 0 and p[N-1] == N:
    cnt += 1
print(cnt)

Measured memory_bytes: 20596
#include <stdio.h>
#include <string.h>

int main(void)
{

    int i_stringLength;

    scanf("%d", &i_stringLength);

    char c_inputStringS[i_stringLength];
    char c_inputStringT[i_stringLength];

    scanf("%s%s", c_inputStringS, c_inputStringT);

    for (int index = 0; index < i_stringLength; index++)
    {
        printf("%c%c", c_inputStringS[index], c_inputStringT[index]);
    }

}

Measured memory_bytes: 128
import math
n=int(input())
li=[]
for x in range(2,int(math.sqrt(n))+1):
    if n%x==0:
        y=n//x
        walk=y+x-2
        li.append(walk)
    
if li==[]:
    print(n-1)
else:
    print(min(li))

Measured memory_bytes: 3188
N = int(input())
A, B = map(int, input().split())
P = list(map(int, input().split()))

ans1 = ans2 = ans3 = 0
for p in P:
    if p <= A:
        ans1 += 1
    elif A + 1 <= p <= B:
        ans2 += 1
    else:
        ans3 += 1
print(min(ans1,ans2,ans3))


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std ;

const long long maxn = 1e5+10 ;
const long long mod = 1000000007 ;
long long fib[maxn] ;

int main(){


    ios::sync_with_stdio(false) ;
    cin.tie(0) ;

    long long n, m ;
    cin >> n >> m ;

    fib[1] = 1 ;
    for(long long i = 2; i < maxn ; i++)
        fib[i] = (fib[i-1]+fib[i-2]) % mod ;
    long long ans = 1 ;
    long long last = -1 ;
    for(long long i = 0 ; i < m; i++){
        long long tmp ;
        cin >> tmp ;
        ans *= fib[tmp-last-1];
        ans %= mod ;
        last = tmp ;
    }
    cout << ans * fib[n-last] % mod ;

}


Measured memory_bytes: 1024
#include "bits/stdc++.h"
using namespace std;
typedef long long lint;

#define rep(i,n) for(int i=0;i<(n);++i)
#define MAXN 1010
#define linf 8223372036854775808

//d,edge,g
lint d[MAXN];
struct edge{ int to;lint cost; };
vector<edge> g[MAXN];

bool bellmanford(int n,int s){
	d[s]=0;
	rep(i,n){
		rep(v,n){
			for(edge &e:g[v])if(d[v]!=linf&&d[e.to]>d[v]+e.cost){
				d[e.to]=d[v]+e.cost;
				if(i==n-1&&e.to==n-1)return 1;
			}
		}
	}return 0;
}

int main(){
	cin.tie(0);cout.tie(0);
	ios::sync_with_stdio(0);
	int n,m;cin>>n>>m;
	int a,b;lint c;
	fill(d,d+n,linf);
	rep(i,m){
		cin>>a>>b>>c;--a;--b;
		g[a].push_back({b,-c});
	}
	if(bellmanford(n,0))cout<<"inf\n";
	else cout<<-d[n-1];
	return 0;
}


Measured memory_bytes: 384
import std.stdio, std.string, std.conv;
import std.range, std.algorithm, std.array, std.typecons, std.container;
import std.math, std.numeric, core.bitop;

alias Edge = Tuple!(int, "to", int, "cost");

void main() {
    int n, m, s, t;
    scan(n, m, s, t);
    s--, t--;

    auto adj = new Edge[][](n, 0);
    auto adjr = new Edge[][](n, 0);

    foreach (i ; 0 .. m) {
        int ui, vi, ai, bi;
        scan(ui, vi, ai, bi);
        ui--, vi--;
        adj[ui] ~= Edge(vi, ai);
        adj[vi] ~= Edge(ui, ai);
        adjr[ui] ~= Edge(vi, bi);
        adjr[vi] ~= Edge(ui, bi);
    }

    auto yuki = dijkstra(adj, s);
    auto kaeri = dijkstra(adjr, t);

    debug {
        writeln(yuki);
        writeln(kaeri);
    }

    long[] ans = new long[](n);

    ans[n-1] = yuki[n-1] + kaeri[n-1];

    foreach_reverse (i ; 0 .. n-1) {
        ans[i] = min(ans[i+1], yuki[i] + kaeri[i]);
    }

    foreach (i ; 0 .. n) {
        writeln(10L^^15 - ans[i]);
    }
}




auto dijkstra(Edge[][] adj, int s) {
    alias Pair = Tuple!(int, "num", long, "dist");
    immutable inf = 10L^^18;

    int N = adj.length.to!int;

    auto dist = new long[](N);
    dist[] = inf;
    dist[s] = 0;

    auto q = BinaryHeap!(Array!Pair, "a.dist > b.dist")();
    q.insert(Pair(s, 0));

    int rep = N - 1;

    while (!q.empty && rep) {
        auto v = q.front;
        q.popFront();

        if (dist[v.num] < v.dist) continue;

        rep--;

        foreach (e ; adj[v.num]) {
            if (dist[e.to] > dist[v.num] + e.cost) {
                dist[e.to] = dist[v.num] + e.cost;
                q.insert(Pair(e.to, dist[e.to]));
            }
        }
    }

    return dist;
}







































void scan(T...)(ref T args) {
    import std.stdio : readln;
    import std.algorithm : splitter;
    import std.conv : to;
    import std.range.primitives;

    auto line = readln().splitter();
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}



void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}


Measured memory_bytes: 20348
/* template.cpp {{{ */
#include <bits/stdc++.h>
using namespace std;
#define get_macro(a, b, c, d, name, ...) name
#define rep(...) get_macro(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep(...) get_macro(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__)
#define rep1(n) rep2(i_, n)
#define rep2(i, n) rep3(i, 0, n)
#define rep3(i, a, b) rep4(i, a, b, 1)
#define rep4(i, a, b, s) for (ll i = (a); i < (ll)(b); i += (ll)(s))
#define rrep1(n) rrep2(i_, n)
#define rrep2(i, n) rrep3(i, 0, n)
#define rrep3(i, a, b) rrep4(i, a, b, 1)
#define rrep4(i, a, b, s) for (ll i = (ll)(b) - 1; i >= (ll)(a); i -= (ll)(s))
#define each(x, c) for (auto &&x : c)
#define fs first
#define sc second
#define all(c) begin(c), end(c)
using ui = unsigned;
using ll = long long;
using ul = unsigned long long;
using ld = long double;
const int inf = 1e9 + 10;
const ll inf_ll = 1e18 + 10;
const ll mod = 1e9 + 7;
const ll mod9 = 1e9 + 9;
const int dx[]{-1, 0, 1, 0, -1, 1, 1, -1};
const int dy[]{0, -1, 0, 1, -1, -1, 1, 1};
template<class T, class U> void chmin(T &x, const U &y){ x = min<T>(x, y); }
template<class T, class U> void chmax(T &x, const U &y){ x = max<T>(x, y); }
struct prepare_ { prepare_(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(12); } } prepare__;
/* }}} */

int n;
int a[100000];
vector<int> g[100000];

int dfs(int v){
  vector<int> z;
  each(x, g[v]) z.push_back(dfs(x));
  sort(all(z));
  int s = 0;
  rep(i, z.size()) chmax(s, z[i] + z.size() - i);
  return s;
}

int main(){
  cin >> n;
  rep(i, 1, n){
    cin >> a[i], a[i]--;
    g[a[i]].push_back(i);
  }
  cout << dfs(0) << endl;
}


Measured memory_bytes: 13952
print(*[2, 7, 17, 37, 47, 67, 97, 107, 127, 137, 157, 167, 197, 227, 257, 277, 307, 317, 337, 347, 367, 397, 457, 467, 487, 547, 557, 577, 587, 607, 617, 647, 677, 727, 757, 787, 797, 827, 857, 877, 887, 907, 937, 947, 967, 977, 997, 1087, 1097, 1117, 1187, 1217, 1237, 1277, 1297][:int(input())])

Measured memory_bytes: 3064
#include<iostream>
#include<algorithm>
#include<math.h>
#include<string>
#include<vector>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define ll long long
using namespace std;

int main() {
	double ans=0;
	int n, m;
	cin >> n >> m;
	rep(i, 5) {
		ans += n / m*pow(0.1,i);
		n = (n%m) * 10;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 640
// #include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())

int gcd(int a, int b){
    if (b == 0) {
        return a;
    }
    return gcd(b, a%b);
}

ll lcm(ll a, ll b){
    return a * b / gcd(a,b);
}

void solve(){
    string s;
    cin >> s;

    string sol = "CODEFESTIVAL2016";
    int ans = 0;

    for (int i = 0; i < (int)sol.size(); i++) {
        if (sol[i] != s[i]) {
            ans++;
        }
    }

    cout << ans << endl;

    return;
}

int main(int argc, char const* argv[])
{
    solve();
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
//3*3の2次元配列A
//vector<vector<int>> A(3, vector<int>(3));

void solve(){
    long long n, a, b;
    cin >> n >> a >> b;

    if(a != 0 && b == 0){
        cout << n << endl;
        exit(0);
    }

    if(n%(a+b) >= a){
        cout << a*(n/(a+b)) + a << endl;
    }else{
        cout << a*(n/(a+b)) + n%(a+b) << endl;
    }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    solve();
}

Measured memory_bytes: 256
#!/usr/local/bin/python3
# coding: utf-8
n = input()
hairu = input()
kita = hairu.split(" ")
seki = 1

for c in kita:
    if c == "0":
        kita[0] = "0"

for c in kita:
    seki = seki * int(c)
    if seki > 10**18:
        break

if seki > 10**18:
    print("-1")
else:
    print(seki)

Measured memory_bytes: 19060
h,w=map(int,input().split())
hoge=[]
for i in range(h):
  hoge.append(input())

for i in range(w+2):
  print("#",end="")

print("")

for i in range(h):
  print("#",end="")
  print(hoge[i],end="")
  print("#")
  
for i in range(w+2):
  print("#",end="")

print("")

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;


int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n; cin>>n;
    vector<int> a(n),dp(n,INT_MAX);

    for(auto &i:a)  cin>>i;

    dp[0]=0;

    for(int i=0 ; i<n ; i++)
    {
        for(int j:{i+1,i+2})
            {
                if(j<n)
                    dp[j]=min(dp[j],dp[i]+abs(a[i]-a[j]));
            }
    }

        cout<<dp[n-1];

}


Measured memory_bytes: 1024
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<limits.h>

int max(int a, int b){
  return a >= b ? a : b;
}
int lmax(long int a, long int b){
  return a >= b ? a : b;
}
int min(int a, int b){
  return b >= a ? a : b;
}
int lmin(long int a, long int b){
  return b >= a ? a : b;
}
int sei(int a){
  return a>0 ? a : 0;
}
long int power(int a,int b){
  long int count=1;
  for(int i=0;i<b;i++){
    count *= 2;
  }
  return count;
}
int factorial(int n) {
    if (n > 0) return n*factorial(n - 1);
		else return 1;
}
int compare_up_int(const void *a, const void *b){
   return *(int*)a - *(int*)b;
}
int compare_down_int(const void *a, const void *b){
   return *(int*)b - *(int*)a;
}
int euclid(int a, int b){
  if(a < b){int tmp = a;a = b;b = tmp;}
  int r = a % b;
  if(r < 0) r += b;
  while(r != 0){
    a = b;b = r;r = a % b;
    if(r < 0) r += b;
  }
  return b;
}

int main(){
  char s[100001];
  int count0=0,count1=0;
  scanf("%s",s);
  for(int i=0;i<strlen(s);i++){
    if(s[i]=='0')count0++;
    else count1++;
  }
  if(count1>=1 && count0>=1){
    printf("%d",2*min(count0,count1));
    return 0;
  }
  else printf("%d",0);
  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static int gcd(int a, int b){
        if(b == 0)
            return a;
        return gcd(b, a % b);
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] ar = new int[n];
        for (int i = 0; i < n; i++) {
            ar[i] = sc.nextInt();
        }
        if(n == 2){
            System.out.println(Math.max(ar[0], ar[1]));
            return;
        }
        int[] p1 = new int[n];
        int[] p2 = new int[n];
        p1[0] = ar[0];
        for (int i = 1; i < n; i++) {
            p1[i] = gcd(p1[i-1], ar[i]);
        }
        p2[ar.length - 1] = ar[ar.length - 1];
        for(int i = ar.length - 2; i >= 0; i--){
            p2[i] = gcd(p2[i + 1], ar[i]);
        }
        int result = Math.max(p1[ar.length - 2], p2[1]);
        for (int i = 1; i < ar.length - 1; i++) {
            result = Math.max(result, gcd(p1[i - 1], p2[i + 1]));
        }
        System.out.println(result);
    }
}

Measured memory_bytes: 48484
#include<bits/stdc++.h>
#define ll long long int

using namespace std;

const ll mod=1000000007;
const ll inf=1e18;

int main(){

  ll a,b,c;
  cin >> a >> b >>c;
  if(a+b+c>=22)cout << "bust" << endl;
  else cout << "win" << endl; 

}

Measured memory_bytes: 3556
#include <bits/stdc++.h>
using namespace std;

int main() {
  
  	int N;
  	cin >> N;
  	
  	int M=N;
	int keta;
    while(true){
		keta +=(N%10);
      	if(N/10==0){
        	break;
        }
      	N /=10;
    }
    
    if(M%keta==0){
    	cout << "Yes" << endl;
    }
    else{
    	cout << "No" << endl;
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<cstdio>
#define ll long long int
#define pb push_back
using namespace std;
int main()
{
    ll a,b,n,i,j,k,x,y;
    vector<ll>v,u;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>k;
        v.pb(k);
    }
    u.pb(0);
    x=0;
    for(i=n-2;i>=0;i--)
    {
        if(v[i]>=v[i+1])
        {
            x+=1;
            u.pb(x);
        }
        else
        {
            x=0;
            u.pb(x);
        }
    }
    sort(u.begin(),u.end());
    cout<<u[u.size()-1]<<endl;


    return 0;
}


Measured memory_bytes: 2548
#include <iostream>

using namespace std;

int main() {
    int n, y;
    int i, j, k;

    cin >> n;
    cin >> y;

    for (i = 0; i <= n; i++) {
        for (j = 0; j <= n; j++) {
            k = (y - (i * 10000 + j * 5000)) / 1000;
            if (i + j + k== n && k >= 0) 
                    break;
        }
        if (i + j + k == n && k>= 0) {
            cout << i << " " << j << " " << k << endl;
            break;
        }
    }

    if (i + j + k != n || k < 0)
        cout << "-1 -1 -1" << endl;

    return 0;
}

Measured memory_bytes: 256
import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, std.bitmanip;

immutable long MOD = 10^^9 + 7;

void main() {
    auto s = readln.split.map!(to!int);
    auto H = s[0];
    auto W = s[1];
    auto A = H.iota.map!(_ => readln.chomp).array;

    auto dp = new long[][](H, W);
    dp[0][0] = 1;

    foreach (i; 0..H) {
        foreach (j; 0..W) {
            if (A[i][j] == '#') continue;
            foreach (k; 0..2) {
                int ni = i + k;
                int nj = j + 1 - k;
                if (ni >= H || nj >= W || A[ni][nj] == '#') continue;
                (dp[ni][nj] += dp[i][j]) %= MOD;
            }
        }
    }

    dp[H-1][W-1].writeln;
}


Measured memory_bytes: 11004
#include <stdio.h>  
#include <algorithm>  
#include <assert.h>
#include <bitset>
#include <cmath>  
#include <complex>  
#include <deque>  
#include <functional>  
#include <iostream>  
#include <limits.h>  
#include <map>  
#include <math.h>  
#include <queue>  
#include <set>  
#include <stdlib.h>  
#include <string.h>  
#include <string>  
#include <time.h>  
#include <unordered_map>  
#include <unordered_set>  
#include <vector>  

#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")  
using namespace std;

#define mp make_pair  
#define Fi first  
#define Se second  
#define pb(x) push_back(x)  
#define szz(x) ((int)(x).size())  
#define rep(i, n) for(int i=0;i<n;i++)  
#define all(x) (x).begin(), (x).end()  
#define ldb ldouble  

typedef unsigned int uint;
typedef tuple<int, int, int> t3;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;

int IT_MAX = 1 << 19;
const ll MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1e-10;

const int MX = 2005;

int N;
int dp[MX][MX];

struct BIT{
	int t[MX*2];
	void update(int x, int v){
		while(x < 2*MX) t[x] += v, x += x&-x;
	}
	int read(int x){
		int r = 0;
		while(x) r += t[x], x -= x&-x;
		return r;
	}
}t;

int W[MX], B[MX];

int main()
{
	scanf("%d", &N);
	for(int i = 1; i <= 2*N; i++){
		char s[2]; int v;
		scanf("%s%d", s, &v);
		if(s[0] == 'W') W[v] = i;
		else B[v] = i;
	}
	for(int i = 0; i <= N; i++){
		for(int j = 0; j <= N; j++){
			if(j) t.update(W[j], 1);
			dp[i][j] = 1e9;
			if(i == 0 && j == 0) dp[i][j] = 0;
			if(j) dp[i][j] = min(dp[i][j], dp[i][j-1] + (t.read(2*N) - t.read(W[j])));
			if(i) dp[i][j] = min(dp[i][j], dp[i-1][j] + (t.read(2*N) - t.read(B[i])));
		}
		for(int j = 1; j <= N; j++) t.update(W[j], -1);
		if(i != N)if(i != N)  t.update(B[i+1], 1);
	}
	printf("%d\n", dp[N][N]);
}


Measured memory_bytes: 16000
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<complex>
#include<vector>

using namespace std;

typedef complex<double> point;

#define dist2(p1,p2) (real(((p1)-(p2))*conj((p1)-(p2))))

#define mid(p1,p2) ((p1)+(p2))/2.0

#define PI (3.1415926535)
#define EPS (1e-6)

const point ang90 = point(0,1.0);

bool test (const point &a,const point &b){
    return real(a) < real(b);
}

int main(){
  int n;
  point p[300];
  while(scanf("%d",&n),n){
    for(int i=0;i<n;i++){
      double x,y;
      scanf("%lf%lf",&x,&y);
      p[i]=point(x,y);
    }
    sort(p,p+n,test);
    int ans=1;
    for(int i=0;i<n;i++){
      for(int j=i+1;j<n;j++){
        if(real(p[j])-real(p[i]) > 2.0+EPS) break;
        if(dist2(p[i],p[j])>4.0) continue;
        point tmp = (p[i]-p[j]) * ang90;
        tmp=(tmp/abs(tmp))*sqrt(1.0-dist2(p[i],p[j])/4.0);
        point p1 = mid(p[i],p[j]) + tmp;
        int count=0;
        double rp=real(p1);
        bool f=false;
        for(int k=0;k<n;k++){
          if(k==i||k==j){
            count++;
          }else{
            if(f||(rp - real(p[k]) > 1.0 + EPS)) continue;
            f=true;
            if(real(p[k]) - rp > 1.0 + EPS) break;
            if(dist2(p1,p[k])<1.0+EPS){
              count++;
            }
          }
        }
        ans = max(count,ans);
        p1 = mid(p[i],p[j]) - tmp;
        rp=real(p1);
        count=0;
        f=false;
        for(int k=0;k<n;k++){
          if(k==i||k==j){
            count++;
          }else{
            if(f||(rp - real(p[k]) > 1.0 + EPS)) continue;
            if(real(p[k]) - rp > 1.0 + EPS) break;
            if(dist2(p1,p[k])<1.0+EPS){
              count++;
            }
          }
        }
        ans = max(count,ans);
      }
    }
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 956
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <iterator>
#include <cmath>
#include <set>
#include <deque> 
#include <string>


using namespace std;

int n;
long long a[200010];
long long diff[200010];
std::map<long long, long long> diffMap;

int main()
{
	scanf("%d", &n);
	
	for (int i = 1 ; i <= n ; i++) {
		scanf("%lld", &(a[i]));
		if (i != 1) {
			long long dist = i - 1;
			long long sum = a[1] + a[i];
			diff[i] = dist - sum;
			diffMap[diff[i]]++;
		}
	}
	
	long long total = 0;
	long long curZero = 0;
	for (int i = 1 ; i <= n ; i++) {	//没有最后一个了，阁下 
//		if (curZero >= 0)
//			total = total + diffMap[curZero];
//		else
			total = total + diffMap[curZero];
			
		//向前推进 
		if (i < n) {
			diffMap[diff[i + 1]]--;
			curZero++;
			curZero = curZero + (a[i + 1] - a[i]);
		}
	}
	
	printf("%lld\n", total);

	return 0;
}


Measured memory_bytes: 29188
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long N,M,sum=0,p;
    cin>>N>>M;
    int arr[M];
    for(int i=0;i<M;i++)
    {
        cin>>arr[i];
        sum+=arr[i];
    }
    if(N>=sum)
    {
        cout<<N-sum;
    }
    else
    {
        cout<<"-1";
    }
}


Measured memory_bytes: 3600
import java.io.*;
import java.util.*;

public class Main{

    static int count=0;
    
    public static void main(String args[]) throws IOException{
	BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

	int n=Integer.parseInt(br.readLine());
	String str[]=br.readLine().split(" ");
	int a[]=new int[n];
	
	for(int i=0;i<n;i++){
	    a[i]=Integer.parseInt(str[i]);
	}

	mergeSort(a,0,n);

	System.out.print(a[0]);
	for(int i=1;i<n;i++){
	    System.out.print(" "+a[i]);
	}
	System.out.print("\n");
	System.out.println(count);
    }
    static void mergeSort(int a[],int left,int right){
	if (left+1 < right){
	    int mid = (left + right)/2;
	    mergeSort(a, left, mid);
	    mergeSort(a, mid, right);
	    merge(a, left, mid, right);
	}
    }

    static void merge(int A[], int left, int mid, int right){
	int n1 = mid - left;
	int n2 = right - mid;

	int L[]=new int[n1+1];
	int R[]=new int[n2+1];

	int i=0;
	int j=0;
	
	for (i = 0;i<n1;i++)
	    L[i] = A[left + i];
	for (i = 0;i<n2;i++)
	    R[i] = A[mid + i];
	L[n1] = Integer.MAX_VALUE;
	R[n2] = Integer.MAX_VALUE;
	i=0;
	j=0;
	for (int k = left; k<right;k++){
	    if (L[i] <= R[j]){
		A[k] = L[i];
		i = i + 1;
	    }else{ 
		A[k] = R[j];
		j = j + 1;
	    }
	    count++;
	}
    }
}



Measured memory_bytes: 159120
#include <algorithm>
#include <iostream>
using namespace std;
int x[10500],y[10500];
int main()
{
	int w,h,n;
	cin >> w >> h >> n;
	for(int i=0;i<n;i++)
	{
		cin >> x[i] >> y[i];
	}
	int ans=0;
	for(int i=1;i<n;i++)
	{
		int dx=abs(x[i]-x[i-1]),dy=abs(y[i]-y[i-1]);
		if((x[i]>=x[i-1]&&y[i]>=y[i-1])||(x[i]<=x[i-1]&&y[i]<=y[i-1]))
		{
			ans+=max(dx,dy);
		}
		else
		{
			ans+=(dx+dy);
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3116
N=int(input())
A=[int(input()) for i in range(N)]
cnt=0
d=0
D=[-1]*(N+1)
for i in range(N):
  D[A[i]-1]=i
cnt=1
ans=0
for i in range(N):
  if D[i]<D[i+1]:
    cnt+=1
  else:
    ans=max(cnt,ans)
    cnt=1
print(N-ans)
  

Measured memory_bytes: 18924
#include <bits/stdc++.h>
#define REP(i,n) for(ll i = 0; i < (ll)n; i++)
#define FOR(i,a,b) for (ll i=(a);i<(ll)b; i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define INF 1LL << 60
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;
typedef pair<ll,ll> p;
const int MOD = 1000000007;

// vector<p> cut(M);
// cut[i].second
// cut[i].first;
// REP(i,M){
//     int a,b;cin>>a>>b;
//     cut[i] = make_pair(b,a);//last first の順番
// }
// for(int i=0; i<N;i++){
// }
// sort(cut.begin(),cut.end()); //sort
// char '' str ""
long long gcd(long long a, long long b){
  if(b == 0) return a;
  return gcd(b, a%b);
}

int main(void)
{
    int N,M;cin>>N;
    vector<ll> T;
    for(int i=0; i<N;i++){
      ll t; cin>>t; T.push_back(t);
    }
    ll gc; ll lc;
    if(N==1){
      cout<<T[0]<<endl; return 0;
    }
    for(int i=0; i<N;i++){
      if(i==0) gc = gcd(T[i], T[i+1]);
      else gc = gcd(T[i], lc);

      if(i==0) lc = T[i]/gc*T[i+1];
      else lc = T[i]/gc*lc;
    }

    cout<<lc<<endl;
    return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader
import java.util.*
import kotlin.system.exitProcess

fun main() = agc031b()

@OptIn(ExperimentalStdlibApi::class)
fun agc031b() = SimpleFastIOWithToken_agc031b().exec {
    val n = readInt()
    val colors = IntArray(n) { readInt() - 1 }
    val mod = 1_000_000_007L

    val beforeAppearedIndexByColor = mutableMapOf<Int, Int>()
    val patterns = LongArray(n)
    patterns[0] = 1

    for ((i, c) in colors.withIndex()) {
        if (i != 0) {
            patterns[i] = patterns[i - 1]
            beforeAppearedIndexByColor[c]
                ?.takeIf { it != -1 && it != i - 1 }
                ?.let { patterns[i] += patterns[it] }
            patterns[i] %= mod
        }
        beforeAppearedIndexByColor[c] = i
    }

    val answer = patterns.last()

    println(answer)
}

// region kokokara template dayo (^o^)
@Suppress("unused", "HasPlatformType", "MemberVisibilityCanBePrivate", "ClassName")
private class SimpleFastIOWithToken_agc031b(private val separator: String = System.lineSeparator()) {
    private val br: BufferedReader = System.`in`.bufferedReader()
    private var st: StringTokenizer = StringTokenizer("")
    private val sb: StringBuilder = StringBuilder()
    private fun prepareNext() = run { if (!st.hasMoreTokens()) st = StringTokenizer(br.readLine()) }

    fun readString(): String = run { prepareNext() }.run { st.nextToken() }
    fun readInt(): Int = Integer.valueOf(readString())
    fun readLong(): Long = java.lang.Long.valueOf(readString())

    fun println(): Unit = run { sb.append(separator) }
    fun print(any: Any): Unit = run { sb.append(any) }
    fun println(any: Any): Unit = run { sb.append(any.toString() + separator) }

    fun exec(action: SimpleFastIOWithToken_agc031b.() -> Unit) = run {
        Thread(null, { action() }, "(^o^)", 128 * 1024 * 1024)
            .apply { setUncaughtExceptionHandler { _, e -> e.printStackTrace(); exitProcess(1) } }
            .apply { start() }.join()
    }.run { kotlin.io.print(sb) }

    fun readLine(): Nothing = error("readLine is disabled.")
}
// endregion kokomade template dayo (^o^)


Measured memory_bytes: 75480
/* nothing is impossible */
#pragma comment(linker, "/stack:227420978")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h> 
 
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
using namespace std;
 
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pii;
typedef double ld;
typedef string st;
const double PI=3.14159265358979323846264338327950288419716939937510582097494459230;
const ll MOD = 1e9 + 7 ;
const ll INF=1e14;                                                                                                 
ll mpow(ll a,ll b,ll p=MOD){a=a%p;ll res=1;while(b>0){if(b&1)res=(res*a)%p;a=(a*a)%p;b=b>>1;}return res%p;}             

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
 // freopen("input.txt", "r", stdin);
  ll n;
  cin>>n;
  if(!n)
  {
    cout<<"0";
    return 0;
  }
  ll k=0;
  ll a[10000];
  while(n)
  {
    ll o=n%(-2);
    if(o==-1)
    {
      a[k++]=1;
      n/=-2;
      n++;
    }
    else a[k++]=o,n/=-2;
  }
  //if(carry!=0) a[k++]=carry;
  for(ll i=k-1;i>=0;i--) cout<<a[i];
return 0;
}         

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
 
#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=(int)(a)-1;i>=(int)(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)
 
#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
 
// #define DEBUG
 
#ifdef DEBUG
    #define dump(...) fprintf(stderr, __VA_ARGS__)
#else
    #define dump(...)
#endif
 
template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}
 
using namespace std;
using ll=long long;
using vi=vector<int>;
using vll=vector<ll>;
 
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int inf = (int)1e9;
const ll mod=1000000007LL;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
 
 
ll extgcd(ll a,ll b,ll& x,ll& y){x=1,y=0;ll g=a;if(b!=0) g=extgcd(b,a%b,y,x),y-=a/b*x;return g;}
ll ADD(const ll &a, const ll &b,const ll &mod) { return (a+b)%mod;}
ll SUB(const ll &a, const ll &b,const ll &mod) { return (a-b+mod)%mod;}
ll MUL(const ll &a, const ll &b,const ll &mod) { return (1LL*a*b)%mod;}
ll DIV(const ll &a, const ll &b,const ll &mod) {ll x,y; extgcd(b,mod,x,y);return MUL(a,(x+mod)%mod,mod);}
 
random_device rd;
mt19937 mt(rd());
uniform_int_distribution<int> dice(1,6);
uniform_real_distribution<double> score(0.0,10.0);

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n; cin >> n;
    map<char, vi> x;
    map<char, vi> y;
    for(auto& c : "RLUD"){
        x[c] = vi(1, -inf), y[c] = vi(1, -inf);
    }
    rep(i, n){
        int xx, yy; char d; cin >> xx >> yy >> d;
        x[d].emplace_back(xx);
        y[d].emplace_back(yy);
    }

    vi xmax(300), xmin(300), ymax(300), ymin(300);
    for(auto& c : "RLUD"){
        xmax[c] = *max_element(_all(x[c]));
        ymax[c] = *max_element(_all(y[c]));

        x[c][0] = inf, y[c][0] = inf;
        xmin[c] = *min_element(_all(x[c]));
        ymin[c] = *min_element(_all(y[c]));
    }

    int xmab = max(xmax['U'], xmax['D']);
    int xmib = min(xmin['U'], xmin['D']);
    int ymab = max(ymax['R'], ymax['L']);
    int ymib = min(ymin['R'], ymin['L']);

    using R = double;
    R res = 1LL << 61;
    rep(_, 4 * ((int)1e8 + 1)){
        R loop = 0.5 * _;
        R xma = max(1. * xmab, max(xmax['R'] + loop, xmax['L'] - loop));
        R xmi = min(1. * xmib, min(xmin['R'] + loop, xmin['L'] - loop));
        R yma = max(1. * ymab, max(ymax['U'] + loop, ymax['D'] - loop));
        R ymi = min(1. * ymib, min(ymin['U'] + loop, ymin['D'] - loop));

        chmin(res, (xma - xmi) * (yma - ymi));
    }

    cout.precision(20);
    cout << fixed << res << endl;

    return 0;
}


Measured memory_bytes: 1408