akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <iomanip>
#include <string>
#include <map>
#include <math.h>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <set>
#include <queue>
#include <sstream>
#include <stack>
#include <deque>
#include <memory.h>
#include <cassert>
#include <ctime>
#include <climits>
#include <list>
#include <time.h>
#include <unordered_map>
#include <bitset>
#include <exception>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned long long ull;
#define pb push_back
#define mp make_pair
#define FILE "file"
#define lc v << 1
#define rc (v << 1) + 1
#define inf 1e+9
#define linf ll(1e+18)
#define dinf 1e+14

typedef long long ll;
#define pb push_back
#define mp make_pair

vector<int> a, b;

void solve()
{
    int n, k;
    cin >> n >> k;
    
    for(int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        if(x >= 0)
        {
            a.pb(x);
        }
        else
        {
            b.pb(-x);
        }
    }
    
    int na = (int) a.size();
    int nb = (int) b.size();
    
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    
    int res = inf;
    
    if(k <= na)
    {
        res = min(res, a[k - 1]);
    }
    
    if(k <= nb)
    {
        res = min(res, b[k - 1]);
    }
    
    for(int i = 0, j = k - 2; i < na; i++, j--)
    {
        if(j >= 0 && j < nb)
        {
            //cout << i << " " << j << " " << a[i] << " " << b[j] << "\n";
            int temp = min(2 * a[i] + b[j], 2 * b[j] + a[i]);
            res = min(res, temp);
        }
        
    }
    cout << res;
    
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    //freopen("/Users/bekhzodsoliev/Desktop/C++/cp/cp/file.in", "r", stdin);freopen("/Users/bekhzodsoliev/Desktop/C++/cp/cp/file.out", "w", stdout);
    
    int t = 1;
    //cin >> t;
    
    while(t--)
    {
        solve();
    }
    
    return 0;
}


Measured memory_bytes: 1020
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef set<int> si;
typedef pair<int,int> pii;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define per(i,a,b) for(int i=(b)-1; i>=(a); --i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define F first
#define S second

const ll MOD = 1e9+7;

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	//freopen("in.txt", "r", stdin);
	int n, m;
	cin >> n >> m;
	map<int, int> y;
	map<int, int> x;
	rep(i,0,n) {
		int a;
		cin >> a;
		y[a] = i;
	}
	rep(i,0,m) {
		int b;
		cin >> b;
		x[b] = i;
	}
	ll ret = 1;
	ll A = 0;
	ll B = 0;
	per(i,1,n*m+1) {
		bool flagy = (y.find(i) != y.end());
		bool flagx = (x.find(i) != x.end());
		if(flagy && flagx) {
			A++; B++;
		} else if(flagy) {
			ret = ret * B % MOD;
			A++;
		} else if(flagx) {
			ret = ret * A % MOD;
			B++;
		} else {
			ll loc = A * B - (ll)(n*m - i);
			ret = ret * loc % MOD;
		}
	}
	cout << ret << '\n';
}

Measured memory_bytes: 384
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
sum = 0
for i in range(N):
  sum += B[A[i]-1]
  if i >=1:
    if A[i]==A[i-1]+1:
      sum += C[A[i-1]-1]
    
print(sum)
    

Measured memory_bytes: 3060
n = int(input())
a = list(map(int,input().split()))
order_counter = 1
is_not_minus = False
for i in range(n):
    if a[i] == order_counter:
        order_counter += 1
        is_not_minus = True

if is_not_minus:
    print(n - order_counter + 1)
else:
    print(-1)

Measured memory_bytes: 32356
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pl;
typedef pair<int,int> pi;
typedef pair<ll,pl> pp;
const ll MOD = 1e9+7;
const ll MAX = 1e18*2;

int main(){
  ll n,k,h[111111];
  cin>>n>>k;
  for(int i=0;i<n;i++)cin>>h[i];
  ll dp[111111];
  fill_n(dp,111111,MAX);
  dp[0]=0;
  for(int i=0;i<n;i++){
    for(int j=1;j<=k;j++){
	 if(i+j<n)dp[i+j]=min(dp[i+j],dp[i]+abs(h[i]-h[i+j]));
    }
  }
  cout<<dp[n-1]<<endl;
  return 0;
}


Measured memory_bytes: 1920
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

const (
	initialBufSize = 100000
	maxBufSize     = 10000000
)

var (
	sc = bufio.NewScanner(os.Stdin)
	wt = bufio.NewWriter(os.Stdout)
)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	i, _ := strconv.Atoi(next())
	return i
}

func puts(a ...interface{}) {
	fmt.Fprintln(wt, a...)
}

func divFloor(a, b int) int {
	return (a + (b - 1)) / b
}

type Mon struct {
	x, h int
}

type Mons []Mon

func (a Mons) Len() int      { return len(a) }
func (a Mons) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
func (a Mons) Less(i, j int) bool {
	return a[i].x < a[j].x
}

func upperBound(a []int, key int) int {
	l, r := 0, len(a)-1
	for l <= r {
		mid := (l + r) / 2
		if a[mid] <= key {
			l = mid + 1
		} else {
			r = mid - 1
		}
	}
	return l
}

func main() {
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, initialBufSize), maxBufSize)
	defer wt.Flush()

	n, d, a := nextInt(), nextInt(), nextInt()
	mons := make(Mons, n)
	for i := 0; i < n; i++ {
		x, h := nextInt(), nextInt()
		mons[i] = Mon{x, h}
	}
	sort.Sort(mons)
	x, h := make([]int, n), make([]int, n)
	for i := range mons {
		x[i], h[i] = mons[i].x, mons[i].h
	}

	ans := 0
	s := make([]int, n+1)
	for i := 0; i < n; i++ {
		if s[i] < h[i] {
			// 攻撃回数
			need := (h[i] - s[i] + a - 1) / a
			// 攻撃範囲
			r := upperBound(x, x[i]+2*d)
			s[i] += need * a
			s[r] -= need * a
			ans += need
		}
		s[i+1] += s[i]
	}

	puts(ans)
}


Measured memory_bytes: 13828
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;

int main() {
  int n;
  string s, t;
  cin >> n >> s >> t;
  for (int i = 0; i < n; i++) {
    cout << s[i] << flush;
    cout << t[i] << flush;
  }
  cout << endl;
  return 0;
}

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

// dump macro{{{
// http://www.creativ.xyz/dump-cpp-652
#define DUMPOUT cerr // 変数ダンプ先。coutかcerr

