akhauriyash/Code-Regression huggingface dataset:
nodes = [[] for i in range(4)]

a = [int(i) for i in input().split()]
nodes[a[0]-1].append(a[1]-1)
nodes[a[1]-1].append(a[0]-1)

b = [int(i) for i in input().split()]
nodes[b[0]-1].append(b[1]-1)
nodes[b[1]-1].append(b[0]-1)

c = [int(i) for i in input().split()]
nodes[c[0]-1].append(c[1]-1)
nodes[c[1]-1].append(c[0]-1)

ok = 0

ct = [0]*5

for i in range(1,5):
    ct[i] = a.count(i) + b.count(i) + c.count(i)

ct.sort(reverse=True)

ct = ct[:-1]

if ct[0]==2 and ct[1]==2 and ct[2]==1 and ct[3]==1:
    ok = 1

if ok:
    print('YES')
else:
    print('NO')


Measured memory_bytes: 3064
#include<cstdio>
#include<algorithm>
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std;
const int maxn=200000+10;
int h[maxn],go[maxn*4],nxt[maxn*4],co[maxn*4],e[maxn][2];
int dfn[maxn],low[maxn],dep[maxn],d[maxn],dl[maxn],fa[maxn];
bool bz[maxn],pd[maxn];
int i,j,k,l,t,n,m,x,y,tot,top,ans,head,tail;
void add(int x,int y,int z){
	go[++tot]=y;
	co[tot]=z;
	nxt[tot]=h[x];
	h[x]=tot;
}
void dfs(int x,int y){
	fa[x]=y;
	dfn[x]=++top;
	int t=h[x];
	while (t){
		if (co[t]&&go[t]!=y){
			dep[go[t]]=dep[x]+1;
			dfs(go[t],x);
		}
		t=nxt[t];
	}
	low[x]=++top;
}
bool check(int x,int y){
	if (dfn[x]>dfn[y]) swap(x,y);
	if (dfn[x]<=dfn[y]&&low[x]>=low[y]) return dep[y]-dep[x]>2;
	if (fa[x]==fa[y]) return 0;else return 1;
}
void bfs(){
	int now,t;
	pd[x]=1;
	dl[tail=1]=x;
	while (head<tail){
		now=dl[++head];
		t=h[now];
		while (t){
			if (!co[t]&&!pd[go[t]]){
				d[go[t]]=d[now]+1;
				if (d[go[t]]<dep[go[t]]){
					pd[go[t]]=1;
					dl[++tail]=go[t];
				}
			}
			t=nxt[t];
		}
	}
}
int main(){
	scanf("%d%d%d",&n,&x,&y);
	fo(i,1,n-1){
		scanf("%d%d",&j,&k);
		//add(j,k,0);add(k,j,0);
		e[i][0]=j;e[i][1]=k;
	}
	fo(i,1,n-1){
		scanf("%d%d",&j,&k);
		add(j,k,1);add(k,j,1);
	}
	dfs(y,0);
	fo(i,1,n-1){
		j=e[i][0];k=e[i][1];
		if (check(j,k)) bz[j]=bz[k]=1;
		else{
			add(j,k,0);
			add(k,j,0);
		}
	}
	bfs();
	fo(i,1,n){
		if (pd[i]&&bz[i]){
			printf("-1\n");
			return 0;
		}
		else if (pd[i]) ans=max(ans,dep[i]*2);
	}
	printf("%d\n",ans);
}

Measured memory_bytes: 24960
import java.math.BigInteger;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.TreeMap;
import java.util.*;
import java.util.Map.Entry;

public class Main{
	static int mod = (int) 1e9 + 7;

	public static void main(String[] args) {
		Scanner scn = new Scanner(System.in);
		String s = scn.next();
		int d = scn.nextInt();
		int a[] = new int[s.length()];
		for (int i = 0; i < s.length(); i++) {
			a[i] = s.charAt(i) - '0';
		}
		long dp[][][] = new long[a.length][d][2];
		for (long v[][] : dp) {
			for (long c[] : v) {
				Arrays.fill(c, -1);
			}
		}
		long ans = (solve(0, 0, 1, a, dp, d) - 1+mod)%mod;
		System.out.println(ans);

	}

	private static long solve(int pos, int rem, int flag, int[] a, long[][][] dp, int d) {
		if (pos == a.length) {
			return rem == 0 ? 1 : 0;
		}
		if (dp[pos][rem][flag] != -1) {
			return dp[pos][rem][flag];
		}
		long res = 0;
		int limit = (flag == 1) ? a[pos] : 9;
		for (int i = 0; i <= limit; i++) {
			if (i == limit && flag==1) {
				res = (res + solve(pos + 1, (rem + i) % d, 1, a, dp, d)) % mod;
			} else {
				res = (res + solve(pos + 1, (rem + i) % d, 0, a, dp, d)) % mod;
			}

		}
		dp[pos][rem][flag] = res%mod;
		return res;
	}

}

Measured memory_bytes: 90040
# coding: utf-8
# Your code here!

N = int(input())
h = list(map(int,input().split()))

costs = [0]*N

costs[1] = abs(h[1]-h[0])

for i in range(2,N):
    costs[i] = min(costs[i-2]+abs(h[i]-h[i-2]),costs[i-1]+abs(h[i]-h[i-1]))
    
print(costs[N-1])

Measured memory_bytes: 13980
N,K=map(int,input().split())
h=list(map(int,input().split()))
dp=[0]*N
dp[0]=0
for n in range(1,N):
    dp[n]=dp[n-1]+abs(h[n-1]-h[n])
    if N-K>=0 and n-K>=0:
        for i in range(n-K,n):
            if dp[n]>=dp[i]+abs(h[i]-h[n]):
                dp[n]=dp[i]+abs(h[i]-h[n])
    elif N-K>=0 and n-K<0:
        for i in range(0,n):
            if dp[n]>=dp[i]+abs(h[i]-h[n]):
                dp[n]=dp[i]+abs(h[i]-h[n])
    else:
        for i in range(0,n):
            if dp[n]>=dp[i]+abs(h[i]-h[n]):
                dp[n]=dp[i]+abs(h[i]-h[n])
print(dp[N-1])

Measured memory_bytes: 52832
#include<iostream>
#include<algorithm>
#include<functional>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<tuple>
#include<stack>
#include<queue>
#include<deque>
#include<sstream>
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<bitset>
#include<time.h>
#include<cstdlib>
#include<cassert>
#define ll long long
#define fi first
#define se second
using namespace std;

int n,k;
ll a[100001],b[100001];

inline ll solve(ll now){
  ll res=0;
  for(int i=0;i<n;i++){
    if((a[i]|now)<=now){
      res+=b[i];
    }
  }
  return res;
}
                   
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.precision(10);
  cout<<fixed;
