akhauriyash/Code-Regression huggingface dataset:
#pragma warning disable

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Runtime.Serialization.Formatters.Binary;
using System.Text;
using System.Text.RegularExpressions;
using System.Diagnostics;
using System.Numerics;
using System.Collections;
using System.Timers;

static class MainClass
{
    public static void Main(string[] args)
    {
        var dp = new BigInteger[90];
        dp[0] = 2;
        dp[1] = 1;
        for (int i = 0; i < 86; i++)
        {
            dp[i + 2] = dp[i + 1] + dp[i];
        }
        Console.WriteLine(dp[Console.ReadLine().ToInt32()]);
        Console.ReadLine();
    }


    #region ライブラリ

    #region 文字列処理

    public static int ToInt32(this string str) => int.Parse(str);
    public static BigInteger ToBigInteger(this string str) => BigInteger.Parse(str);
    public static List<string> SplittedStringToList(this string str) => str.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).ToList();
    public static List<int> SplittedStringToInt32List(this string str) => str.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(x => int.Parse(x)).ToList();

    public static List<BigInteger> SplittedStringToBigInteger(this string str) => str.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(x => BigInteger.Parse(x)).ToList();
    #endregion
    #region DeepClone
    public static T DeepClone<T>(this T src)
    {
        using (var memoryStream = new MemoryStream())
        {
            var binaryFormatter
              = new BinaryFormatter();
            binaryFormatter.Serialize(memoryStream, src);
            memoryStream.Seek(0, SeekOrigin.Begin);
            return (T)binaryFormatter.Deserialize(memoryStream);
        }
    }
    #endregion

    public static int Gcd(int a, int b)
    {
        if (b == 0)
            return a;
        return Gcd(b, a % b);
    }
    public static BigInteger Gcd(BigInteger a, BigInteger b)
    {
        if (b == 0)
            return a;
        return Gcd(b, a % b);
    }


    public static BigInteger Factorial(int n)
    {
        var dp = new BigInteger[n];
        dp[0] = 1;
        for (int i = 1; i < n; i++)
        {
            dp[i] = dp[i - 1] * (i + 1);
        }
        return dp[n - 1];
    }

    public static List<int> PrimeFactorize(int n)
    {
        var bases = n;
        var num = (int)Math.Pow(n, 0.5);
        var ls = new List<int>();
        for (int i = 2; i <= num; i++)
        {
            if (n % i == 0)
            {
                n = n / i;
                ls.Add(i);
                i--;
                continue;
            }
        }
        var nnn = 1;
        foreach (var item in ls)
        {
            nnn = nnn * item;
        }
        if (nnn != bases)
            ls.Add(n);
        return ls;
    }

    #endregion

}


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

#define int long long
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<n;++i)
#define exrep(i, a, b) for(ll i = a; i < b; i++)
#define out(x) cout << x << endl
#define EPS (1e-7)
#define gearup ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<bool> > vvb;
typedef vector<vector<double> > vvd;
typedef vector<vector<string> > vvs;
typedef vector<ll> vl;
typedef vector<vector<ll> > vvl;
typedef vector<vector<vector<ll> > > vvvl;
ll MOD = 1000000007;
const long long L_INF = 1LL << 60;
const int INF = 2147483647; // 2^31-1
const double PI = acos(-1);
//cout<<fixed<<setprecision(10);

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
template<class T> void debug(T v){rep(i,v.size()) cout<<v[i]<<" ";cout<<endl;}
const ll dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
//以降 cin の入力元が 'input.txt' になる
//std::ifstream in("input.txt");
//std::cin.rdbuf(in.rdbuf());


signed main()
{
    gearup;
    ll a,b,c; cin >> a >> b >> c;
    out(a+b+c-max(a,max(b,c)));
}

Measured memory_bytes: 3644
// clang-format off
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define stoi stoll
using pii = pair<int,int>;
using vi = vector<int>;
using vvi = vector<vi>;
#define all(c) begin(c), end(c)
#define rall(c) rbegin(c), rend(c)
#define fore(x, c) for(auto &&x : c)
#define rep(i, a, n) for(int i = a, i##len = (int)(n); i < i##len; ++i)
#define rrep(i, a, n) for(int i = (int)(n - 1); i >= a; --i)
#define sz(c) ((int)c.size())
#define contains(c, x) (c.find(x) != end(c))
#define inseg(l, x, r) ((l) <= (x) && (x) < (r))
#define dump(...)
#define pb push_back
#define eb emplace_back
#define _ 0
const signed INF_ = 1001001001; const long long INF = 1001001001001001001LL;
const int DX[9] = {0,1,0,-1,1,1,-1,-1,0}, DY[9] = {-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os, const vector<T> &v) {
  for (auto i = begin(v); i != end(v); i++) os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is, vector<T> &v) {
  for (auto i = begin(v); i != end(v); i++) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
  is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a, const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a, const U &b){return a>b?a=b,1:0;}
template <class T> void psum(T& c) {partial_sum(begin(c), end(c), begin(c));}
template<class T> using heap = priority_queue<T, deque<T>, greater<T>>;
struct before_main_function {
  before_main_function() {
      cin.tie(nullptr); ios::sync_with_stdio(0);
      cout << setprecision(15) << fixed;
  }
} before_main_function;
// clang-format on
//------------------8<------------------------------------8<--------------------

signed main() {
  int N, M, Q;
  cin >> N >> M >> Q;
  vi A(Q), B(Q), C(Q), D(Q);
  rep(i, 0, Q) {
    cin >> A[i] >> B[i] >> C[i] >> D[i];
    A[i]--, B[i]--;
  }

  int ans = 0;
  vi a;
  auto rec = [&](auto &self, int i) {
    if (sz(a) > N) return;
    if (i > M) {
      if (sz(a) == N) {
        int tmp = 0;
        rep(j, 0, Q) {
          if (a[B[j]] - a[A[j]] == C[j]) {
            tmp += D[j];
          }
        }
        chmax(ans, tmp);
        return;
      } else {
        return;
      }
    }
    rep(j, 0, N + 1) {
      rep(k, 0, j) a.push_back(i);
      self(self, i + 1);
      rep(k, 0, j) a.pop_back();
    }
  };
  rec(rec, 1);
  cout << ans << endl;
  return (0 ^ _ ^ 0);
}



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