#ifdef PCM
// 引数はいくつでもどんな型でも可（ストリーム出力演算子があればOK）
#define dump(...) DUMPOUT<<"  "; \
  DUMPOUT<<#__VA_ARGS__; \
  DUMPOUT<<":=> "; \
  dump_func(__VA_ARGS__); DUMPOUT<<"in ["<<__LINE__<<":"<<__FUNCTION__<<"]"<<endl;
#define dump_1d(x,n) DUMPOUT <<"  " \
  <<#x<<"["<<#n<<"]"<<":=> {"; \
  rep(i,n){ DUMPOUT << x[i] << (((i)==(n-1))?"}":", "); } DUMPOUT <<" in [" << __LINE__ << "]" << endl;

#define dump_2d(x,n,m) DUMPOUT <<"  " \
    <<#x<<"["<<#n<<"]"<<"["<<#m<<"]"<<":=> \n"; \
    rep(i,n)rep(j,m){ DUMPOUT << ((j==0)?"     |":" ") << x[i][j] << (((j)==(m-1))?"|\n":" "); } \
    DUMPOUT <<"  in [" << __LINE__ << "]" << endl;
#else
#define dump(...) 42
#define dump_1d(...) 42
#define dump_2d(...) 42
#endif

// デバッグ用変数ダンプ関数
void dump_func() {
}
template <class Head, class... Tail>
void dump_func(Head&& head, Tail&&... tail)
{
    DUMPOUT << head;
    if (sizeof...(Tail) == 0) {
        DUMPOUT << " ";
    }
    else {
        DUMPOUT << ", ";
    }
    dump_func(std::move(tail)...);
}

// vector出力
template<typename T>
ostream& operator << (ostream& os, vector<T>& vec) {
    os << "{";
    for (int i = 0; i<vec.size(); i++) {
        os << vec[i] << (i + 1 == vec.size() ? "" : ", ");
    }
    os << "}";
    return os;
}/*}}}*/

#define rep(i, x) for(int i = 0; i < (int)(x); i++)/*{{{*/
#define reps(i,x) for(int i = 1; i <= (int)(x); i++)
#define rrep(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define rreps(i,x) for(int i=((int)(x));i>0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define RFOR(i, m, n) for(int i = m;i >= n;i--)
#define foreach(x,a) for(auto& (x) : (a) )
#define all(x) (x).begin(),(x).end()
#define sum(v) accumulate(all(v), 0)
#define sz(x) ((int)(x).size())
#define fill(x,y) memset(x,y,sizeof(x))
#define pb(a) push_back(a)
#define INF 2147483647
#define INFLL 1000000000000000000LL
#define MOD 1000000007/*}}}*/

struct Fast {Fast(){std::cin.tie(0);ios::sync_with_stdio(false);}} fast;/*{{{*/
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<long long> vll;
typedef vector<vll> vvll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<vii> vvii;
typedef tuple<int,int,int> iii;
typedef set<int> si;
typedef complex<double> pnt;
typedef vector<pnt> vpnt;
typedef priority_queue<pii,vii,greater<pii> > spq;
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

/*}}}*/

// global variables

int main() {
  ll h,w;cin>>h>>w;

  ll res = 1000000000000000;

  ll a,b,r;
  FOR(i, 1, h){
    r = h-i;
    a = (r/2)*w;
    b = ((r+2-1)/2)*w;
    res = min(res, max(abs(i*w-a), abs(i*w-b)));

    a = (w/2)*r;
    b = ((w+2-1)/2)*r;
    res = min(res, max(abs(i*w-a), abs(i*w-b)));
  }

  FOR(i, 1, w){
    r = w-i;
    a = (r/2)*h;
    b = ((r+2-1)/2)*h;
    res = min(res, max(abs(i*h-a), abs(i*h-b)));

    a = (h/2)*r;
    b = ((h+2-1)/2)*r;
    res = min(res, max(abs(i*h-a), abs(i*h-b)));
  }

  cout << res << endl;

  return 0;
}


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

using namespace std;

#define fi first
#define se second
#define eb emplace_back
#define mt make_tuple
#define all(x) (x).begin(), (x).end() 
#define MOD 1000000007

typedef long long ll;
typedef pair <int, int> ii;
typedef pair <ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef long double ld;

ll INF=LLONG_MAX;

int const mxn=2e5+5;
int n;
vi adj[mxn];
ll subans[mxn],ans[mxn],sz[mxn],fac[mxn],ifac[mxn];

ll modpow(ll a, ll b) // put b = mod-2, calc for (x!)^(mod-2) % mod only, [use x^(mod-2) when x^-1] 
{
	ll r=1;
	while(b)
	{
		if(b&1)r=(r*a)%MOD;
		a=(a*a)%MOD;
		b>>=1;
	}
	return r;
}

void multi(ll &a, ll b){
	a%=MOD; b%=MOD; a*=b; a%=MOD;
}

void seive(int n){
	fac[0]=ifac[0]=1;
	for(int i=1; i<n; i++){
		fac[i]=fac[i-1]*1LL*i%MOD;
		ifac[i]=modpow(fac[i],MOD-2);
	}
	return;
}

int dfs1(int u, int p=-1){
	sz[u]=1;
	for(auto v:adj[u]){
		if(v==p)continue;
		sz[u]+=dfs1(v,u);
	}
	subans[u]=fac[sz[u]-1];
	for(auto v:adj[u]){
		if(v==p)continue;
		(subans[u] *= subans[v])%=MOD;
		(subans[u] *= ifac[sz[v]])%=MOD;
	}
	return sz[u];
}

void dfs2(int u, int p=-1){
	ans[u] = fac[n-1];
	for(auto v:adj[u]){
		(ans[u]*=subans[v])%=MOD;
		(ans[u]*=ifac[sz[v]])%=MOD;
	}
	for(auto v:adj[u]){
		if(v==p)continue;
		subans[u]=ans[u]%MOD;
		multi(subans[u],ifac[n-1]); 
		multi(subans[u],fac[n-1-sz[v]]);
		multi(subans[u],fac[sz[v]]);		
		multi(subans[u],modpow(subans[v],MOD-2));
		sz[u]=n-sz[v];
		dfs2(v,u);
	}
	return;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
	int u,v;
	cin >> n;
	seive(n);
	for(int i=0; i<n-1; i++){
		cin >> u >> v;
		u--; v--;
		adj[u].eb(v);
		adj[v].eb(u);
	}
	dfs1(0); dfs2(0);
	for(int i=0; i<n; i++){
		cout << ans[i] << endl;
	}
}
	