#ifdef LOCAL_DEFINE
    freopen("in", "r", stdin); 
    freopen("out","w",stdout);
#endif
  cin>>n>>k;
  for(int i=0;i<n;i++){
    cin>>a[i]>>b[i];
  }
  int temp=k;
  int now=1;
  int i=0;
  ll ans=solve(temp);
  while(now<=temp){
    if(temp&now){
      for(int j=0;j<=i;j++){
        if(j==i){
          temp=temp&~(1<<j);
        }else{
          temp=temp|(1<<j);
        }
      }
      //cout<<temp<<endl;
      ans=max(ans,solve(temp));
    }
    temp=k;
    now<<=1;
    i++;
  }
  cout<<ans<<"\n";
  /*
  for(int i=0;i<n;i++){
    int a,b;cin>>a>>b;
    v.push_back(make_pair(a,b));
  }
  sort(v.begin(),v.end());
  reverse(v.begin(),v.end());
  ll now=0;
  ll ans=0;
  for(int i=0;i<n;i++){
    if((now|v[i].fi)<=k){
      ans+=v[i].se;
      now|=v[i].fi;
    }
  }
  cout<<ans<<endl;*/
#ifdef LOCAL_DEFINE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
  return 0;
}

Measured memory_bytes: 1920
import java.io.*;
import java.util.Arrays;
class Main{
	public static void main(String[] args) throws IOException {
		int i,j;
		int[] n = new int[990];
		String[] str = new String[990];
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		for(;;){
			str = in.readLine().split(" ");
			for(i=0;i<2;i++){
				n[i] = Integer.parseInt(str[i]);
			}
			if(n[0]+n[1]==0) break;
			for(i=0;i<n[0];i++){
				for(j=0;j<n[1];j++){
					if(i%2==0 && j%2==0 || i%2!=0 && j%2!=0)
						System.out.print("#");
					else
						System.out.print(".");
				}
				System.out.println();
			}
			System.out.println();
		}
	}
}

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

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

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

using ll=long long;
using R=long double;
const R EPS=1e-9; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r){return(r > EPS)-(r < -EPS);}
inline R sq(R x){return sqrt(max<R>(x,0.0));}

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

// Problem Specific Parameter:

struct Segment_tree{
	using T=ll;

	int n;
	vector<T> data;
	const T out=0LL;

	inline T vmerge(T l,T r){return l+r;}

	Segment_tree(int n):n(n){data.assign(2*n,out);}

	void update(int p,T x) {  // set value at position p
		for(data[p+=n]+=x; p > 1; p >>= 1){
			data[p>>1]=vmerge(data[p],data[p^1]);
		}
	}

	T query(int l, int r) {  // sum on interval [l, r)
		T resl = out,resr = out;
			for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
				if (l&1) resl = vmerge(data[l++], resl);
				if (r&1) resr = vmerge(resr, data[--r]);
		}
		return vmerge(resl,resr);
	}
};

int main(void){
	int n,q;
	cin >> n >> q;

	Segment_tree rsq(n);

	rep(loop,q){
		int com,x,y;
		cin >> com >> x >> y;
		if(com)
			cout << rsq.query(x,y+1) << endl;
		else
			rsq.update(x,y);
	}
	return 0;
}

Measured memory_bytes: 4340
#include <algorithm>
#include <iostream>
using  namespace  std;
int n;
int main()
{
    int n;
    cin>>n;
    if(n%1000==0)
    {
        puts("0");
    } else{
        int money =((n/1000)+1)*1000-n;
        cout<<money<<endl;
    }
    return 0 ;
}

Measured memory_bytes: 3632
(* Is it a Right Triangle? *)
let () =
  let check a b c = if a >= b && a >= c then a * a = b * b + c * c
    else if b >= a && b >= c then b * b = a * a + c * c
    else c * c = a * a + b * b in
  Scanf.scanf "%d\n" @@ fun n ->
  let arr = Array.init n @@ fun _ -> Scanf.scanf "%d %d %d\n" @@ 
    fun a b c -> check a b c in
  Array.iter (fun b -> if b then print_endline "YES" else print_endline "NO") arr


Measured memory_bytes: 2728
package main

import (
	"fmt"
)

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

func main() {
	var a, b, k int
	fmt.Scan(&a, &b, &k)

	m := min(a, b)
	for i := m; i > 0; i-- {
		if a%i == 0 && b%i == 0 {
			k--
		}
		if k == 0 {
			fmt.Println(i)
			return
		}
	}
}


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

int main()
{
  string s;
  cin >> s;
  int a, z;
  size_t n = s.size();
  for (int i = 0; i < n; i++) {
    if (s[i] == 'A') {
      a = i;
      break;
    }
  }
  reverse(s.begin(), s.end());
  for (int i = 0; i < n; i++) {
    if (s[i] == 'Z') {
      z = i;
      break;
    }
  }
  cout << n -a -z << endl;
  return 0;
}