int main() {
  int N;
  cin >> N;
  int sum=0;
  for(int i=0;i<=15;i++) {
    for(int j=0;j<=25;j++) {
      if(i*7+j*4==N) sum++;
    }
  }
  if(sum) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define PI 3.1415926535897
using namespace std;
typedef long long ll;
const int INF = 1000000000;
const ll LINF = 1000000000000000000; //1e18
const double EPS = 1e-10;

int main(void)
{
    int A, B, C, D;
    cin >> A >> B >> C >> D;

    string ans;
    bool isTakahasi;
    for (;;)
    {
        C = C - B;
        if (C <= 0)
        {
            isTakahasi = true;
            break;
        }
        A = A - D;
        if (A <= 0)
        {
            isTakahasi = false;
            break;
        }
    }

    if (isTakahasi == true)
    {
        ans = "Yes";
    }
    else
    {
        ans = "No";
    }

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

Measured memory_bytes: 3624
#include <bits/stdc++.h>
#include <stdio.h>
#include <math.h>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
#define rep(i, n) for(int i=0;i<n;i++)

  
int main(){
 int k;
  cin >> k;
  if(k%2==0) cout << k*k/4 <<endl;
  else cout << (k/2+1)*(k/2) <<endl;
   
 
}
  

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
#include <map>
#include <set>
#include <queue>
#include <cmath>
#include <cassert>
using namespace std;
#define INF 1LL<<60

template <class X>
tuple<vector<X>, vector<int>, bool> bellman_ford(int V, vector<tuple<int, int, X>> &edges, int s){
    /*
     * Bellman-Ford
     * 負の重みが有っても良い
     * O(VE)
     * 1. s からの距離
     * 2. 最短経路での一つ前のノードの添字
     * 3. 負の重みの閉路があるか
     * を返す
     */
    vector<X> distance(V, INF);
    vector<int> predecessor(V);
    bool negative_cycle = false;

    distance[s] = 0;
    for(int i=0; i<V-1; i++){
        for(auto edge : edges){
            int fr, to;
            X cost;
            tie(fr, to, cost) = edge;
            if(distance[fr] != INF && distance[to] > distance[fr] + cost){
                distance[to] = distance[fr] + cost;
                predecessor[to] = fr;
            }
        }
    }

    // 負の重みの閉路がないかチェック
    for(auto edge : edges){
        int fr, to;
        X cost;
        tie(fr, to, cost) = edge;
        if(distance[fr] != INF && distance[to] > distance[fr] + cost)
            negative_cycle = true;
    }
    return make_tuple(distance, predecessor, negative_cycle);
}

vector<int> bfs(vector<vector<int>> &G, int s){
    int N = G.size();
    vector<int> vis(N);
    vis[s] = true;
    queue<int> que;
    que.push(s);
    while(!que.empty()){
        int fr = que.front();
        que.pop();
        for(auto t : G[fr]){
            if(vis[t]) continue;
            vis[t] = true;
            que.push(t);
        }
    }
    return vis;
}

int main(){
    int N, M, P;
    cin >> N >> M >> P;
    vector<tuple<int, int, long long>> edges;

    vector<vector<int>> G(N), Ginv(N);
    for(int i=0; i<M; i++){
        int A, B, C;
        cin >> A >> B >> C;
        A--; B--;
        edges.emplace_back(A, B, -C+P);
        G[A].push_back(B);
        Ginv[B].push_back(A);
    }

    vector<int> hoge = bfs(G, 0);
    vector<int> fuga = bfs(Ginv, N-1);

    auto edges0 = edges;
    edges.clear();
    for(auto edge : edges0){
        int s, t;
        long long cost;
        tie(s, t, cost) = edge;
        if(hoge[s] && fuga[s] && hoge[t] && fuga[t])
            edges.push_back(edge);
    }

    vector<long long> distance;
    vector<int> predecessor;
    bool negative_cycle;
    tie(distance, predecessor, negative_cycle) = bellman_ford(N, edges, 0);

    if(negative_cycle){
        cout << -1 << endl;
        return 0;
    }
    long long ans = max(-distance[N-1], 0LL);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n, count;
  int inst = 1;
  cin >> n;
  vector<int> vec(n);
  for (int i = 0; i<n; i++){
  	cin >> vec.at(i);
  }

  while (count != n){
    inst = vec.at(inst-1);
    count += 1;
    if (inst == 2){
      break;
    }
  }
  if (count == n){
    cout << -1 << endl;
  }else{
    cout << count << endl;
  }

}

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

#define ALL(a) (a).begin(), (a).end()
#define ll long long

using namespace std;

signed main(){
	string str; cin >> str;
	int n; cin >> n;
	vector<string> arr(n);
	for(auto &e : arr)cin >> e;

	int ans = 0;
	for(int i = 0; i < n; i++){
		bool flag1 = false;
		for(int j = 0; j < 10; j++){
			bool flag = true;
			for(int k = 0; k < str.size(); k++){
				if(str[k] != arr[i][(j+k)%10]){
					flag = false;
					break;
				}
			}
			if(flag){
				flag1 = true;
				break;
			}
		}
		if(flag1){
			ans++;
		}
	}
	cout << ans << endl;

	return 0;
}




Measured memory_bytes: 3196
S = input()
if S[0] in S[1:4]:
    if S[1] in S[2:4] :
        if S[0] != S[1]:
            print("Yes")
            exit()
    elif S[2] in S[3]:
        if S[0] != S[2]:
            print("Yes")
            exit()
print("No")

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

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ii, int> ri3;
#define mp make_pair
#define pb push_back
#define fi first
#define sc second
#define SZ(x) (int)(x).size()
#define ALL(x) begin(x), end(x) 
#define REP(i, n) for (int i = 0; i < n; ++i) 
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)

int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);

    int N; string S, T;
    cin >> N >> S >> T;

    string ans = "";
    FOR(i,0,N-1){
        ans += S[i];
        ans += T[i];
    }
    cout << ans;
}



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