// READ & UNDERSTAND
// ll, int overflow, array bounds, memset(0)
// special cases (n=1?), n+1 (1-index)
// do smth instead of nothing & stay organized
// WRITE STUFF DOWN


Measured memory_bytes: 21748
import math
import numpy as np
x1, y1, x2, y2 = map(int, input().split())
R = np.array([[0, 1], [-1, 0]])
a = np.array([x1, y1])
b = np.array([x2, y2])
ab = b - a
d = ab.dot(R) + a
da = a - d
c = da.dot(R) + d
print(c[0], c[1], d[0], d[1])


Measured memory_bytes: 12504
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#define maxn 200010
using namespace std;
struct node{
    int to,wi;
    node*next;
}*con[maxn];
void addedge(int x,int y,int w)
{
    node*p=new node;
    p->to=y;
    p->wi=w;
    p->next=con[x];
    con[x]=p;
}
int n,m,dist[maxn],l[maxn],r[maxn],w[maxn];
bool vis[maxn];
void dfs(int v,int dis)
{
    dist[v]=dis;vis[v]=true;
    for(node*p=con[v];p;p=p->next)
        if(!vis[p->to]) dfs(p->to,dis+p->wi);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&l[i],&r[i],&w[i]);
        addedge(l[i],r[i],w[i]);addedge(r[i],l[i],-w[i]);
    }
    for(int i=1;i<=n;++i)
        if(!vis[i]) dfs(i,0);
    for(int i=1;i<=m;++i)
    {
        if(dist[r[i]]-dist[l[i]]!=w[i]) {
            printf("No");
            return 0;
        }
    }
    printf("Yes");
    return 0;
}


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

namespace Atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
          // test3
            long[] vs = new long[100001];
            var NK = Console.ReadLine().Split(' ').Select(long.Parse).ToArray();
            for (int i = 0; i < NK[0]; i++)
            {
                int[] ab = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
                vs[ab[0]] += ab[1];
            }
            long K = NK[1];
            for (int i = 0; i < vs.Length; i++)
            {
                K -= vs[i];
                if (K <= 0)
                {
                    Console.WriteLine(i);
                    break;
                }
            }

            ;
        }
    }
}


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

namespace AtCoder.Abc
{
    class QuestionB
    {
        public static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);

            string s = Console.ReadLine();
            string t = Console.ReadLine();

            long slen = s.Length;
            long tlen = t.Length;

            long result = tlen;
            long tempresult = 0;

            for (int i = 0; i <= slen-tlen; i++)
            {
                var st = s.Substring(i, (int)(tlen));
                //stとtの、重複具合を調べる
                for (int j = 0; j < tlen; j++)
                {
                    if (st[j] != t[j])
                    {
                        tempresult++;
                    }
                }

                if (tempresult < result)
                {
                    result = tempresult;
                }

                //debug
                //Console.WriteLine($"debug: i {i}, tempresult {tempresult}, result {result}, st {st}");

                tempresult = 0; //tempの初期化
            }


            Console.WriteLine(result);

            Console.Out.Flush();
        }

    }
}


Measured memory_bytes: 26068
n=int(input())
d,x=map(int,input().split())
chocho=0

for i in range(n):
  j=1
  chocho+=1
  A=int(input())
  tmp=j*A+1
  while tmp <= d:
    j+=1
    tmp=j*A+1
    chocho+=1
print(chocho+x)




Measured memory_bytes: 2940
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n;
		n = sc.nextInt();
		sc.close();
		int r = n % 10;
		int r2 = n / 10;
		if (r != 9 && r2 != 9)
			System.out.println("No");
		else
			System.out.println("Yes");
	}

}


Measured memory_bytes: 22356
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int x = scan.nextInt();
        int y = scan.nextInt();
        Boolean[][] dp=new Boolean[101][101];
        boolean as = dfs(x,y,dp);
        System.out.println(as ? "Yes" : "No");
    }

    private static boolean dfs(int x, int y, Boolean[][] dp) {
        if(y < 0){
            return false;
        }
        if(x <= 0){
            return x == 0 && y == 0;
        }
        if(dp[x][y] != null) return dp[x][y];
        return dp[x][y] = dfs(x-1,y-2,dp) || dfs(x-1,y-4,dp);
    }
}


Measured memory_bytes: 35788
#include<map>
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define mem(a,b) memset(a,b,sizeof(a))
#define  For(i,a,b) for(int i=a,i##E=b;i<=i##E;++i)
#define rFor(i,a,b) for(int i=a,i##E=b;i>=i##E;--i)
using namespace std;
typedef long long LL;
template<typename T>inline T chkmax(T A,T B){return A>B?A:B;}
template<typename T>inline T chkmin(T A,T B){return A<B?A:B;}
template<typename T>inline void read(T &x)
{
	x=0;int _f(0);char ch=getchar();
	while(!isdigit(ch))_f|=(ch=='-'),ch=getchar();
	while( isdigit(ch))x=x*10+ch-'0',ch=getchar();
	x=_f?-x:x;
}
inline void file()
{
#ifndef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
}
int n;
LL Max1,Max2;
map<int,int>mp;
int main()
{
	int x;
	read(n);
	For(i,1,n)
	{
		read(x);
		if(mp[x])
		{
			mp.erase(x);
			if(x>=Max1)
			{
				Max2=Max1;
				Max1=x;
			}
			else
			if(x>Max2)Max2=x;
		}
		else mp[x]=1;
	}
	printf("%lld\n",Max1*Max2);
	return 0;
}


Measured memory_bytes: 4992
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
#include <stack>
#include <functional>

#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
    #define eprintf(...) 42
#endif

#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define repp(i, m, n) for(int i = m, i##_len = (n); i < i##_len; ++i)
#define reprev(i, n) for(int i = (n-1LL); i >= 0; --i)
#define all(x) (x).begin(), (x).end()
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; }
template <class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair <int,int> P;
typedef long double ld;

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n, m;
    cin >> n >> m;
    vector<ll> a(n);
    rep (i, n) {
        cin >> a[i];
        a[i] /= 2;
    }
    sort(all(a));
    ll l = 1;
    rep (i, n) {
        l = l / gcd(l, a[i]) * a[i];
        if (l > m) {
            cout << "0\n";
            return 0;
        }
    }
    bool c = true;
    rep (i, n) {
        if ((l / a[i]) % 2 == 0) c = false;
    }
    if (c) cout << (m + l) / (2 * l) << "\n";
    else cout << "0\n";
    return 0;
}