Measured memory_bytes: 640
using System.Linq;
using System;
class Program
{
    static void Main()
    {
        var N = int.Parse(Console.ReadLine());
        var astr = Console.ReadLine().Split(' ');
        var a = new int[astr.Length];
        for (int i = 0; i < astr.Length; i++)
        {
            a[i] = int.Parse(astr[i]);
        }

        var ans = a.Max() - a.Min();

        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 13268
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(nullptr); cout.tie(0)
#define endl "\n"
#define int long long
typedef vector<int> vi;
#define all(x) x.begin(),x.end()
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
#define pii              pair <int,int>
#define DEBUG(x) cerr << '>' << #x << ':' << x << endl;
typedef long long ll;
//#pragma comment(linker, "/STACK:667772160")
#define in_range(x, y, r, c) ((x >= 0 && x < r && y >= 0 && y < c))

const double eps=1e-9;
const int MOD=1e9+7;
const int N=1e5+30;
const int inf = 1e17+995;

template< class T > T gcd(T a, T b) { return (b != 0 ? gcd<T>(b, a%b) : a); }
template< class T > T lcm(T a, T b) { return (a / gcd<T>(a, b) * b); }
template <typename T> T exp(T b, T p){T x = 1;while(p){if(p&1)x=(x*b);b=(b*b);p=p>>1;}return x;}
inline int ones(int n) { int res = 0; while(n && ++res) n-=n&(-n); return res; }
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
void boostIO() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
int n,mem[N],k,h[N];
int dp(int idx){
    if(idx==n-1)
        return 0;

    int &ret=mem[idx];
    if(ret!=-1)
        return ret;
    ret=inf;
    for (int i = idx+1; i<=idx+k and i<=n-1; ++i) {
        //work as take or leave the current element
        ret=min(ret,abs(h[idx]-h[i])+dp(i));
    }
    return ret;
}
int32_t main() {
boostIO();
cin>>n>>k;
    for (int i = 0; i < n; ++i) {
        cin>>h[i];
    }
    memset(mem,-1, sizeof(mem));
    int ans=dp(0);
    cout<<ans<<endl;
}

Measured memory_bytes: 4992
def tostr(N):
    if N == 0:
        return "a"
    if N == 1:
        return "b"
    if N == 2:
        return "c"
    if N == 3:
        return "d"
    if N == 4:
        return "e"
    if N == 5:
        return "f"
    if N == 6:
        return "g"
    if N == 7:
        return "h"
    if N == 8:
        return "i"
    if N == 9:
        return "j"
    if N == 10:
        return "k"
    if N == 11:
        return "l"
    if N == 12:
        return "m"
    if N == 13:
        return "n"
    if N == 14:
        return "o"
    if N == 15:
        return "p"
    if N == 16:
        return "q"
    if N == 17:
        return "r"
    if N == 18:
        return "s"
    if N == 19:
        return "t"
    if N == 20:
        return "u"
    if N == 21:
        return "v"
    if N == 22:
        return "w"
    if N == 23:
        return "x"
    if N == 24:
        return "y"
    if N == 25:
        return "z"
    if N == 0:
        return "z"


def main(N):
    N -= 1
    ans = ""
    loop = 0
    while True:
        if N < 0:
            break
        if N <= 25:
            ans = tostr(N)+ans
            break
        ans = tostr(N % 26)+ans
        N = N//26
        N -= 1
    return ans


N = int(input())
print(main(N))


Measured memory_bytes: 9272
#include <stdio.h>

int main()
{
    int n,i=1,x;
    scanf("%d",&n);
    while(i<=n){
        if(i%3==0){
            printf(" %d",i);
        }
        else{
            if(i%10==3){
                printf(" %d",i);
            }
            else{
                x=i;
                while(x){
                    if(x%10!=3){
                    x/=10;
                    }
                    else{
                        printf(" %d",i);
                        break;
                    }
                }
            }
        }
        i++;
    }
    printf("\n");
    return 0;
}



Measured memory_bytes: 2104
from operator import itemgetter

N,M = map(int,input().split())
AB = sorted([list(map(int,input().split())) for _ in range(M)],key=itemgetter(1))
x, ans = AB[0][1],1
for a,b in AB:
  if a>=x:
    x = b
    ans += 1
print(ans)

Measured memory_bytes: 29920
#include <bits/stdc++.h>
#define MAX (ll)(1e3 + 7)
#define INF (ll)(1e18)
#define MOD (ll)(1e9 + 7)

using namespace std;
using ll = long long;
using cd = complex<double>;

int main () {
	int h, w, k;
	cin >> h >> w >> k;
	int cc = 0;
	char mat[h][w];
	for (int i = 0; i < h; i++) {
		for (int j =0; j < w; j++) {
			cin >> mat[i][j];
		}
	}
	for (int i = 0; i < (1 << h); i++) {
		for (int j = 0; j < (1 << w); j++) {
			int c = 0;
			for (int x = 0; x < h; x++) {
				for (int y = 0; y < w; y++) {
					if (((i >> x) & 1) || ((j >> y) & 1)) {
						continue;
					}
					c += mat[x][y] == '#';
				}
			}
			cc += c == k;
		}
	}
	cout << cc << "\n";
}
					


Measured memory_bytes: 3668
import sys
import math
import collections
from collections import deque
from functools import reduce
import heapq
#n = int(input())
a, b, c, x, y = map(int, sys.stdin.readline().split())
#s = input()
#a = list(map(int, sys.stdin.readline().split()))

n = max(x, y)
ans = 10 ** 10
for i in range(n+1):
    p = max(x - i, 0)
    q = max(y - i, 0)
    r = 2 * i * c + p * a + q * b
    if r < ans:
        ans = r

print(ans)
    

        


Measured memory_bytes: 3692
def main():
    A = int(input())
    B = int(input())
    C = int(input())
    target = int(input())
    answer = 0
    for i in range(A + 1):
        for j in range(B + 1):
            for k in range(C + 1):
                if 500 * i + 100 * j + 50 * k == target:
                    answer += 1
    print(answer)


if __name__ == '__main__':
    main()

Measured memory_bytes: 3060
#include<iostream>
#include<vector>
#include<algorithm>
#include<stdlib.h>
#include<utility>
#include<functional>
#include<cfenv>
#include<cmath>
#include<string>
#include<queue>
#include<map>
#include<set>

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define vint vector<ll>
#define vvint vector<vint>
#define P pair<int,int>
#define INT_MAX 2147483647
using namespace std;
typedef long long ll;


int main(void) {
	map<string, int> mp;
	string s, t; cin >> s >> t;
	int a, b; cin >> a >> b;
	mp[s] = a;
	mp[t] = b;
	string u; cin >> u;
	--mp[u];
	cout << mp[s] << ' ' << mp[t] << endl;
	return 0;
	
}

Measured memory_bytes: 256
#include <iostream>
#include <iterator>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
using namespace std;

int main(){
    long ans=0;
    //bool ans=false;
    long H;
    
    cin>>H;

    int count=0;

    while(H>0){
        
        ans+=pow(2,count);
        H=H/2;
        count++;
        
    }

    cout<<ans<<endl;

   /* if(ans){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }
*/
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

#define mod 1000000007 
#define check exit(0)
#define ordered_set tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>
#define ll long long int
#define trace(x) cerr<<#x<<" : "<<x<<endl;
#define jaldi ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace __gnu_pbds;
using namespace std;

int main()
{
    jaldi
    int n;
    cin>>n;
    map<ll,ll> mp;
    vector<ll> v(n);
    for(ll &x:v) cin>>x,mp[x]++;
    ll ans=0;
    for(auto it=mp.begin();it!=mp.end();it++)
    {
        ans+=((it->second)*(it->second-1))/2;
    }
    for(int i=0;i<n;i++)
    {
        ll tmpans=ans-(mp[v[i]]*(mp[v[i]]-1))/2;
        mp[v[i]]--;
        tmpans+=(mp[v[i]]*(mp[v[i]]-1))/2;
        cout<<tmpans<<endl;
        mp[v[i]]++;
    }
    return 0;
}


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

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];

    long long res = 0;
    for (int i = 0; i < N - 1; i++) {
        if (A[i] % 2 == 1) {
            if (A[i] > 0 && A[i + 1] > 0) {
                A[i]--;
                A[i + 1]--;
                res++;
            }
        }
    }

    for (int i = 0; i < N; i++) {
        res += A[i] / 2;
    }

    cout << res << endl;
    return 0;
}

Measured memory_bytes: 640
#include <stdio.h>
#include <string.h>
 
int main(void){
  char s[1001], order[8], ch[1001];
  int i, j, n, a, b;
 
  scanf("%s\n%d", s, &n);
 
  for(i=0;i<n;i++){
    scanf("%s %d %d", order, &a, &b);
     
    if(!strcmp(order, "reverse")){
      for(j=a;j<=b;j++)
        ch[b-j] = s[j];
      for(j=a;j<=b;j++)
        s[j] = ch[j-a];
    }
 
    if(!strcmp(order, "replace")){
      scanf("%s", ch);
      for(j=0;ch[j]!='\0';j++)
        s[a+j] = ch[j];
    }
 
    if(!strcmp(order, "print")){
      for(j=a;j<=b;j++)
        printf("%c", s[j]);
      printf("\n");
    }
  }
 
  return 0;
}
 
 
 
  



Measured memory_bytes: 2112
using System;
using System.Collections.Generic;
using System.Collections;
using System.Collections.Specialized;
using System.Linq;
using System.Text;
using System.IO;
using System.Reflection;
using static System.Math;
using System.Numerics;
static class Program{
	const int mod=(int)1e9+7;
	const double eps=1e-11;
	static void Main(){
		Sc sc=new Sc();
		var n=sc.I;
		var t=sc.S;
		var a="";
		if(t.Length>n){
			t=t.Substring(0,n)+"...";
		}
		Console.WriteLine("{0}",t);
	}
}
public class Sc{
	public int I{get{return int.Parse(Console.ReadLine());}}
	public long L{get{return long.Parse(Console.ReadLine());}}
	public double D{get{return double.Parse(Console.ReadLine());}}
	public string S{get{return Console.ReadLine();}}
	public int[] Ia{get{return Array.ConvertAll(Console.ReadLine().Split(),int.Parse);}}
	public long[] La{get{return Array.ConvertAll(Console.ReadLine().Split(),long.Parse);}}
	public double[] Da{get{return Array.ConvertAll(Console.ReadLine().Split(),double.Parse);}}
	public string[] Sa{get{return Console.ReadLine().Split();}}
	public object[] Oa{get{return Console.ReadLine().Split();}}
	public int[] Ia2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),int.Parse);}}
	public int[] Ia3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),int.Parse);}
	public int[] Ia3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),int.Parse);}
	public long[] La2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),long.Parse);}}
	public long[] La3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),long.Parse);}
	public long[] La3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),long.Parse);}
	public double[] Da2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),double.Parse);}}
	public double[] Da3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),double.Parse);}
	public double[] Da3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),double.Parse);}
	public T[] Arr<T>(int n,Func<T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f();}return a;}
	public T[] Arr<T>(int n,Func<int,T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(i);}return a;}
	public T[] Arr<T>(int n,Func<string[],T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(Console.ReadLine().Split());}return a;}
	public T[] Arr<T>(int n,Func<int,string[],T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(i,Console.ReadLine().Split());}return a;}
}