void solve(long long N, long long D){
    if (N >= 2 * D + 1) {
        if (N % (2 * D + 1))
            cout << (N / (2 * D + 1)) + 1<< '\n';
        else
            cout << (N / (2 * D + 1)) << '\n';
    } else
        cout << 1 << '\n';
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    long long N;
    scanf("%lld",&N);
    long long D;
    scanf("%lld",&D);
    solve(N, D);
    return 0;
}


Measured memory_bytes: 256
s = input()

L = ['R', 'U', 'D']
M = ['L', 'U', 'D']

lens = len(s)
cnt = 0

for i in range(lens):
    if (i+1)%2 == 1 and s[i] in L:
        cnt += 1
    elif (i+1)%2 == 0 and s[i] in M:
        cnt += 1

if cnt == lens:
    print('Yes')
else :
    print('No')
        


Measured memory_bytes: 9052
#include<iostream>
#include<vector>
using namespace std;

int main(){
    long long a;
    cin>>a;
    vector<int>v(a);
    vector<int>v1(a+1,1e9);
    for(int i=0;i<a;i++){
        cin>>v[i];
    }
    v1[0]=0;
    for(int i=0;i<a-1;i++){
        v1[i+1]=min(v1[i+1],v1[i]+abs(v[i+1]-v[i]));
        v1[i+2]=min(v1[i+2],v1[i]+abs(v[i+2]-v[i]));
    }
    cout<<v1[a-1];
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <time.h>
#include <list>

using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);++i)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define reps(x,c) for(auto x:c)
#define all(x) begin(x), end(x)
#define pb(a) emplace_back(a) 
#define mp(a,b) make_pair((a),(b))
#define pl pair<ll,ll>
#define INF 2147483600
#define MOD 1000000007
#define fi first
#define se second
#define dbg(x) cout << #x"="<< (x) << endl
#define dbgv(x) cout<<#x<<endl;reps(y,x){cout<<y<<" ";}cout<<endl

int main(){
  ll n;cin>>n;
  vector<ll> a(n);
  rep(i,n){
    cin>>a[i];
  }
  sort(all(a),greater<ll>());
  ll alice=0,bob=0;
  rep(i,n){
    if(i%2==0){
      alice+=a[i];
    }else{
      bob+=a[i];
    }
  }
  cout<<alice-bob<<endl;
  return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder_solve
{
    class Program
    {
        public const ulong mod = 1000000007;

        static void Main(string[] args)
        {
            var nm = Input3();
            var n = nm[0];
            var m = nm[1];
            var maxrange = n;
            long minrange = 1;
            for(int i = 0; i < m; i++)
            {
                var lr = Input3();
                maxrange = Math.Min(maxrange, lr[1]);
                minrange = Math.Max(minrange, lr[0]);
            }

            if (maxrange - minrange < 0) Console.WriteLine(0); 
            else Console.WriteLine(maxrange-minrange+1);
            
        }

        static public long Input()
        {
            return long.Parse(Console.ReadLine());
        }

        static public string[] Input2()
        {
            return Console.ReadLine().Split();
        }
        
        static public long[] Input3()
        {
            string[] data = Console.ReadLine().Split();
            long[] res = new long[data.LongLength];
            for(long i = 0; i < data.LongLength; i++)
            {
                res[i] = long.Parse(data[i]);
            }
            return res;
        }
        public static long Choose(long n, long a)
        {
            long x = 1;
            long y = 1;
            for (long i = 0; i < a; i++)
            {
                x *= n - i;
                y *= i + 1;
            }
            return x / y;
        }

        public static long Gcd(long a, long b)
        {
            long x = Math.Max(a, b);
            long y = Math.Min(a, b);
            if (x % y == 0) return y;
            else return Gcd(y, x % y);
        }
    }
}


Measured memory_bytes: 17228
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>
#include <fstream>
#include <bitset>
#include <time.h>
#include <tuple>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef complex<double> Point;

#define PI acos(-1.0)
#define EPS 1e-10
const ll INF = 1e12;
const ll MOD = 1e9 + 7;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,N) for(int i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define EQ(a,b) (abs((a)-(b))<EPS)
#define EQV(a,b) ( EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()) )
#define fi first
#define se second
#define N_SIZE (1LL << 20)
#define NIL -1

int A[500100];
int cnt = 0;

void Merge(int left, int mid, int right) {
	int n1 = mid - left;
	int n2 = right - mid;
	vector<ll> L(n1 + 1, 0), R(n2 + 1, 0);
	for (int i = 0; i < n1; i++)L[i] = A[left + i];
	for (int i = 0; i < n2; i++)R[i] = A[mid + i];
	L[n1] = INF;
	R[n2] = INF;
	int i = 0;
	int 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;
		}
		cnt++;
	}
}

void MergeSort(int left, int right) {
	if (left + 1 < right) {
		int mid = (left + right) / 2;
		MergeSort(left, mid);
		MergeSort(mid, right);
		Merge(left, mid, right);
	}
}

int n;

int main() {
	cin >> n;
	rep(i, n)cin >> A[i];
	MergeSort(0, n);
	rep(i, n) {
		if (i != n - 1)cout << A[i] << " ";
		else cout << A[i] << endl;
	}
	cout << cnt << endl;
}

Measured memory_bytes: 8612
k = int(input())
k_list = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
print(k_list[k - 1])

Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int MAX = 20;

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

struct P
{
	int x, y;
};