Measured memory_bytes: 1024
class RollingHash:
    def __init__(self, s: list, base: int = 1007, mod: int = 10**9 + 7):
        self.s = s
        self.n = len(s)
        self.base = base
        self.mod = mod

        # preprocess
        self.h_cum = [0] * (self.n + 1)  # h_cum[i] = (hash of s[:i])
        self.b_pow = [1] * (self.n + 1)  # b_pow[i] = base ** i
        # for i in range(self.n):
        #     self.h_cum[i + 1] = (self.h_cum[i] * base + s[i]) % mod
        #     self.b_pow[i + 1] = (self.b_pow[i] * base) % mod
        for i, si in enumerate(s):
            self.h_cum[i + 1] = (self.h_cum[i] * base + si % mod) % mod
            self.b_pow[i + 1] = (self.b_pow[i] * base) % mod

    def get_hash(self, l: int, r: int) -> int:
        # get hash value of the substring s[l:r]
        hash_val = self.h_cum[r] - self.h_cum[l] * self.b_pow[r - l] % self.mod
        if hash_val < 0:
            hash_val += self.mod
        return hash_val


# class RollingHashMulti:
#     def __init__(self,
#                  s: list,
#                  base_list: list = [1007, 2009],
#                  mod_list: list = [10**9 + 7, 10**9 + 9]):
#         self.n = len(base_list)
#         self.base_list = base_list
#         self.mod_list = mod_list
#         self.rh_list = [
#             RollingHash(s, base_list[i], mod_list[i]) for i in range(self.n)
#         ]
#
#     def get_hash(self, l: int, r: int) -> tuple:
#         return tuple(self.rh_list[i].get_hash(l, r) for i in range(self.n))

n = int(input())
a = tuple(map(int, input().split()))
b = tuple(map(int, input().split()))

# a_xor = [a[i % n] ^ a[(i + 1) % n] for i in range(n * 2)]
# b_xor = [b[i % n] ^ b[(i + 1) % n] for i in range(n * 2)]
a_xor = [a[i % n] ^ a[(i + 1) % n] for i in range(n)] * 2
b_xor = [b[i % n] ^ b[(i + 1) % n] for i in range(n)] * 2

a_xor_rh = RollingHash(a_xor)
b_xor_rh = RollingHash(b_xor)

b_hash = b_xor_rh.get_hash(0, n)
for k in range(n):
    if a_xor_rh.get_hash(k, k + n) == b_hash:
        x = a[k] ^ b[0]
        print(k, x)


Measured memory_bytes: 99636
//
//  main.cpp
//  HelloWorld
//
//  Created by purple on 2020/04/13.
//  Copyright © 2020 Purple. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <string>
#include <fstream>
#include <cmath>

using namespace std;

int main(int argc, const char * argv[]) {



    int n;
    cin >> n;
    
    int tmp;
    
    for(int i=1; i<=n; i++){
        tmp = i;

        if(tmp%3==0)
            cout << " " << i;
        else{

            while(1){
                if(tmp%10 == 3){
                    cout << " " << i;
                    break;
                }

                tmp /= 10;

                if(tmp==0)
                    break;
            }
        }
    }

    cout << endl;
    return 0;
    
}



Measured memory_bytes: 3100
package main

import (
	"fmt"
	"math"
)

func main() {
	var N int
	fmt.Scan(&N)
	ws := make([]int, N)
	for i := range ws {
		fmt.Scan(&ws[i])
	}
	wa := make([]int, N)
	wa[0] = ws[0]
	for i := 1; i < N; i++ {
		wa[i] = wa[i-1] + ws[i]
	}
	m := math.MaxInt64
	for i := 1; i < N-1; i++ {
		b := wa[i]
		a := wa[N-1] - wa[i]
		m = min(m, abs(a-b))
	}
	fmt.Println(m)
}

func min(a, b int) int {
	if b < a {
		return b
	}
	return a
}
func abs(a int) int {
	return int(math.Abs(float64(a)))
}


Measured memory_bytes: 512
#include "bits/stdc++.h"
using namespace std;

int main()
{
	long N, A, B;
	cin >> N >> A >> B;
	long round = 0;
	long L = max(A, B);
	long S = min(A, B);
	long shift = min(S-1, N - L);
	if ((L - S) % 2 == 1) 
	{
		round += shift + 1;
	}
	round += (L - S) / 2;
	cout << round;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,j) for (int (i)=0;(i)<(int)(j);++(i))
#define put(i) cout << (i) << endl
using namespace std;
typedef long long ll;
const int mod = 1e9+7;

int main() {
    int n, m, ans = 0; cin >> n >> m;
    vector<int> b(n, 1);
    vector<int> a(n, 0); a[0] = 1;
    vector<int> c(n, 0);
    c[0] = 1;
    rep(i, m) {
        int x, y; cin >> x >> y; x--; y--;
        if (a[x]) {
            if (b[x] >= 1) { c[y] = 1; }
            if (b[x] == 1) { c[x] = 0; }
            a[x] = 0;
            a[y] = 1;
        }
        else {
            if (c[x]) {
                if (b[x] >= 1) { c[y] = 1; }
                if (b[x] == 1) { c[x] = 0; }
            }
        }
        b[x]--;
        b[y]++;
    }

    for (int i = 0; i < c.size(); ++i) {
        if (c[i] && b[i]) ans++;
    }

    cout << ans << endl;
}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
#define int long long
using namespace std;
int mod = 1000000007;
 int c[26];