Measured memory_bytes: 27508
package main

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

func main() {
	var n, m int
	fmt.Scan(&n, &m)
	xs := make([]int, n+1)
	for i := range xs {
		xs[i] = 1
	}
	sc := bufio.NewScanner(os.Stdin)
	var a int
	for i := 0; i < m; i++ {
		sc.Scan()
		a, _ = strconv.Atoi(sc.Text())
		xs[a] = 0
	}

	f2 := 1
	f1 := xs[1]
	f0 := xs[0]
	for i := 2; i <= n; i++ {
		f2 = (f1*xs[i-1] + f0*xs[i-2]) % 1000000007
		f1, f0 = f2, f1
	}
	fmt.Println(f2)
}


Measured memory_bytes: 1920
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author cherrypi59
 */

#pragma GCC optimize ("O2")
#pragma GCC optimize ("tree-vectorize")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define FFOR(i, a, b) FOR(i, a, b+1)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) FOR(i, 1, n+1)
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define LEN(x) (int)(x).size()
#define DUMP(x) cerr<<__LINE__<<' '<<#x<<"="<<(x)<<endl;
#define pb push_back
#define eb emplace_back
#define mp make_pair

using namespace std;
using lint = long long;
using pii =  pair<int, int>;
using pll =  pair<lint, lint>;
template <typename T> using vc = vector<T>;
template <typename T> using vvc = vector<vector<T>>;
template <typename T> inline bool chmax(T &a, T b){if(a<b){a = b; return true;} return false;}
template <typename T> inline bool chmin(T &a, T b){if(a>b){a = b; return true;} return false;}

constexpr lint ten(int n) {return n==0 ? 1 : ten(n-1)*10;}

template <typename T>
class Basis{
public:
    int sz = 0, dim;
    vector<T> basis;

    // high to low
    void insert(T mask){
        for(int i=dim-1;0<=i;--i){
            if((mask & T(1) << i) == 0) continue;
            if(not basis[i]){
                basis[i] = mask;
                ++sz;
                return;
            }
            mask ^= basis[i];
        }
    }

    //kth highest element
    T kThHighest(T k){
        T res = 0, cnt = T(1) << sz;
        for(int i=dim-1;i<=0;--i){
            if(not basis[i]) continue;
            cnt >>= 1;
            if((k <= cnt and (res & T(1) << i) == 0) or (k > cnt and (res & T(1) << i) > 0)){
                res ^= basis[i];
            }
            if(k > cnt) k -= cnt;
        }
        return res;
    }

    //kth lowest element
    T kThLowest(T k){
        return kThHighest((T(1)<<sz)-k);
    }

    explicit Basis(int _dim=60) : dim(_dim){
        basis.assign(dim, 0);
    }
};

class AXorBattle {
public:
    void solve(std::istream& in, std::ostream& out){
        ios_base::sync_with_stdio(false);
        in.tie(nullptr), out.tie(nullptr);
        int tt;
        in>>tt;
        while(tt--){
            int N;
            in>>N;
            vc<lint> A(N), odd;
            for(auto& a : A) in>>a;
            string S;
            in>>S;
            Basis<lint> B;
            bool ok = true;
            for(int i=N-1;0<=i;--i){
                if(S[i]=='0') B.insert(A[i]);
                else{
                    int tmp = B.sz;
                    B.insert(A[i]);
                    if(tmp<B.sz){
                        ok = false;
                        break;
                    }
                }
            }
            if(ok) out<<"0\n";
            else out<<"1\n";
        }
    }
};