int main() {
	int h, w;
	cin >> h >> w;
	char S[MAX][MAX];
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			cin >> S[i][j];
		}
	}
	int ans = 0;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			if (S[i][j] == '#') continue;
			int now = 0;
			int dist[MAX][MAX]; fill((int *)begin(dist), (int *)end(dist), -1);
			queue<P> que;
			que.push(P{i,j});
			dist[i][j] = 0;
			while (!que.empty()) {
				P p = que.front(); que.pop();
				for (int k = 0; k < 4; k++) {
					int next_x = p.x + dx[k], next_y = p.y + dy[k];
					if (next_x < 0 || next_y < 0 || next_x >= h || next_y >= w) continue;
					if (S[next_x][next_y] == '#') continue;
					if (dist[next_x][next_y] != -1) continue;
					dist[next_x][next_y] = dist[p.x][p.y] + 1;
					now = max(now, dist[next_x][next_y]);
					que.push(P{next_x, next_y});
				}
			}
			ans = max(ans, now);
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
n = int(input())
wlist = list(map(int, (input().split())))
all = sum(wlist)
anslist = []
for i in range(n):
    s1 = 0
    for j in range(i+1):
        s1 += wlist[j]
    s2 =  all - s1
    d = abs(s2-s1)
    anslist.append(d)
print(min(anslist))

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

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define br() p("")
#define pn(s) cout << (#s) << " " << (s) << endl

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

// ローリングハッシュ
// h = 2^64にすることでmod不要
using ull = unsigned long long;
vector<ll> rolling_hash_search(string s, string t){
    vector<ll> index_list;
    ll SL = s.size();
    ll TL = t.size();
    
    ull b = 1e8 + 7;

    // 蟻本でいう、bのm乗
    ull a = 1;
    FOR(i, 0, TL){
        a *= b;
    }
    
    // 先頭のローリングハッシュ
    ull s_hash = 0;
    FOR(i, 0, TL){
        s_hash = s_hash * b + s[i];
    }

    ull t_hash = 0;
    FOR(i, 0, TL){
        t_hash = t_hash * b + t[i];
    }

    // sの始点を1つずつ進めながらハッシュ値をチェック
    FOR(i, 0, SL - TL + 1){
        if(s_hash==t_hash){
            index_list.push_back(i);
        }

        if(i+TL<SL){
            s_hash = s_hash * b - s[i] * a + s[i+TL];
        }
    }

    return index_list;
}

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

    // input
    string s, t;
    cin >> s >> t;

    auto ans = rolling_hash_search(s, t);
    for(ll i : ans){
        p(i);
    }

    return 0;
}


Measured memory_bytes: 14116
#include <algorithm>
#include <bitset>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <cctype>
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <limits>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <math.h>

// ===============================================================

using namespace std;
using ll = long long;
using vl = vector<long long>;
using vll = vector<vector<long long>>;
using vs = vector<string>;
using vc = vector<char>;
using vcc = vector<vector<char>>;
using vm = vector<short>;
using vmm = vector<vector<short>>;
using pii = pair<int, int>;
using psi = pair<string, int>;
using ld = long double;
using ull = unsigned long long;
using ld = long double;

// ========================================================================

//ライブラリ(*'▽')

ll gcd(ll a, ll b)
{
	if (a % b == 0)
	{
		return(b);
	}
	else
	{
		return(gcd(b, a % b));
	}
}
//最大公約数
ll lcm(ll a, ll b)
{
	return a * b / gcd(a, b);
}
//最小公倍数
ll box(double a)
{
	ll b = a;
	return b;
}
//切り捨て
ll fff(double a)
{
	ll b = a + 0.5;
	return b;
}
//四捨五入
ll sum(ll n) {
	return (1 + n) * n / 2;
}
//1から整数nまでの合計を出す
bool prime(ll a)//素数判定、primeならtrue,違うならfalse
{
	if (a < 2) return false;
	else if (a == 2) return true;
	else if (a % 2 == 0) return false;
	double m = sqrt(a);
	for (int i = 3; i <= m; i += 2)
	{
		if (a % i == 0)
		{
			return false;
		}
	}

	// 素数である
	return true;
}
//素数判定
ll modpow(ll a, ll n, ll mod) {
	ll hi = 1;
	while (n > 0) {
		if (n & 1) hi = hi * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return hi;
}
//いろいろやります（ただの前座）
ll mg(ll a, ll mod) {
	return modpow(a, mod - 2, mod);
}
//割り算の10^9+7等対策で逆元を出します



// ========================================================================


vl e(250000);
vl f(250000, 100000000000);

int main() {
	long long int k;
	cin >> k;
	int x = 0;
	int ans = 0;
	for (int i = 1; i <= k; i++) {
		x = x * 10 + 7;
		x %= k;
		if (x == 0) {
			ans = i;
			break;
		}
	}
	if (ans == 0) {
		cout << -1 << endl;
	}
	else {
		cout << ans << endl;
	}


	return 0;
}

Measured memory_bytes: 7048
using System;
using System.Linq;
public class Hello{
    public static void Main(){
        var a = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
        Array.Sort(a);
        Console.WriteLine(Math.Abs(a[2] - a[1]) + Math.Abs(a[1] - a[0]));
    }
}


Measured memory_bytes: 13396
#include "bits/stdc++.h"

using namespace std;

#define endl            "\n"
#define sz(x)          (int) (x.size())
#define all(v)          v.begin(), v.end()
#define isOdd(n)       (n&1)
#define pow(n, m)      (ll)powl(n, m)
#define clr(x, val)     memset(x, val, sizeof(x))


typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;


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

    int n; cin >> n;
    while(n--){
        cout << "ACL";
    }
    return 0;
}


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

const long long int MOD = 1000000007;
const int MAX_K = 202020;

long long int inv[MAX_K], comb[MAX_K];

void com_init(long long int n){
  comb[0] = 1LL;
  inv[1] = 1LL;
  for(int i = 2; i < MAX_K; i++){
    inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
  }
  for(int i = 1; i < MAX_K; i++){
    comb[i] = comb[i - 1] * (n - i + 1) % MOD * inv[i] % MOD;
  }
}