main() {
    //freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    string s;
    cin >> s;
    for (int i=0; i < n; i++){
        c[s[i]-'a']++;
    }
    int ans = 1;
    for (int i=0; i < 26; i++){
        ans *= (c[i]+1);
        ans %= mod;
    }
    ans--;
    if (ans<0) ans += mod;
    cout << ans;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#include <climits>
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define srep(i, begin, end) for (__typeof(end) i = begin; i != end; i++)
#define si(x) int x = scanInt();
#define sll(x) LL x = scanLong();
#define sci(x) int x; scanf("%d", &x);
#define scll(x) LL x; scanf("%lld", &x);
#define pi(x) printf("%d ", x)
#define pll(x) printf("%lld ", x)
#define nl printf("\n")
#define clr(a) memset(a, 0, sizeof(a))
#define PB push_back
#define MP make_pair
using namespace std;
typedef unsigned int UI; // 32 bit integer
typedef long int LI; // 32 bit integer
typedef unsigned long int ULI; // 32 bit unsigned integer
typedef long long int LL; // 64 bit integer
typedef unsigned long long int  ULL; // 64 bit unsigned integer
typedef long double LD;
typedef vector<int> VI;
typedef vector<LL> VLL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
const LL MOD = 1e9+7;

/* Fast I/O */
inline int scanInt() {
	int n = 0;
	char ch = getchar();
	int sign = 1;
	while(ch < '0' || ch > '9') {
		if(ch == '-')	sign = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9') {
		n = (n<<1)+(n<<3)+(int)(ch-'0');
		ch = getchar();
	}
	return n*sign;
}

inline LL scanLong() {
	LL n = 0;
	char ch = getchar();
	LL sign = 1;
	while(ch < '0' || ch > '9') {
		if(ch == '-')	sign = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9') {
		n = (n<<1)+(n<<3)+(LL)(ch-'0');
		ch = getchar();
	}
	return n*sign;
}

const LL MAXN = 1e5+10;
LL N, M;
PLL edges[MAXN], subsets[MAXN];
LL inconvenience[MAXN];

LL find(LL x) {
	if(x != subsets[x].first)
		subsets[x].first = find(subsets[x].first);
	return subsets[x].first;
}

LL unite(LL a, LL b) {
	LL rootA = find(a);
	LL rootB = find(b);
	if(rootA == rootB)	return 0;
	LL pairs = subsets[rootA].second * subsets[rootB].second;
	if(rootA > rootB)	swap(rootA, rootB);
	subsets[rootB].first = rootA;
	subsets[rootA].second += subsets[rootB].second;
	return pairs;
}

int main() {
	N = scanLong(); M = scanLong();
	rep(i, 1, N+1)	subsets[i] = make_pair(i, 1);
	rep(i, 0, M) {
		edges[i].first = scanLong();
		edges[i].second = scanLong();
	}
	inconvenience[M] = N*(N-1)/2;
	rep(i, M, 0) {
		inconvenience[i] = inconvenience[i+1] - unite(edges[i].first, edges[i].second);
	}
	rep(i, 1, M+1)	pll(inconvenience[i]-inconvenience[0]), nl;
}


Measured memory_bytes: 5376
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        for (;;) {
            int n = sc.nextInt();
            if (n == 0) {
                break;
            }
            int m = sc.nextInt();
            char[] s = sc.next().toCharArray();
            int count = 0;
            int[] a = new int[m];
            for (int i = 2; i < m; i++) {
                if (s[i - 2] == 'I' && s[i - 1] == 'O' && s[i] == 'I') {
                   a[i]=a[i-2]+1;
                   if(n<=a[i]) {
                       count++;
                   }
                }
            }
            System.out.println(count);
        }
    }
}


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

#define mod 1000000007

using namespace std;
typedef long long ll; 
 
int main(void){
	
	int N;
	
	cin >> N;
	
	ll A[N], out[N] = {}, sum = 0;
	
	for(int i=0; i<N; i++){
		cin >> A[i];
		//A[i] *= 2;
	}
	
	
	for(int i=0; i<N; i++){
		if(i%2 == 0)
			sum += A[i];
		else
			sum -= A[i];
	}
	out[0] = sum;
	for(int i=1; i<N; i++){
		out[i] = abs(A[i-1]*2 - out[i-1]); 
	}
	
	for(int i=0; i<N; i++)
		cout << out[i] << " ";
	
	return 0;
}

Measured memory_bytes: 2816
#define _USE_MATH_DEFINES

#include <cstdio>
#include <cstdlib>
#include <string.h>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>

using namespace std;

typedef pair<long long int, long long int> P;
long long int INF = 1e18;
long long int MOD = 1000000007;

int main(){
	
	long long int N, T;
	cin >> N >> T;
	
	vector<long long int> v;
	
	for(int i = 0; i < N; i++){
		long long int num;
		cin >> num;
		v.push_back(num);
	}
	
	sort(v.begin(), v.end());
	
	long long int ans = 1;
	for(int i = 1; i < N; i++){
		int pos = lower_bound(v.begin(), v.end(), v[i] - T) - v.begin();
		ans *= i - pos + 1;
		ans %= MOD;
	}
	
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 3928
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<cstdio>
#include<sstream>
#include<iomanip>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef pair<int,pii> pip;
typedef vector<pip>vip;
const double PI=acos(-1);
const double EPS=1e-8;
const int inf=1e8;
int main(){
	int n;
	cin>>n;
	for(int i=1;;i++)if(i*(i+1)/2>=n){
		int sum=i;
		cout<<i<<endl;
		i--;
		while(n!=sum){
			if(sum+i<=n){
				sum+=i;
				cout<<i<<endl;
			}
			i--;
		}
		break;
	}
}








Measured memory_bytes: 256
#include <iostream>
#include <vector>

using namespace std;
int main (){
  int a,b,c,x,y;
  cin >> a >> b >> c >> x >> y ;
  int smaller = min(x,y);
  x -= smaller;
  y -= smaller;
  cout << min(a+b,2*c)*smaller + min(a*x+y*b,max(x,y)*2*c )<< endl;
                                     }                                     
 

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i,k,n)  for(int i = (k);i < (n);++i)
#define REP(i,n)    FOR(i,0,n)
#define ALL(x)      begin(x),end(x)

using namespace std;
using vecint = vector<int>;
using ll = int64_t;

int main()
{
  int n;
  cin>>n;
  vecint a(n);
  REP(i,n)cin>>a[i];
  vecint f(n+1), b(n+1);
  f[0] = 0;
  REP(i,n) f[i+1] = max(f[i], a[i]);
  b[n] = 0;
  for(int i=n-1; i>=0; --i) b[i] = max(b[i+1], a[i]);
  REP(i,n) {
    cout<<max(f[i], b[i+1])<<endl;
  }
  return 0;
}


Measured memory_bytes: 3968
takahashi,aoki,k=gets.split.map &:to_i
turn='takahashi'
k.times do
  if turn=='takahashi'
    aoki+=takahashi/2
    takahashi/=2
    turn='aoki'
  else
    takahashi+=aoki/2
    aoki/=2
    turn='takahashi'
  end
end
print "#{takahashi} #{aoki}"


Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define fi first
#define se second
long long mo = 1e9 + 7;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
template<class A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}cout << "\n";}
ld PI=3.14159265358979323846;
 