int main() {
	AXorBattle solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


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

int main() {
  int n;
  cin >> n;
  vector<int> a(n), b(n);
  deque<int> c;
  rep(i,n) cin >> a[i];
  rep(i,n) cin >> b[i];
  int ans=0;
  ll res=0;
  rep(i,n) {
    int x=a[i]-b[i];
    if(x<0) {
      ans++;
      res+=-x;
    }
    else if(x>0) c.push_back(x);
  }
  sort(c.begin(),c.end());
  while(res>0) {
    if(c.size()==0) {
      cout << -1 << endl;
      return 0;
    }
    res -= c.back();
    c.pop_back();
    ans++;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1280
#include<iostream>
#include<algorithm>
#include<vector>
#include<math.h>
#include<queue>

#define MOD 1000000007
#define rep(i, n) for(ll i=0; i < (n); i++)

using namespace std;
typedef long long int ll;
typedef vector<ll> llvec;
typedef vector<double> dvec;
typedef pair<int, int> P;
typedef priority_queue<ll, vector<ll>, greater<ll> > gpq_int;
typedef priority_queue<ll, vector<ll>, less<ll> > lpq_int;

ll mod(ll a, ll mod){
  ll res = a%mod;
  if(res<0)res=res + mod;
  return res;
}

ll modpow(ll a, ll n, ll mod){
  ll res=1;
  while(n>0){
    if(n&1) res=res*a%mod;
    a=a*a%mod;
    n>>=1;
  }
  return res;
}

ll modinv(ll a, ll mod){
  return modpow(a, mod-2, mod);
}

bool is_prime(ll n){
  ll i = 2;
  if(n==1)return false;
  if(n==2)return true;
  bool res = true;
  while(i*i <n){
    if(n%i==0){
      res = false;
    }
    i = i+1;
  }

  //if(i==1)res = false;
  if(n%i==0)res=false;
  return res;
}



void fact(ll a, ll fact[]){
  ll i=2;
  ll original = a;
  fact[1]=1;
  rep(i, 1000000-1){
    int ii = i+2;
    while(a%ii==0){
      fact[ii] +=1;
      a = a/ii;
    }
  }
  if(a>1){
    fact[0]=a;
  }
  
  return;
}

ll N, M;
ll A[100010];

int main(){
  cin >> N >> M;
  lpq_int que;
  rep(i, N){
    cin >> A[i];
    que.push(A[i]);
  }
  rep(i, M){
    ll tmp = que.top();
    que.pop();
    que.push(floor(tmp/2));
    //cout << floor(tmp/2) << endl;
  }
  ll ans=0;
  rep(i, N){
    //cout << que.top() << endl;
    ans += que.top();
    que.pop();
  }
  cout << ans;
  return 0;
}


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

const int mod = 1e4 + 7;

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	int N;
	string S;
	cin >> N >> S;
	vector<int> v(N);
	for (int i = 0; i < N; i++) {
		v[i] = S[i] == 'J' ? 0 : S[i] == 'O' ? 1 : 2;
	}
	vector<vector<int>> dp(N + 1, vector<int>(8));
	dp[0][1] = 1;
	for (int i = 0; i < N; i++) {
		for (int j = 1; j < 8; j++) {
			for (int k = 1; k < 8; k++) if ((k & (1 << v[i])) != 0 && (j & k) != 0) {
				dp[i + 1][k] = (dp[i + 1][k] + dp[i][j]) % mod;
			}
		}
	}
	int res = 0;
	for (int i = 0; i < 8; i++) {
		res = (res + dp[N][i]) % mod;
	}
	cout << res << endl;
	return 0;
}



Measured memory_bytes: 3280
#include<bits/stdc++.h>
#define YOU setprecision
using namespace std;
int i[11111111];
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int a,b,c,d=0,e,f;
  string s;
  cin >>a;
  if(a<1200) cout <<"ABC\n";
  else{
    if(a<2800) cout <<"ARC\n";
    else cout <<"AGC\n";
  }
  return (0);
}


Measured memory_bytes: 256
#!/usr/bin/env python3


s = input()
t = input()

result = len(t)

for i in range(len(s) - len(t) + 1):
    dif = 0
    for j in range(len(t)):
        if(s[i + j] != t[j]):
            dif += 1


    if result > dif:
        result = dif

print(result)



Measured memory_bytes: 8912
#include <bits/stdc++.h>
using namespace std;
//cin.ignore();	// better to use 2 times getline(cin,s);
// g++ iterator.cpp -std=c++17
//cout << (A + B == C ? "YES" : "NO") << endl;
#define pb push_back
#define mk make_pair
#define vll vector<ll>
#define mll map<ll,ll >
#define mlli map<ll,ll>::iterator
#define size size()
#define endl "\n"
#define ll long long int
#define ld long double
void fast(){
   	ios_base::sync_with_stdio(false);
   	cin.tie(NULL);
   	cout.tie(NULL);}


int main(void)
{
  fast();
  int n;
  cin>>n;
  int mini = INT_MAX;
  int maxi = INT_MIN;
  int a[n];
  for(int i=0;i<n;i++)
  {
    cin>>a[i];
    mini = min(mini,a[i]);
    maxi = max(maxi,a[i]);
  }
  int ans=INT_MAX;
  for(int i=mini;i<=maxi;i++)
  {
      int x = 0;                        // imp logic..
    for(int j=0;j<n;j++)
    {
        x = x+((a[j]-i)*(a[j]-i));
    }
    ans = min(ans,x);
  }
  cout<<ans<<endl;
}

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

int main(){
    int N;
    ull K;
    cin >> N >> K;
    
    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A.at(i);
        A.at(i)--;
    }

    //if (K == 1) {
    //    cout << A.at(0) + 1 << endl;
    //    return 0;
    //}

    vector<bool> flag(N, false);
    int num = 0, rep = 0, start = 0;
    vector<int> ans_lst;
    
    while (true) {
        if (flag.at(num)) {
            start = num;
            break;
        }
        rep++;
        flag.at(num) = true;
        ans_lst.push_back(num);
        int num_tmp = num;
        num = A.at(num_tmp);
    }

    int minus = 0;

    for (int i = 0; i <= ans_lst.size(); i++) {
        if (ans_lst.at(i) == start) {
            minus = i;
            break;
        }
    }

    ll rep_tmp = rep - minus;
    //cout << rep_tmp << endl;
    if (K >= minus ){ 
        ll K_tmp = K - (ll)minus;
        //cout << K_tmp << endl;
        int ans_num = K_tmp % rep_tmp;
        //cout << ans_num << endl;
        cout << ans_lst.at(minus + ans_num) + 1 << endl;
    } else {
        cout << ans_lst.at((int)K) + 1 << endl;
    }

    return 0;
}


Measured memory_bytes: 5124
<?php
while (true) {
    list($height, $width) = getInputExplodeBySpaces();
    
    if ($height == 0 && $width == 0) {
       break;
    }

    $FrameRectangle = new FrameRectangle($height, $width);
    echo $FrameRectangle->makeFrameRectangle();
}
 