long long int com(int k){
  return comb[k];
}

long long int mpow(long long int x, int n)
{
    if(n == 0)
        return 1;

    long long int k = 1;
    while(n > 1)
    {
        if(n % 2 == 1)
        {
            k *= x;
            k %= MOD;
        }
        x *= x;
        x %= MOD;
        n /= 2;

    }
    return (k * x) % MOD;
}

ll n, a, b;

int main()
{
    cin >> n >> a >> b;
    com_init(n);
    ll res = mpow(2, n) - com(a) - com(b) - 1;
    while(res < 0) res += MOD;
    cout << res  << endl;

    return 0;
}

Measured memory_bytes: 3456
N,P = map(int,input().split())
ans=1
i=2
if N==1:
  print(P)
  exit()
if N>=40 or P==1:
  print(1)
  exit()
  
while i<=(P**(1.05/N)):
  while P%(i**N) == 0:
    ans *= i
    P = P//(i**N)
  if i==2:
    i+=1
  else:
    i+=2
print(ans)

Measured memory_bytes: 3064
# 18:57-
def bfs(m, sx, sy)
  
  inf = 10 ** 12
  
  h = m.size
  w = m[0].size
  d = Array.new(h){ [inf] * w }
  used = Array.new(h){ [false] * w }
  
  q = [[sx, sy]]
  d[sx][sy] = 0
  used[sx][sy] = true
  
  while q.any?
    
    x, y = q.shift
    cost = d[x][y]
    
    nx = x - 1
    if 0 <= nx && m[nx][y] == 46 && !used[nx][y]
      d[nx][y] = 1 + cost
      used[nx][y] = true
      q << [nx, y]
    end
    nx = x + 1
    if nx < h && m[nx][y] == 46 && !used[nx][y]
      d[nx][y] = 1 + cost
      used[nx][y] = true
      q << [nx, y]
    end
    ny = y - 1
    if 0 <= ny && m[x][ny] == 46 && !used[x][ny]
      d[x][ny] = 1 + cost
      used[x][ny] = true
      q << [x, ny]
    end
    ny = y + 1
    if ny < w && m[x][ny] == 46 && !used[x][ny]
      d[x][ny] = 1 + cost
      used[x][ny] = true
      q << [x, ny]
    end
  end
  # p d
  res = d.flatten.uniq.sort[-2..-1]
  res[-1] == inf ? res[-2] : res[-1]
end

h, w = gets.to_s.split.map{|t|t.to_i}
a = Array.new(h){ gets.to_s.chomp.bytes }

ans = 0
h.times do |sx|
  w.times do |sy|
    next if a[sx][sy] == 35
    t = bfs(a, sx, sy) #if a[sx][sy] == 46
    ans = t if ans < t
  end
end

puts ans

Measured memory_bytes: 2172
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <math.h>
#include <string>
#include <string.h>
#include <stack>
#include <queue>
#include <vector>
#include <utility>
#include <set>
#include <map>
#include <stdlib.h>
#include <iomanip>

using namespace std;

#define ll long long
#define vvi vector< vector<int> >
#define vi vector<int>
#define All(X) X.begin(),X.end()
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define pi 3.14159265359
#define shosu(X) fixed << setprecision(X)
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b)*b; }