int main(){
    ll N, C;
    cin >> N >> C;
    vector<ll> x(N), v(N);
    vector<ll> SXL(N+1), SXR(N+1), SVL(N+1), SVR(N+1);
    rep(i,N){
        cin >> x[i] >> v[i];
    }
    rep(i,N){
        SXL[i+1] = x[i];
        SVL[i+1] = SVL[i] + v[i];
    }
    for(ll i = N;i>0;i--){
        SXR[i-1] = C - x[i-1];
        SVR[i-1] = SVR[i] + v[i-1];
    }
    vector<ll> f(N+1), g(N+1);
    rep(i,N+1){
        f[i] = SVL[i] - SXL[i];
    }
    rep(i,N){
        g[i+1] = max(g[i], f[i+1]); 
    }
    ll ans = 0;
    for(ll i=N;i>=0;i--){
        cmax(ans, g[i] + SVR[i] - SXR[i]*2);
    }
    vector<ll> ff(N+1), gg(N+1);
    for(ll i=N;i>=0;i--){
        ff[i] = SVR[i] - SXR[i];
    }
    for(ll i=N;i>0;i--){
        gg[i-1] = max(gg[i], ff[i-1]);
    }
    rep(i,N+1){
        cmax(ans, gg[i] + SVL[i] - SXL[i]*2);
    }
    cout << ans << endl;
}
    /*
    // right -> left
    ll lid = 0;
    ll lmax = 0;
    rep(i,N+1){
        if(lmax < SVL[i] - SXL[i]){
            lmax = SVL[i] - SXL[i];
            lid = i;
        }
    }
    ll rid = N;
    ll rmax = 0;
    for(ll i=N;i>=lid;i--){
        if(rmax < SVR[i] - SXR[i]*2){
            rmax = SVR[i] - SXR[i]*2;
            rid = i;
        }
    }
    ll ans = lmax + rmax;
    // left -> right
    rid = N;
    rmax = 0;
    for(ll i=N;i>=0;i--){
        if(rmax < SVR[i] - SXR[i]){
            rmax = SVR[i] - SXR[i];
            rid = i;
        }
    }
    lid = 0;
    lmax = 0;
    rep(i,rid+1){
        if(lmax < SVL[i] - SXL[i]*2){
            lmax = SVL[i] - SXL[i]*2;
            lid = i;
        }
    }
    cout << lmax+rmax << endl;
    cmax(ans, lmax+rmax);
    cout << ans << endl;
}*/

Measured memory_bytes: 11056
#include <stdio.h>
int main(){
  int x, y, tmp;
  while(1){
    scanf("%d%d", &x, &y);
    if(x == 0 && y == 0){
      break;
    }else if(x > y){
     tmp = x; x = y;y = tmp;
    }
    printf("%d %d\n",x, y);
  }
  return 0;
}



Measured memory_bytes: 1928
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

using namespace std;
int main()
{
    char  sr[100000];
    int a,b,cnt=0;
    cin>>a>>b;
    int i;
    for(i=0;i<a;i++)
    	cin>>sr[i];
    if((a-1)%(b-1)!=0)
    	cnt=1;
	cout<<(a-1)/(b-1)+cnt<<endl;
	return 0;
}

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

using namespace std;
typedef long long ll;
#define MOD 1000000007
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

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

    int L[N];
    for(int i=0; i<N; i++) cin >> L[i];

    sort(L, L+N);

    int cnt = 0;
    for(int i=0; i<N; i++) {
       for(int j=i+1; j<N; j++) {
           for (int k=j+1; k<N; k++) {
               if(L[i] + L[j] <= L[k]) break;
               cnt++;
           }
       }
    }

    cout << cnt << endl;

    return 0;
}

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

namespace Main
{
    class Program
    {
        static void Main(string[] arg)
        {
            int answer = int.Parse(Console.ReadLine());
            int count = 0;
            while(answer > count)
            {
                count += 111;
            }

            Console.WriteLine(count);
            Console.ReadLine();

        }
    }
}


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