function getInputExplodeBySpaces()
{
    return explode(' ', trim(fgets(STDIN)));
}
  
class Rectangle
{
    public $height;
    public $width;
    public $hashSymbol  = '#';
    
    public function __construct($height, $width)
    {
        $this->height = $height;
        $this->width  = $width;
    }

    public function setRectangleParts()
    {
        for ($i = 0; $i < $this->height; $i++) {
            for($j = 0; $j < $this->width; $j++) {
                $rectangleParts[$i][$j] = $this->hashSymbol;
            }
        }
        return $rectangleParts;
    }
    
    public function mergeRectangleParts($rectangleParts)
    {
        for ($i = 0; $i < $this->height; $i++) {
            $lines[] = implode($rectangleParts[$i]).PHP_EOL;
        }
        return implode($lines).PHP_EOL;
    }
}
 
class FrameRectangle extends Rectangle
{
    public $dotSymbol = '.';
    
    public function makeFrameRectangle()
    {
        $lines = $this->setRectangleParts();
        for ($i = 1; $i < $this->height - 1; $i++) {
            for($j = 1; $j < $this->width - 1; $j++) {
                $lines[$i][$j] = $this->dotSymbol; 
            }
        }
        
        return $this->mergeRectangleParts($lines);
    }
}

Measured memory_bytes: 17592
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0;i < n;i++)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define ll long long