int main() {
	ll W, a, b;
	ll sum=0;
	cin >> W >> a >> b;
	if (a < b)swap(a, b);
	sum = a - b - W;
	if (sum > 0)cout << sum<<endl;
	else cout << 0<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
vector<P>vec;
int n;
int main(){
	scanf("%d",&n);
	rep(i,n){
		int a,b; scanf("%d%d",&a,&b);;
		vec.pb(mp(b,a));
	}
	SORT(vec);
	int las = 0;
	rep(i,n){
		if(las+vec[i].sc > vec[i].fi){
			goto fail;
		}
		las += vec[i].sc;
	}
	puts("Yes"); return 0;
	fail:; puts("No");
}

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

int main() {
  int H, W;
  cin >> H >> W;

  string masu[H];
  rep(i, 0, H) {
    cin >> masu[i];
  }

  const int dx[8] = { 1, 0, -1,  0, 1, -1, -1,  1};
  const int dy[8] = { 0, 1,  0, -1, 1,  1, -1, -1};

  rep(i, 0, H) {
    rep(j, 0, W) {
      if (masu[i][j] == '#') continue;

      int num = 0;
      rep(d, 0, 8) {
        const int ni = i + dy[d];
        const int nj = j + dx[d];

        if (ni < 0 or H <= ni) continue;
        if (nj < 0 or W <= nj) continue;
        if (masu[ni][nj] == '#') num++;
      }
      masu[i][j] = (char)(num+'0');
    }
  }

  rep (i, 0, H) cout << masu[i] << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
int main(void){
    // Your code here!
    int n,a,b;
    scanf("%d\n",&n);
    
    if(n==1){
        printf("Hello World\n");
    }
    else{
        scanf("%d\n%d\n",&a,&b);
        printf("%d\n",a+b);
    }
}


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

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)2e5 + 9;
vector<int> P[N];
map<pii, bool> cor;

int main(){
  fastIO;
  int n, m, q;
  cin >> n >> m >> q;
  int x, y;
  for(int i = 0 ; i < q; i ++ ){
    cin >> x >> y;
    cor[mp(y,x)] = true;
    P[y].push_back(x);
  }
  for(int i = 1; i <= m ; i ++ )
    P[i].push_back(n + 1);
  for(int i = 1; i <= m ; i ++ )
    sort(P[i].begin(), P[i].end());
  int low = P[1][0];
  int pos = 2;
  int res = P[1][0] - 1;
  int idx;
  for(int i = 2; i <= m ; i ++ ){
    while(pos < low && cor[mp(i, pos)]){
      pos ++ ;
    }
    if(pos >= low) break;
    idx = 0;
    while(P[i][idx] < pos)
      ++idx;
    res = min(res, P[i][idx] - 1);
    pos ++ ;
  }
  cout << res;
  return 0;
}


Measured memory_bytes: 33664
#include<stdio.h>

int main()
{
  int n, a[100001]={0}, x;
  int i, j, t, d, p=1;

  scanf("%d", &n);
  for( i=1; i<=n; i++){
    scanf("%d", &x);
    if(a[x] == x) a[x+1]=x;
    else a[x]=x;
  }

  if(n%2) d=0;
  else d=1;
  for( i=1; i<=n; i++){
    if(a[i] != d){
      p=0;
      break;
    }
    if(n%2){
      if(i%2==1) d += 2;
    }else{
      if(i%2==0) d += 2;
    }
    if(i%2==0)p = p * 2 %1000000007;
  }

  printf("%d\n", p);
  return 0;
}

Measured memory_bytes: 512
//* AuThOr GaRyMr *//
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define niv vector<int>
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define KEEP while(1)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define ff fflush(stdout)
using namespace std;
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
typedef pair<mp,mp> superpair;
int main(){
	int Res=0;
	int n;
	int las=-1,cnt=0;
	cin>>n;
	rb(i,1,n){
		int ai;
		cin>>ai;
		if(ai!=las){
			Res+=cnt/2;
			cnt=1;
			las=ai;
		}
		else{
			cnt++;
		}
	}
	Res+=cnt/2;
	cout<<Res<<endl; 
	return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <bitset>
#include <functional>
using namespace std;

#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<(x)<<endl
#define fi first
#define se second

#define INF 2147483600

int main(){
  int a,b,h;
  cin>>a>>b>>h;

  cout<<(a+b)*h/2<<endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 1000000000000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


int N;
char buf[105];

int main(){

	scanf("%d",&N);
	scanf("%s",buf);

	if(N%2 == 1){

		printf("No\n");
		return 0;
	}

	bool FLG = true;

	for(int i = 0; i < N/2; i++){
		if(buf[i] != buf[i+N/2]){

			FLG = false;
			break;
		}
	}

	if(FLG){

		printf("Yes\n");
	}else{

		printf("No\n");
	}


	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cstring>
#include<climits>
#include<queue>
#include<map>
#include<utility>

using namespace std;

map<string, int> res;
int dx[4] = { 1, -1, 4, -4};

void bfs()
{
    queue<string> q;
    string u = "01234567";
    res[u] = 1;
    q.push(u);

    while(q.size())
    {
        string u = q.front(); q.pop();
        int pos;
        for(int i = 0; i < 8; ++i)
            if(u[i] == '0')
                pos = i;

        for(int i = 0; i < 4; ++i)
        {
            if (0 <= pos + dx[i] && pos + dx[i] < 8 &&
                !(pos == 3 && i == 0) && !(pos == 4 && i == 1))
                {
                    string v = u;
                    swap(v[pos], v[pos + dx[i]] );
                    if(res[v] == 0)
                    {
                        res[v] = res[u] + 1;
                        q.push(v);
                    }
                        
                }
        }
    }
    
}


int main()
{
    string input;
    char ch;
    bfs();
    while(cin>>ch)
    {
        input.push_back(ch);
        for(int i = 0; i < 7; ++i)
        {
            cin>>ch;
            input.push_back(ch);
        }
        cout<< res[input] - 1 << endl;
        input.clear();
    }
}


Measured memory_bytes: 5232
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int arr[5];
  for(int i=0;i<5;i++){
    cin>>arr[i];
  }
  for(int i=0;i<5;i++){
    if(arr[i]==0){
      cout<<i+1;
    }
  }
}
  

Measured memory_bytes: 3636
#include <iostream> // cout, endl, cin
#include <cmath> //sqrt pow
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // dequef
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower

#define rep(i,n) for(int i = 0; i < n; i++)
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define all(a) (a).begin(), (a).end()
#define mod 1000000007
using ll = long long;
using namespace std;
int main(){
  int a;
  cin >> a;
  cout << a * a * 3 << endl;
}

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

int N;
long long ans;

int main() {
  cin >> N;
  for(int i = 1; i <= N; i++) {
    if(i % 3 != 0 && i % 5 != 0)ans += i;
  }
  cout << ans << '\n';
}

Measured memory_bytes: 3636
#include <cstdio>
#include <string>
#include <vector>


using namespace std;

int h, w;
int a[510][510];

struct Oper
{
	
	int sr, sc;
	int tr, tc;
};

std::vector<Oper> opers;

int main()
{
	scanf("%d%d", &h, &w);
	
	for (int r = 1 ; r <= h ; r++)
		for (int c = 1 ; c <= w ; c++)
			scanf("%d", &(a[r][c]));
			
	for (int r = 1 ; r <= h ; r++)
	{
		for (int c = 2 ; c <= w ; c++)
		{
			int lc = c - 1;
			if (a[r][lc] % 2 == 1)
			{
				a[r][lc]--;
				a[r][c]++;
				
				Oper newOper;
				newOper.sr = r;
				newOper.sc = lc;
				newOper.tr = r;
				newOper.tc = c;
				
				opers.push_back(newOper);
			}
		}
	}
	
	for (int r = 2 ; r <= h ; r++)
	{
		int lr = r - 1;
		
		if (a[lr][w] % 2 == 1)
		{
			a[lr][w]--;
			a[r][w]++;
			
			Oper newOper;
			newOper.sr = lr;
			newOper.sc = w;
			newOper.tr = r;
			newOper.tc = w;
				
			opers.push_back(newOper);			
		}
	}

	printf("%d\n", opers.size());
//	if (opers.size() >= 1)
//		prinf("%d")
	
	for (int i = 0 ; i < opers.size() ; i++)
	{
		printf("%d %d %d %d\n", opers[i].sr, opers[i].sc, opers[i].tr, opers[i].tc);
	}
	
	
		
	return 0;
}

Measured memory_bytes: 5232
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<functional>

using namespace std;

const int INF=1000000009;
struct edge{
	int t,c;
	edge(int t,int c):t(t),c(c){};
};
struct lca{
	int t,c;
};
typedef pair<int,int> P;
typedef pair<int,P> PP;

int N,M,K,Q;
int fest[100001];

int dist[100001];
bool used[100001];
vector<edge> G[100001];
vector<edge> tree[100001];

int root;
int depth[100001];
lca parent[20][100001];

void dfs(int v,int p,int deep){
	parent[0][v].t=p;
	parent[0][v].c=min(dist[v],(p!=-1 ? dist[p]:INF));
	depth[v]=deep;
	for(int i=0;i<tree[v].size();i++){
		if(tree[v][i].t!=p){
			dfs(tree[v][i].t,v,deep+1);
		}
	}
}

void rmg_init(int V){
	dfs(root,-1,0);
	for(int k=0;k+1<20;k++){
		for(int v=0;v<V;v++){
			if(parent[k][v].t<0){
				parent[k+1][v].t=-1;
			}else{
				parent[k+1][v].t=parent[k][parent[k][v].t].t;
				parent[k+1][v].c=min(parent[k][parent[k][v].t].c,parent[k][v].c);
				
			}
		}
	}
}

int query(int u,int v){
	int res;
	res=min(dist[u],dist[v]);
	if(depth[u]>depth[v])swap(u,v);
	for(int k=0;k<20;k++){
		if(((depth[v]-depth[u]) >> k) & 1){
			res=min(res,parent[k][v].c);
			v=parent[k][v].t;
		}
	}
	if(u==v)return min(res,dist[u]);
	for(int k=19;k>=0;k--){
		if(parent[k][u].t!=parent[k][v].t){
			res=min(res,min(parent[k][u].c,parent[k][v].c));
			u=parent[k][u].t;
			v=parent[k][v].t;
		}
	}
	return (min(res,parent[0][v].c));
}

void dijk(){
	fill(dist,dist+N,INF);
	priority_queue<P,vector<P>,greater<P> > que;
	for(int i=0;i<K;i++){
		que.push(P(0,fest[i]));
		dist[fest[i]]=0;
	}
	while(que.size()){
		P p=que.top();
		que.pop();
		int c=p.first,v=p.second;
		if(dist[v]<c)continue;
		for(int i=0;i<G[v].size();i++){
			edge e=G[v][i];
			if(dist[e.t]>c+e.c){
				dist[e.t]=c+e.c;
				que.push(P(c+e.c,e.t));
			}
		}
	}
}

void prim(){
	memset(used,false,sizeof(used));
	priority_queue<PP> que;
	que.push(PP(0,P(0,-1)));
	while(que.size()){
		PP p=que.top();
		que.pop();
		int c=p.first,v=p.second.first,pv=p.second.second;
		if(used[v])continue;
		used[v]=true;
		if(pv!=-1){
			tree[v].push_back(edge(pv,c));
			tree[pv].push_back(edge(v,c));
		}
		for(int i=0;i<G[v].size();i++){
			edge e=G[v][i];
			if(!used[e.t]){
				que.push(PP(e.c,P(e.t,v)));
			}
		}
	}
}

int main(void){
	scanf("%d%d%d%d",&N,&M,&K,&Q);
	for(int i=0;i<M;i++){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		a--,b--;
		G[a].push_back(edge(b,c));
		G[b].push_back(edge(a,c));
	}
	for(int i=0;i<K;i++){
		scanf("%d",&fest[i]);
		fest[i]--;
	}
	dijk();
	for(int i=0;i<N;i++){
		for(int j=0;j<G[i].size();j++){
			G[i][j].c=min(dist[i],dist[G[i][j].t]);
		}
	}
	prim();
	rmg_init(N);
	for(int i=0;i<Q;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		a--,b--;
		printf("%d\n",query(a,b));
	}
	
	return 0;
}

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

#ifdef _DEBUG
    #include "/home/v-o_o-v/deb.h"
    #define deb(x...)cerr << "[" << #x << "] = [";_print(x);
#else
    #define deb(x...)
#endif

#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    string s;
    cin >> s;
    int x = stoi(s.substr(0, 2)), y = stoi(s.substr(2));
    if((x > 12 && y > 12) || (x == 0 && y == 0))puts("NA");
    else if((x > 12 && y == 0) || (x == 0 && y > 12))puts("NA");
    else if(x <= 12 && y <= 12 && x > 0 && y > 0)puts("AMBIGUOUS");
    else if(x <= 12 && x > 0)puts("MMYY");
    else puts("YYMM");
    return 0;
}
// Write Here


Measured memory_bytes: 3656
#include <bits/stdc++.h>
using ll=long long;
using namespace std;
#define rep_i(i, n) for (int i = 0; i < (n); ++i)
#define rep_ll(i, n) for (long long i = 0; i < (n); ++i)
#define r_rep_i(i, start, end) for (int i = (start); i < (end); ++i)
#define r_rep_ll(i, start, end) for (long long i = (start); i < (end); ++i)
#define debug_vi(v) copy((v).begin(), (v).end(), ostream_iterator<int>(cout, " "));
#define debug_vll(v) copy((v).begin(), (v).end(), ostream_iterator<long long>(cout, " "));
#define debug_vd(v) copy((v).begin(), (v).end(), ostream_iterator<double>(cout, " "));
#define sort_v(v) sort((v).begin(), (v).end()); //昇順
#define d_sort_vi(v) sort((v).begin(), (v).end(), greater<int>()); //降
#define d_sort_vd(v) sort((v).begin(), (v).end(), greater<double>()); //昇順
#define say(t) cout << (t) << endl;
#define sum_vi(v) accumulate((v).begin(), (v).end(), 0);
#define sum_vll(v)accumulate((v).begin(), (v).end(), 0LL);

int main(){
  cin.tie(0);
  ios::sync_with_stdio(0);
  int n; cin >> n;
  vector<pair<int, int>> hoge(n);
  int a, b;
  rep_i(i, n){
    cin >> a >> b;
    // b基準でソートするため.
    hoge[i] = make_pair(b, a);
  }

  sort_v(hoge);
  ll time = 0;
  // rep_i(i, n){
  //   cout << hoge[i].second << ":" << hoge[i].first << endl;
  // }
  rep_i(i, n){
    time += (ll)hoge[i].second;
    if(time > (ll)hoge[i].first){
      // cout << "i:" << i << endl;
      // cout << "time:" << time << endl;
      say("No");
      return 0;
    }
  }
  say("Yes");
}

Measured memory_bytes: 1792
#pragma comment(linker, "/stack:200000000")
        #pragma GCC optimize ("Ofast")
        #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
        #include <iostream>
        #include <iomanip>
        #include <sstream>
        #include <cstring>
        #include <vector>
        #include <deque>
        #include <queue>
        #include <set>
        #include <map>
        #include <valarray>
        #include <iterator>
        #include <functional>
        #include <limits>
        #include <algorithm>
        #include <numeric>
        #include <cmath>
        #include <cassert>
        #include <unordered_map>
        #include <unordered_set>
        #include <stack>
        using namespace std;
        #define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
         #define trace(x) cerr << #x << ": " << x << " " << endl;
     
        typedef int64_t ll;
     
        #define endl '\n'
        #define int ll
        ll mod=1e9+7;
        ll mod1=1e9+5;
        ll power(ll a,ll b)
        {
            if(b==0) return 1;
            else if(b%2==0)
                return power((((a%mod)*(a%mod))%mod),b/2)%mod;
            else return ((a%mod)*(power((((a%mod)*(a%mod))%mod),b/2)%mod))%mod;
        }
        int a[301][301];
        int c=0;
        int n,m;
        int init[501][501];

     int32_t main()
        {
        IOS
    
            

            int x,y;
            cin>>x>>y;
            if(x==1 and y==1)
            {
                cout<<1000000;
                return 0;
            }
            if(x==2 and y==2)
            {
                cout<<400000;
                return 0;
            }
            if(x==3 and y==3)
            {
                cout<<200000;
                return 0;
            }
            if(x==1 and y==2)
            {
                cout<<500000;
                return 0;
            }
            if(x==1 and y==3)
            {
                cout<<400000;
                return 0;
            }
            if(x==3 and y==1)
            {
                cout<<400000;
                return 0;
            }
            if(x==2 and y==3)
            {
                cout<<300000;
                return 0;
            }
            if(x==3 and y==2)
            {
                cout<<300000;
                return 0;
            }
            if(x==2 and y==1)
            {
                cout<<500000;
                return 0;
            }
            x=min(x,y);
            if(x==1)
            {
                cout<<300000;
                return 0;
            }
            if(x==2)
            {
                cout<<200000;
                return 0;
            }
            if(x==3)
            {
                cout<<100000;
                return 0;
            }
            cout<<0;
        }

Measured memory_bytes: 256
/*
 * C言語のサンプルプログラム - Webkaru
 * - 入力した文字がアルファベットの小文字か大文字かを判定 -
 */
#include<stdio.h>
 
int main(void){
 
  int i;
 
  /* 文字 */
  char moji;

  scanf("%c", &moji);
 
  /* アルファベットの小文字か大文字かを判定 */
  if((moji>= 'a') && (moji<='z')){
    printf("a");
  }
  else if((moji>= 'A') && (moji<='Z')){
    printf("A");
  }
 
  return 0;
}


Measured memory_bytes: 1980
#include<stdio.h>
int main(void){
	int i=1,x,y,temp;
	while(i<=3000){
		scanf("%d %d",&x,&y);
		if (x==0 && y==0){
			break;
		}
		if (x>y){
			temp=x;
			x=y;
			y=temp;
		}
		printf("%d %d\n",x,y);
		i++;
	}
return 0;
}

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

using ll = long long;
const int mod = 1e9 + 7;

ll calc(ll H) {
    if (H == 1)
        return 1;
    return calc(H / 2) * 2 + 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll H;
    cin >> H;
    cout << calc(H) << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <climits>
#include <iomanip>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
int main(){
  ll n,k;
  cin >> n >> k;
  vector<ll> a(n);
  for(int i = 0;i < n;i++)cin >> a[i];
  vector<ll> b(n);
  for(int i = 0;i < k;i++){
    for(int j = 0;j < n;j++)b[j] = 0;
    for(int j = 0;j < n;j++){
      b[max((ll)0,(ll)j - a[j])]++;
      if(j + a[j] + 1< n)b[j + a[j] + 1]--;
    }
    bool fin = true;
    for(int j = 0;j < n;j++){
      if(j == 0)a[0] = b[0];
      else a[j] = a[j - 1] + b[j];
      if(a[j] != n)fin = false;
    }
    //cout << "i" << i << endl;
    if(fin)break;
  }
  for(auto i:a)cout << i << " ";
  cout << endl;
}

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

int main() {
  int N, A = 0, B = 0;
  cin >> N;
  vector<int> a(N);
  for (int i = 0; i < N; i++){
    cin >> a.at(i);
  }
  sort(a.begin(), a.end());
  reverse(a.begin(), a.end());
  
  for (int i = 0; i < N; i++){
    if (i % 2 == 0){
      A += a[i];
    }
    else{
      B += a[i];
    }
  }

  cout << A-B << endl;
}

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

using namespace std;

int n;

long long q, ans;

vector < long long > a, b;

int main() {
    cin >> n;
    a.resize(n + 1);
    b.resize(n + 1);
    for (int i = 0; i < n; ++i) {
        cin >> a[i] >> b[i];
    }
    for (int i = n - 1; i >= 0; --i) {
        a[i] += q;
        if (a[i] % b[i] != 0) {
            long long x = ((a[i] / b[i]) + 1) * b[i] - a[i];
            ans += x;
            q += x;
        }
    }
    cout << ans;
}


Measured memory_bytes: 1792