int main(){
    __int64_t A;
    __int64_t B;
    __int64_t C, D;

    cin >> A >> B >> C >> D;
    __int64_t E = C*D;
    
    
    __int64_t r;
    __int64_t f = C;
    __int64_t g = D;
    r = g % f;
      while(r!=0){
        g = f;
        f = r;
        r = g % f;
      }
    E /= f;

    __int64_t a_c = (A - 1) / C;
    
    __int64_t a_d = (A - 1) / D;
    __int64_t a_e = (A - 1) / E;
    __int64_t b_c = B  / C;
    __int64_t b_d = B  / D;
    __int64_t b_e = B / E;
    
    __int64_t area = (B - A + 1 );
    __int64_t out_area = (b_c - a_c) + (b_d - a_d) - (b_e - a_e);
    cout << area - out_area << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<numeric>
#include<string>
#include<cmath>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<iomanip>
#include<cctype>
#include<map>
#include<cstring>
#include<bitset>
#include<cassert>

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep2(i,a,b) for (int (i)=a;(i)<(b);(i)++)
#define all(x) (x).begin(),(x).end()

using namespace std;
using ll = long long int;

const int inf = 1001001000;
const long long int Inf = 1001001001001001000;



void print(vector<vector<int>> a){
	for (int i = 0; i < a.size(); i++)
	{
		for (int j=0;j<a[i].size();j++){
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
}

void print(vector<vector<long long int>> a){
	for (int i=0;i<a.size();i++){
		for (int j=0;j<a[i].size();j++){
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
}

void print(vector<int> a){
    int n = a.size();
    for (int j=0;j<n;j++) {
        if (j != n-1) cout << a[j] << " ";
        else cout << a[j] << endl;
    }
}

void print(vector<long long int> a){
    int n = a.size();
    for (int j=0;j<n;j++) {
        if (j != n-1) cout << a[j] << " ";
        else cout << a[j] << endl;
    }
}

void print(set<int> a){
	for (auto x:a)
		cout << x << " ";
	cout << endl;
}

//UnionFind木のテンプレ.parentには根のindexが入っている.
//根には連結成分のサイズが入っている.nはノード数.
class UnionFind{
public:
	vector<int> parent;
	UnionFind(){}
	UnionFind(int n){
		this->parent = vector<int>(n,-1);
	}
	int root(int x){
		if (this->parent[x] < 0) return x;
		this->parent[x] = root(this->parent[x]);
		return this->parent[x];
	}
	int unite(int x, int y){
		int rx = this->root(x);
		int ry = this->root(y);
		if (rx == ry) return false;
		if (this->parent[rx] > this->parent[ry]) swap(rx, ry);
		this->parent[rx] += this->parent[ry];
		this->parent[ry] = rx;
		return true;
	}
	int same(int x, int y){
		int rx = this->root(x);
		int ry = this->root(y);
		return rx == ry;
	}
	int size(int x){
		return -this->parent[this->root(x)];
	}
};

int main()
{
	int n, m;
	cin >> n >> m;
	UnionFind uf(n);
	rep(i, m)
	{
		int x, y, z;
		cin >> x >> y >> z;
		x--;
		y--;
		uf.unite(x, y);
	}
	set<int> ans;
	rep(i,n){
		ans.insert(uf.root(i));
	}
	cout << ans.size() << endl;

	return 0;
}

Measured memory_bytes: 8316
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <complex>
#include <string>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#ifndef LOCAL
#define debug(x) ;
#else
#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;

template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &p) {
  out << "{" << p.first << ", " << p.second << "}";
  return out;
}

template <typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  out << '{';
  for (const T &item : v) out << item << ", ";
  out << "\b\b}";
  return out;
}
#endif

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 200010


int main(){
  ll N;

  cin >> N;


  ll ans = LLINF;

  for (ll i=1; i*i<=N; i++) {
    if (N % i == 0)
      ans = min(ans, i + N / i);
  }

  cout << ans - 2 << endl;

  return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

int n, a[5][105], dp[5][105], ans = 0; 

int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= 2; i++)
		for(int j = 1; j <= n; j++)	scanf("%d", &a[i][j]);
	dp[1][1] = a[1][1];
	dp[2][1] = a[1][1] + a[2][1];
	for(int i = 2; i <= n; i++)	dp[1][i] = dp[1][i - 1] + a[1][i];
	for(int i = 2; i <= n; i++)	dp[2][i] = a[2][i] + max(dp[1][i], dp[2][i - 1]);
	printf("%d\n", dp[2][n]);
}

Measured memory_bytes: 128
// includes {{{
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<tuple>
#include<cmath>
#include<random>
#include<cassert>
// #include<deque>
// #include<multiset>
// #include<bitset>
// #include<cstring>
// #include<bits/stdc++.h>
// }}}
using namespace std;
using ll = long long;

// NOTE : there's get and sum method.
/// --- BIT Library {{{ ///

template < class T = ll >
struct BIT {
  int n, m;
  T identity;
  vector< T > data;
  BIT() : n(0) {}
  BIT(int n, T identity = T()) : n(n), identity(identity), data(n, identity) {
    m = 1;
    while(m < n) m <<= 1;
  }
  void add(int i, T x) {
    i++;
    while(i <= n) {
      data[i - 1] = data[i - 1] + x;
      i += i & -i;
    }
  }
  T sum(int i) {
    if(i < 0) return identity;
    if(i >= n) i = n - 1;
    i++;
    T s = identity;
    while(i > 0) {
      s = s + data[i - 1];
      i -= i & -i;
    }
    return s;
  }
  T get(int i) { return sum(i) - sum(i - 1); }
  T range(int a, int b) { return sum(b) - sum(a - 1); }
  int lower_bound(T w) {
    int i = 0;
    for(int k = m; k > 0; k >>= 1) {
      if(i + k <= n && data[i + k - 1] < w) w -= data[(i += k) - 1];
    }
    return i;
  }
};

/// }}}--- ///

const int N = 1e5 + 10;
ll x[N], y[N];
int n, m;
const ll inf = 1e18;
const int mod = 1e9 + 7;

BIT<> bit(N);

// uniq, compress {{{
#include <algorithm>
#include <map>
#include <vector>
template < class T >
void uniq(vector< T > &v) {
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
}
template < class T >
map< T, int > compress(const vector< T > &v) {
  map< T, int > mp;
  int i = -1;
  for(auto &e : v) mp[e] = ++i;
  return mp;
}
// }}}

int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  cin >> n >> m;
  for(int i = 1; i <= n; i++) cin >> x[i];
  for(int i = 1; i <= m; i++) cin >> y[i];
  y[0] = -inf;
  y[m+1] = inf;
  vector<tuple<ll, ll, int>> v;
  for(int i = 1; i <= n; i++) {
    int p = lower_bound(y, y + m + 2, x[i]) - y;
    if(p == m + 1 || p == 1) continue;
    v.emplace_back(x[i] - y[p-1], -(y[p] - x[i]), i);
  }
  sort(begin(v), end(v));
  ll ans = 0;

  vector<ll> w(v.size());
  for(int i = 0; i < v.size(); i++) w[i] = -get<1>(v[i]);

  uniq(w);
  auto mp = compress(w);

  for(int id = 0; id < v.size(); id++) {
    int i;
    ll s, t;
    tie(s, t, i) = v[id];

    // iが左に入れるやつのなかで最後 (s-order)

    // 次と同じなので自由度がない
    if(id + 1 < n && s == get<0>(v[id + 1]) && t == get<1>(v[id + 1])) continue;

    t = -t;

    // 右への距離が真に短いやつのみ，自由がある
    // +1 は以前のもので "自由なものを全て右に入れる"
    ll val = bit.sum(mp[t]-1) % mod + 1;

    ans += val;
    bit.add(mp[t], val);
  }
  ans++; // すべてを右に入れる
  ans %= mod;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 11760
#include <cstdio>
  #include <iostream>
  #include <string.h>
  #include <cstring>
  #include <cmath>
  #include <math.h>
  #include <algorithm>
  #include <iomanip>
  #include <map>
  #include <set>
  #include <vector>
  #include <sstream>
  #include <queue>  
  #include <bitset>
#define MAX 100005
#define INF 9999999999999
#define pb push_back
using namespace std;
typedef long long int ll;
 typedef pair<ll,ll> ii;
 typedef vector<ii> vii;
 typedef vector <ll > vi;
 
vector <vii> adj(MAX); 
ll arr[100005];
int main()
{
//  freopen("input.txt","r",stdin);
  //freopen("output.txt","w",stdout);
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ll sum=0,c=0,n;
  cin>>n;
  for(ll i=0;i<n;i++)
    cin>>arr[i];
  sort(arr,arr+n);
  //reverse(arr,arr+n);
  for(ll i=0;i<n;i++)
    sum+=arr[i];
  //cout<<sum<<endl;
  int f=0;
 if(sum%10==0){
  for(ll i=0;i<n;i++)
  {
    if(arr[i]%10!=0)
    {
      sum-=arr[i];
      f=1;
      break;
    }
  }
  if(f==1)
   cout<<sum<<endl;
 else
  cout<<0<<endl;
}
else
cout<<sum<<endl;
   return 0;
  
  
}  

Measured memory_bytes: 2560
#include <bits/stdc++.h>
#define ll long long
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end))) // rep(i, 1, 5) --> {1,2,3,4} // rep(i, 5, 1) --> {4,3,2,1} // rep(it, end(v), begin(v)) --> *it