int main(){
	string s;
	cin >> s;
	if (s[0] != 'A') {cout << "WA" << endl; return 0;}
	ll pos = s.find('C');
	if (!((pos >= 2) && (pos <= s.size()-2))){cout << "WA" << endl; return 0;}
	FOR(i, 1, s.size()){
		if (i == pos){continue;}
		else if (!((s[i]>='a') && (s[i]<='z'))) {cout << "WA" << endl; return 0;}
	}
	cout << "AC" << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <string.h>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define MAX 10000

using namespace std;

#define ll long long
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define rep(i,a,n) for(int i=a; i<n; i++)
#define r0 return 0
#define INF (int)1e15
#define MOD 1000000007

#define access(i) a[i/3][i%3]
//#define random_shuffle(r...)random_shuffle(r,[](int _){return my_rand()%_;})

 int main(){

  string s;
  cin>>s;

  int n = s.size();
  long long cnt=0,flag=0;

  for(int i=0;i<n-1;i++){
      if(s[i] == 'R' && s[i+1] == 'R')
            cnt++;
  }

  for(int i=0;i<n;i++){
      if(s[i] == 'R')
            flag = 1;
  }

   if(cnt == 0 && flag == 0)
      cout<<"0"<<endl;
   else if(flag == 1 && cnt == 0)
      cout<<"1"<<endl;
   else
  cout<<cnt+1<<endl;

 return 0;
 }

Measured memory_bytes: 3620
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std;

int main() {
  
  int n,a,b,c,d,x;
  long long la,lb,lc,lx;
  double da,db,dc;
  string s,ss,sss;
  
  int ans = 0;
  string anss = "";
  
  cin >> a >> b;
  //vector<double> va(n);
  //vector<int> vb(n);
  //vector<int> vc(n-1);
  //rep(i,0,n) cin >> va.at(i);
  //rep(i,0,n) cin >> vb.at(i);
  //rep(i,0,n-1) cin >> vc.at(i);
  //int ab [] = {0 , 1 , 3 , 1 , 2 , 1 , 2 , 1 , 1 , 2 , 1 , 2 , 1};
  //int result3 = std::max({a, b, c});
//--------------------------------------------------------------------------------
ans = b-a+1;
  while(b+a-1>ans){
    cout << ans <<" ";
    ans++;
  }

  cout << ans << endl;
 // cout << fixed << setprecision(5) << ans << endl;

}

Measured memory_bytes: 256
{-# LANGUAGE TupleSections #-}

import qualified Data.ByteString.Char8 as B
import           Data.Maybe (fromJust)
import qualified Data.Map.Strict as M
import           Control.Monad (replicateM)

modT :: Integer
modT = 1000000007

main :: IO ()
main = do
  n <- getInt
  m <- M.fromListWith (+) . fmap ((, 1) . convert) <$> replicateM n getIntegers
  print . solve $ m

convert [a, b]
  | a == 0 && b == 0 = (0, 0)
  | a == 0 = (0, 1)
  | b == 0 = (1, 0)
  | otherwise = let gcd' = gcd a b
                in if b < 0
                   then (-div a gcd', -div b gcd')
                   else (div a gcd', div b gcd')

solve :: M.Map (Int, Int) Int -> Integer
solve map = let zero = M.findWithDefault 0 (0, 0) map
                ans = solve' . M.delete (0, 0) $ map
            in (fromIntegral zero + ans - 1) `mod` modT

solve' :: M.Map (Int, Int) Int -> Integer
solve' map =
  if M.null map
  then 1
  else let ((a, b), count) = M.elemAt 0 map
           inv = if a > 0
                 then (-b, a)
                 else (b, -a)
           count' = M.findWithDefault 0 inv map
           ncount = solve' . M.delete (a, b) . M.delete inv $ map
           ccount = ((2 ^ count) `mod` modT + (2 ^ count' - 1) `mod` modT)
             `mod` modT
       in ncount `seq` ccount `seq` (ncount * ccount) `mod` modT

getInt = fst . fromJust . B.readInt <$> B.getLine

getIntegers = fmap (fst . fromJust . B.readInt) . B.words <$> B.getLine


Measured memory_bytes: 94796
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
char buf[2010];
int d;
int main()
{
	scanf("%s",buf);
	scanf("%d",&d);
	for(int i=0;i<strlen(buf);i+=d)printf("%c",buf[i]);
	return 0;
}

Measured memory_bytes: 256
import std.stdio, std.typecons;

alias Tuple!(int, "from", int, "to", int, "value") Number;

void main() {
  int size, interval;
  while(readf("%d %d\n", &size, &interval), (size + interval) != 0) {
    Number[int] table;

    for(int i = 2; i < size; i++) {
      table[i] = Number(i - 1, i + 1, i);
    }
    table[1] = Number(size, 2, 1);
    table[size] = Number(size - 1, 1, size);

    int m = size;
    int len = 0;
    while(table.length != 1) {
      if (len == interval) {
        int to = table[m].to;
        int from = table[m].from;
        table.remove(m);
        table[from].to = to;
        table[to].from = from;
        m = to;
        len = 0;
      }
      else {
        m = table[m].to;
      }
      len++;
    }
    writeln(m);
  }
}

Measured memory_bytes: 1136
H,W=map(int,input().split())
A=[input() for x in range(H)]

ans=[]

for i in range(H):
  ch=False
  for j in range(W):
    if A[i][j]=='#':
      ch=True
      break
  if ch:
    ans.append(A[i])

ans=list(zip(*ans))
ans1=[]

for i in range(W):
  ch=False
  for j in range(len(ans[i])):
    if ans[i][j]=='#':
      ch=True
      break
  if ch:
    ans1.append(ans[i])
    
ans1=list(zip(*ans1))

for i in range(len(ans1)):
  print("".join(list(ans1[i])))


Measured memory_bytes: 3188
n = int(input())
data = [[] for i in range(n)]
for i in range(n):
    a = int(input())
    for _ in range(a):
        data[i].append(list(map(int,input().split())))

ans = 0
for i in range(1<<n):
    use = []
    for bit in range(n):
        if i&(1<<bit):
            use.append(bit+1)

    judge = True
    for j in use:
        for x,y in data[j-1]:
            if x in use and y == 0:
                judge = False
                break
            if x not in use and y == 1:
                judge = False
                break

    if judge:
        ans = max(ans,len(use))

print(ans)


Measured memory_bytes: 46684
n,m=map(int,input().split())
s=[]
for i in range(n):
    a1,b1=map(int,input().split())
    s.append([a1,b1])
s.sort()
k=0
h=0
for i in range(n):
    h+=s[i][1]
    k+=s[i][0]*s[i][1]
    if h>=m:
        k-=(h-m)*s[i][0]
        break
print(k)

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

int a, b;

int main() {
	scanf("%d%d", &a, &b);
	puts(a * b % 2 || a * b * 2 % 2 || a * b * 3 % 2 ? "Yes" : "No");
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    vector<int>p(n);
    
    for(int i=0;i<n;i++) cin >> p[i];
    
    int cnt = 0;
    for(int i=1;i<n-1;i++){
        if((p[i-1]<p[i] and p[i]<p[i+1]) or (p[i-1]>p[i] and p[i]>p[i+1])) cnt++;
    }
    
    cout << cnt;
}


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

int main(){
    ll n, m;
    cin >> n >> m;
    ll ans=1;
    ll i = 1;
    while(i<sqrt(m)){
        if(m%i==0){
            if(i>=n)ans = max(ans, m/i);
            else{
                if(i <= m/n){
                    ans = max(ans,i);
                }
            }
        }
        i++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
// statics
using namespace std;
using int64 = int_fast64_t;
using PAIR = pair<int64, int64>;
constexpr int INF = 1 << 30;
constexpr int64 LINF = 1LL << 60;
constexpr int MOD = 1e9 + 7;
constexpr int MAX_N = 1e5 + 1;

// init/input
#define int int64
#define INIT ios::sync_with_stdio(false);cin.tie(0);
#define VAR(type, ...) type __VA_ARGS__;MACRO_VAR_Scan(__VA_ARGS__);
template<typename T> void MACRO_VAR_Scan(T &t) {cin>>t;}
template<typename First, typename...Rest> void MACRO_VAR_Scan(First &first, Rest&...rest) {cin>>first;MACRO_VAR_Scan(rest...);}
#define VEC(type, c, n) vector<type> c(n);for(auto &&i:c)cin>>i;

// out
#define OUT(dist) cout<<(dist);
#define FOUT(n, dist) cout<<fixed<<setprecision(n)<<(dist);
#define SP cout<<" ";
#define BR cout<<endl;
#define zero(n) cout<<setfill('0')<<right<<setw(n)
#define debug(x) cerr<<#x<<":"<< (x);BR;

// utility
#define ALL(a) (a).begin(), (a).end()
#define EACH(i, a) for(auto &&i:(a))
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define RFOR(i, a, b) for(int i=(b)-1;i>=0;--i)
#define REP(i, n) for(int i=0;i<(n);++i)
#define RREP(i, n) for(int i=(n)-1;i>=0;--i)

signed main() {
  INIT;
	VAR(int, n, k);
	VEC(int, h, n);
	sort(ALL(h));

	int ans = INF;
	REP(i, n - k + 1) {
		ans = min(ans, h[i + k - 1] - h[i]);
		// debug(h[i + k - 1]);
	}
	OUT(ans)BR;
  
  return 0;
}


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

#define pout(n)  printf ("%d\n", n)

#define rep(i,a,n) for (int i = a;i < n;i++)
#define per(i,n,a) for (int i = n-1;i >= a;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());

const int d4x[4] = {1, 0, -1, 0};
const int d4y[4] = {0, 1, 0, -1};
const int d8x[8] = { 1,1,0,-1,-1,-1,0,1 };
const int d8y[8] = { 0,1,1,1,0,-1,-1,-1 };

#define MAX_N (int)2e5+20
#define INF 1e12+20

typedef long long ll;
using namespace std;
int main(){
	int n,m,z;
	cin >> n >> m;

	rep(x,0,n+1){
		rep(y,0,n+1){
			z = n-x-y;
			if(z < 0) break; 
			else if(m == 10000*x + 5000*y + 1000*z){
				printf("%d %d %d\n",x,y,z);
				return 0;
			}
		}
	}
	printf("-1 -1 -1\n");
	
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <set>
#include <unordered_map>
#include <vector>
#include <utility>
#include <cassert>
#include <algorithm>
#include <cstring>

using namespace std;

int main(int argc, char *argv[]) {
  int N;
  cin >> N;
  cout << ((N - 1) / 2) << endl;
  return 0;
}


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

using namespace std;

int main(){
	vector<int> vec;
	for (int i = 0; i < 3; i++) {
		int k;
		cin >> k;
		vec.push_back(k);
	}
	sort(vec.begin(), vec.end());
	cout << vec[2] * 10 + vec[1] + vec[0] << endl;
    return 0;
}

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

using namespace std;

typedef long long ll;
 
const int maxn = 1e5 + 10;

int par[maxn], cmp;

int get_par(int v){
	return par[v] < 0 ? v : par[v] = get_par(par[v]);
}

void merge(int v, int u){
	if ((v = get_par(v)) == (u = get_par(u)))
		return;
	cmp --;
	par[v] = u;
}

int main(){
	ios_base::sync_with_stdio (false);
	int n, m;
	cin >> n >> m;
	memset(par, -1, sizeof par);
	cmp = n;
	for (int i = 0; i < m; i++){
		int x, y, z;
		cin >> x >> y >> z;
		merge(x, y);
	}
	cout << cmp << endl;
}


Measured memory_bytes: 768
#include <bits/stdc++.h>
#define _overload3(_1,_2,_3,name,...)name
#define _rep(i,n)repi(i,0,n)
#define repi(i,a,b)for(int i=int(a),i##_len=(b);i<i##_len;++i)
#define MSVC_UNKO(x)x
#define rep(...)MSVC_UNKO(_overload3(__VA_ARGS__,repi,_rep,_rep)(__VA_ARGS__))
#define all(c)c.begin(),c.end()
#define write(x)cout<<(x)<<'\n'
using namespace std; using ll = long long; template<class T>using vv = vector<vector<T>>;
template<class T>auto vvec(int n, int m, T v) { return vv<T>(n, vector<T>(m, v)); }
constexpr int INF = 1 << 29, MOD = int(1e9) + 7; constexpr ll LINF = 1LL << 60;
struct aaa { aaa() { cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10); }; }aaaa;

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> H(N);
    rep(i, N) cin >> H[i];
    vv<int> graph(N);
    rep(i, M) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    int ans = 0;
    rep(i, N) {
        bool ok = true;
        for (int v : graph[i]) {
            if (H[v] >= H[i]) ok = false;
        }
        ans += ok;
    }
    write(ans);
}

Measured memory_bytes: 8740
## main

d, n = gets.strip.split(' ').map{|s| s.to_i}

ts = d.times.map{gets.strip.to_i}
wears = n.times.map{gets.strip.split(' ').map{|s| s.to_i}}
#p ts
#p wears

max_dc = []

for i in (0...n)
  if wears[i][0] <= ts[0] && ts[0] <= wears[i][1]
    max_dc << [wears[i][2], 0]
  end
end

for j in (1...d)
  p_max_dc = max_dc
  max_dc = []

  for i in (0...n)
    if wears[i][0] <= ts[j] && ts[j] <= wears[i][1]
      ci = wears[i][2]
      sdc = 0
      for pmdc in p_max_dc
        pci, psdc = pmdc
        dc = (ci - pci).abs + psdc
        sdc = dc if sdc < dc
      end
      max_dc << [ci, sdc]
    end
  end
end

puts max_dc.map{|mdc| mdc[1]}.max

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

//-----------------------------------LIBRARY OF INPUT-----------------------------------
void reader(int *x) {
	int k = getchar_unlocked(); *x = k - '0';
	while (true) {
		k = getchar_unlocked();
		if (k < '0' || k > '9') break;
		*x = ((*x) << 1) + ((*x) << 3) + k - '0';
	}
}

int n, m, q, dist[110003], mark[110003], u[210003], v[210003];
vector<pair<int, int>>x[110003], y[110003], z[110003]; bool used[210003];
inline bool isgood(int f) {
	for (int i = 0; i < z[f].size(); i++) {
		if (mark[z[f][i].first] == 0 && used[z[f][i].second] == false)return true;
	}
	mark[f] = 1;
	return false;
}
int main() {
	reader(&n); reader(&m); reader(&q); queue<int>Q;
	for (int i = 0; i < m; i++) {
		int a = 0, b = 0;
		reader(&a);
		reader(&b);
		u[i + 1] = a; v[i + 1] = b;
		x[a].push_back(make_pair(b, i + 1)); x[b].push_back(make_pair(a, i + 1));
	}
	Q.push(1); for (int i = 1; i <= n; i++)dist[i] = 999999; dist[1] = 0;
	while (!Q.empty()) {
		int a1 = Q.front(); Q.pop();
		for (int i = 0; i < x[a1].size(); i++) {
			if (dist[x[a1][i].first] > dist[a1] + 1) { dist[x[a1][i].first] = dist[a1] + 1; Q.push(x[a1][i].first); }
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < x[i].size(); j++) {
			if (dist[i] < dist[x[i][j].first]) { y[i].push_back(x[i][j]); }
			if (dist[i] > dist[x[i][j].first]) { z[i].push_back(x[i][j]); }
		}
	}
	int cnt = 0;
	for (int i = 0; i < q; i++) {
		int a = 0;
		reader(&a);
		used[a] = true;
		int E1 = u[a], E2 = v[a];
		if (dist[E1] == dist[E2]) { cnt += 0; }
		else {
			int a1 = 0; if (dist[E1] < dist[E2])a1 = E2; else a1 = E1;
			if (mark[a1] == 0 && isgood(a1) == false) {
				queue<int>Q; Q.push(a1); cnt++; mark[a1] = 1;
				while (!Q.empty()) {
					int a2 = Q.front(); Q.pop();
					for (int j = 0; j < y[a2].size(); j++) {
						if (mark[y[a2][j].first] == 0 && isgood(y[a2][j].first) == false) {
							Q.push(y[a2][j].first); cnt++;
						}
					}
				}
			}
		}
		printf("%d\n", cnt);
	}
	return 0;
}

Measured memory_bytes: 25628
#include <cstdio>
#include <cmath>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>

#ifdef _DEBUG
#define DMP(x) cerr << #x << ": " << x << "\n"
#else
#define DMP(x) ((void)0)
#endif

const int MOD = 1000000007, INF = 1111111111; 
using namespace std;
typedef long long lint;

int main() {

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

	lint N;
	cin >> N;

	string ans;

	if (N >= 0) {
		ans += N % 2 + '0';
		int st = 1;
		for (int i = 1; i <= 32; i++) {
			if (i % 2) st += (1LL << (i - 1));
			ans += int((N - st + (1LL << (i + 1))) % (1LL << (i + 1)) < (1LL << i)) + '0';
		}
		reverse(ans.begin(), ans.end());
	}
	else {
		ans += -(N-1)/2 % 2 + '0';
		int st = 1;
		for (int i = 1; i <= 32; i++) {
			if (i % 2) st += (1LL << (i - 1));
			ans += int((-(N-1)/2 - st + (1LL << (i + 1))) % (1LL << (i + 1)) < (1LL << i)) + '0';
		}
		reverse(ans.begin(), ans.end());
		ans += -N % 2 + '0';
	}

	for (int i = 0; i <= 32; i++) {
		if (ans[i] == '1') {
			cout << ans.substr(i) << "\n";
			break;
		}
		if (i == 32) cout << 0 << "\n";
	}

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 1e5 + 7;

unordered_map <string, int> ma;
int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    string s;
    ll ans = 0;
    for(int i = 0; i < n; i++)
    {
        cin>>s;
        sort(s.begin(), s.end());
        if(ma[s]) ma[s]++;
        else ma[s] = 1;
    }
    unordered_map <string, int> :: iterator it;
    for(it = ma.begin(); it != ma.end(); it++)
    {
        ll x = it->second;
        ans += x*(x-1)/2;
    }
    cout<<ans<<endl;

    return 0;
}



Measured memory_bytes: 10660
n,m=[int(i) for i in input().split()]
dp=[1,1] ;a=set() ; mod=(10**9+7)
for i in range(m):
    a.add(int(input()))
if 1 in a: dp[1]=0
for i in range(2,n+1):
    if i not in a:
        dp.append((dp[-1]+dp[-2])%mod)
    else:
        dp.append(0)
print(dp[-1])
    


Measured memory_bytes: 56536