using namespace std;

int main()
{
    int a, b;
    cin >> a >> b;
    if (a == 1 && b != 1)
        cout << "Alice";
    else if (a != 1 && b == 1)
        cout << "Bob";
    else if (a == b)
        cout << "Draw";
    else if (a > b)
        cout << "Alice";
    else 
        cout << "Bob";
    return 0;
}

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

int main() {
	int a[13] = {0,1,3,1,2,1,2,1,1,2,1,2,1};
	int x,y;
	cin>>x>>y;
	if(a[x]==a[y]) cout<<"Yes\n";
	else cout<<"No\n";
	return 0;
}

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

int main() {
  ll N, ans = 0;
  cin >> N;
  std::vector<ll> v(N);
  for (ll i = 0; i < N; ++i) cin >> v[i];
  std::sort(v.begin(),v.end());
  for (ll j = 0; j < N-2; ++j) {
    ll a = v[j];
    for (ll k = j+2; k < N; ++k) {
      ll b = v[k];
      ll n=0;
      for (ll l = k-1; l > j; --l) {
        ll c = v[l];
        if (std::abs(a-b) < c && c < a+b) n++;
        else break;
      }
      ans+=n;
    }
  }
  cout << ans << endl;
  return 0 ;
}

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

using namespace std;

#define INF 1001001001  //int32_t
#define MOD 1000000007
#define MOD2 998244353

#define all(a)  (a).begin(),(a).end()

#define mkp make_pair
#define pb push_back

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

int main(){

    bool flag=false;
    ll ans=0,sum=0;

    int r,g;
    cin >>r>>g;

    //cout <<fixed<<setprecision(16)<< << endl;
    cout << 2*g - r << endl;

    //if(flag)cout << "Yes" <<endl;
    //else cout << "No" <<endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>   
#define rep(i, n) for(long long int i = 0; i < n; i++)
#define _rep(i, m, n) for(long long int i = m; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const ll mod = 1000000007;
//const int dx[4] = {1, 0, -1, 0};
//const int dy[4] = {0, 1, 0, -1};
     
ll gcd(ll A, ll B){
    if(B == 0)return A;
    return gcd(B, A % B);
}
ll lcm(ll A, ll B){
    return A * B / gcd(A, B);
}
template <typename T>
T pow(T a, ll n, T e = 1) {
    T ret = e;
    while (n) {
        if (n & 1) ret *= a;
        a *= a;
        n >>= 1;
    }
    return ret;
}
 
template <int mod>
struct ModInt {
    int x;
    ModInt() : x(0) {}
    ModInt(long long x_) {
        if ((x = x_ % mod + mod) >= mod) x -= mod;
    }
    ModInt& operator+=(ModInt rhs) {
        if ((x += rhs.x) >= mod) x -= mod;
        return *this;
    }
    ModInt& operator-=(ModInt rhs) {
        if ((x -= rhs.x) < 0) x += mod;
        return *this;
    }
    ModInt& operator*=(ModInt rhs) {
        x = (unsigned long long)x * rhs.x % mod;
        return *this;
    }
    ModInt& operator/=(ModInt rhs) {
        x = (unsigned long long)x * rhs.inv().x % mod;
        return *this;
    }
 
    ModInt operator-() const { return -x < 0 ? mod - x : -x; }
    ModInt operator+(ModInt rhs) const { return ModInt(*this) += rhs; }
    ModInt operator-(ModInt rhs) const { return ModInt(*this) -= rhs; }
    ModInt operator*(ModInt rhs) const { return ModInt(*this) *= rhs; }
    ModInt operator/(ModInt rhs) const { return ModInt(*this) /= rhs; }
    bool operator==(ModInt rhs) const { return x == rhs.x; }
    bool operator!=(ModInt rhs) const { return x != rhs.x; }
    ModInt inv() const { return pow(*this, mod - 2); }
 
    friend ostream& operator<<(ostream& s, ModInt<mod> a) {
        s << a.x;
        return s;
    }
    friend istream& operator>>(istream& s, ModInt<mod>& a) {
        s >> a.x;
        return s;
    }
};
 
using mint = ModInt<1000000007>;
using Graph = vector<vector<int>>;
Graph G;
/*------------------------------------------------------------------*/

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

    int n; cin >> n;
    vector<int> p(n), q(n);
    rep(i, n) cin >> p[i];
    rep(i, n) cin >> q[i];
    vector<int> per(n);
    rep(i, n) per[i] = i + 1;
    int a, b;
    int num = 0;
    do{
        num++;
        bool pf = true, qf = true;
        rep(i, n) if(p[i] != per[i]) pf = false;
        rep(i, n) if(q[i] != per[i]) qf = false;
        if(pf) a = num;
        if(qf) b = num;

    }while(next_permutation(per.begin(), per.end()));
    cout << abs(a - b) << endl;
}

Measured memory_bytes: 3524
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N; cin >>N;
  vector<int>M(N);
  vector<int>saishou(N);
  cin>>M.at(0);
  saishou.at(0)=M.at(0);
  for(int i=1;i<N;i++){
    cin>>M.at(i);
    saishou.at(i)=min(M.at(i),saishou.at(i-1));
  }
  int count=0;
  for(int i=0;i<N;i++){
    if(M.at(i)<=saishou.at(i))count++;
  }
  cout <<count<<endl;
}

Measured memory_bytes: 1792
N,Y = map(int,input().split())
c = 0
array = []
for i in range(N+1):
  for j in range(N+1-i):
    if 10000*i+5000*j+1000*(N-i-j) == Y:
      c = 1
      array.append(i)
      array.append(j)
      array.append(N-i-j)

      
if c == 1:
  print(array[0],array[1],array[2])
else:
  print(-1,-1,-1)

Measured memory_bytes: 3064