akhauriyash/Code-Regression huggingface dataset:
N, K = map(int, input().split())
A = tuple(int(x) - 1 for x in input().split())

done = {0}
rt = [0]
loop_point = 0
while True:
    p = rt[-1]
    np = A[p]
    if np in done:
        loop_point = np
        break
    done.add(np)
    rt.append(np)
if K < len(rt):
    ans = rt[K] + 1
else:
    K -= len(rt)
    rt = rt[rt.index(loop_point):]
    ans = rt[K%len(rt)] + 1
print(ans)

Measured memory_bytes: 32460
#include<iostream>
using namespace std;
int main()
{
  char s[1002];
  cin>>s;
  int l=strlen(s);
  if(s[l-1]=='s')
  {
    s[l]='e';
    s[l+1]='s';
    s[l+2]='\0';
  }
  else
  {
    s[l]='s';
    s[l+1]='\0';
  }
  cout<<s;
}
  

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

struct element {
  int key;

  struct element *fp;
  struct element *bp;
};

struct element list;

void insert(int x);
void delete(int x);
void deleteFirst();
void deleteLast();

int main(int argc, char *argv[])
{
  int n, i;
  char cmd[11 + 3];
  int x;
  struct element *p;

  list.fp = &list;
  list.bp = &list;

  scanf("%d", &n);

  for (i = 0; i < n; i++) {
    scanf("%s", cmd);
    if (!strcmp(cmd, "insert")) {
      scanf("%d", &x);
      insert(x);
    } else if (!strcmp(cmd, "delete")) {
      scanf("%d", &x);
      delete(x);
    } else if (!strcmp(cmd, "deleteFirst")) deleteFirst();
    else if (!strcmp(cmd, "deleteLast")) deleteLast();
  }

  for (p = list.fp; p != &list; p = p->fp) {
    if (p->fp != &list) printf("%d ", p->key);
    else printf("%d\n", p->key);
  }

  return 0;
}

void insert(int x)
{
  struct element *p;

  p = (struct element *)malloc(sizeof(struct element));

  p->key = x;

  p->fp = list.fp;
  p->bp = &list;
  p->fp->bp = p;
  list.fp = p;
}

void delete(int x)
{
  struct element *p;
  int found = 0;

  for (p = list.fp; p != &list; p = p->fp) {
    if (p->key == x) {
      found = 1;
      break;
    }
  }

  if (found == 1) {
    p->bp->fp = p->fp;
    p->fp->bp = p->bp;
    p->fp = NULL;
    p->bp = NULL;

    free(p);
  }
}

void deleteFirst()
{
  struct element *p = list.fp;

  list.fp = p->fp;
  p->fp->bp = &list;
  p->fp = NULL;
  p->bp = NULL;

  free(p);
}

void deleteLast()
{
  struct element *p = list.bp;

  p->bp->fp = &list;
  list.bp = p->bp;
  p->fp = NULL;
  p->bp = NULL;

  free(p);
}

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

int A[50], n;

int solve(int d, int m){
    if( m == 0 ) return 1;
    if( d >= n ) return 0;
    int res = solve(d+1, m) || solve(d+1, m - A[d]);
    return res;
}


int main(void){
    
    int  q, M;
    
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> A[i];
    }
    
    cin >> q;
    
    for(int j = 0; j < q; j++){
        cin >> M;
        if( solve(0, M) ) cout << "yes" << endl;
        else cout << "no" << endl;
    }
    
}



Measured memory_bytes: 3100
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <string>
#include <vector>
#include <cstdlib>
#include <utility>
#include <map>

using namespace std;

int main(){
    string s;
    string ts;
    cin >> s >> ts;
    map<char, char> rule_change1{};
    map<char, char> rule_change2{};
    
    string a = "";
    bool ans = true;
    for(int i = 0; i < s.size(); i++){
        if(rule_change1.find(s[i]) == rule_change1.end()){
            rule_change1[s[i]] = ts[i];
        }else{
            if(!(rule_change1[s[i]] == ts[i])){
                ans = false;
                break;
            }
        }
        if(rule_change2.find(ts[i]) == rule_change2.end()){
            rule_change2[ts[i]] = s[i];
        }else{
            if(!(rule_change2[ts[i]] == s[i])){
                ans = false;
                break;
            }
        }
    }
    if(ans){
        cout << "Yes";
    }else{
        cout << "No";
    }
}


Measured memory_bytes: 776
#include <iostream>
using namespace std;
int main(){
    long int N,M;
    cin >> N >> M;
    long int ans = 0;
    if(N==1&&M==1)
        ans=1;
    else if(N==1)
        ans = M - 2;
    else if(M==1)
        ans = N - 2;
    else
        ans = N*M - (2*N+2*M-4);
 
    cout << ans << endl;
}

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

void foo(int arr[], int dp[], int n, int k) {
	for (int i = 2; i <= n; i++) {
      dp[i] = INT_MAX;
      for (int j = i - 1; j >= 1 && (i - j) <= k; j--) {
        dp[i] = min(dp[i], abs(arr[i] - arr[j]) + dp[j]);
      }
    }
}

int main() {
  int n, k;
  cin >> n >> k;
  int arr[n+1];
  for (int i = 1; i <= n; i++) {
    cin >> arr[i];
  }
  int dp[n+1] = {0};
  foo(arr, dp, n, k);
  cout << dp[n];
  return 0;
}


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

#define REP(i, start, count) for(int i=(start); i<(int)(count); ++i)
#define rep(i, count) REP(i, 0, count)
#define ALLOF(c) (c).begin(), (c).end()

typedef long long ll;
typedef unsigned long long ull;

ll N, K;

int main(void) {

    cin >> N >> K;

    int count = 1;
    ll A = 1;
    while (true) {
        A *= K;
        if (A > N) break;
        count++;
    }

    cout << count << endl;

    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;
import java.util.HashSet;
import java.util.Set;

class Main{
      public static void main(String args[]){
	Scanner sc = new Scanner(System.in);
	int amt = sc.nextInt();
	int kind = sc.nextInt();
	Set<Integer> st = new HashSet<Integer>();
	for(int i=0;i<kind;i++){
	    int num = sc.nextInt();
	    for(int j=0;j<num;j++){
        int tmp = sc.nextInt();
		Integer id = new Integer(tmp);
		st.add(id);
	    }
	}
	System.out.println(amt-st.size());
      }
}

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






// A
int main() {
  int K, A, B;
  cin >> K >> A >> B;
  
  if ((A % K) == 0 ) {
    cout << "OK" << endl;
  }
  else if ((B % K) == 0 ) {
    cout << "OK" << endl;
  }

  else if ((A / K) == (B / K)) {
    cout << "NG" << endl;
  }
  else {
    cout << "OK" << endl;
  }

}


Measured memory_bytes: 3636
#!/usr/bin/env python3
import sys
from math import ceil

def solve(N: int, A: int, B: int, h: "List[int]"):
    INF = 10000000000
    
    def f(K: int):
        c = 0
        for i in range(N):
            c += ceil(max(0, h[i] - B*K)/(A-B))

        if c <= K:
            return True
        else:
            return False


    def binary_search(ok: int, ng: int):
        while ok-ng > 1:
            mid = (ok+ng)//2
            if f(mid):
                ok = mid
            else:
                ng = mid
        return ok

    # def b(ok: int, ng: int):
        
    #     while ok-ng > 1:
    #         mid = (ok+ng)//2
    #         if f(mid):
    #             ok = mid
    #         else:
    #             ng = mid

    #     return ok

    print(binary_search(INF, 0))

    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    h = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A, B, h)

if __name__ == '__main__':
    main()


Measured memory_bytes: 7116
#include <stdio.h>

void shellsort(int a[], int l, int r);

int main(void)
{
  char a[5];
  int n;
  int d[110]={0};

  fgets(a, sizeof(a), stdin);
  sscanf(a, "%d", &n);

  for (int i = 0; i < n; i++) {
    scanf("%d", &d[i]);
  }
  shellsort(d, 0, n-1);
  int v = 0;
  for (int i = 0; i < n; i++) {
    if (d[i] == v) {
      d[i] = 0;
      continue;
    }
    v = d[i];
  }
  shellsort(d, 0, n-1);
  int ans=0;
  for (int i = 0; d[i] != 0; i++) {
    ans++;
  }


    printf("%d\n", ans);

    return 0;
}

void shellsort(int a[], int l, int r)
{
  int h;
  for (h=1; h <= (r-l)/9; h = 3*h+1)
      ;
      for (; h > 0; h /= 3) {
        for (int i = l+h; i <= r; i++) {
          int j = i;
          int v = a[i];
          while (j >= l+h && v > a[j-h]) {
            a[j] = a[j-h];
            j -= h;
          }
          a[j] = v;
        }
      }
}


Measured memory_bytes: 128
import java.util.*;
public class Main {
	public static void main(String[] args){
	Scanner sc = new Scanner(System.in);
    int K = sc.nextInt();
    int X = sc.nextInt();
    int total = 500 * K;
    if(total >= X)
      System.out.println("Yes");
    else
   	  System.out.println("No");
    }
}


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

int main() {
	int N;
	cin >> N;
	vector<string> S(N);
  	//string S[N];
	for (int i = 0; i < N; i++) cin >> S[i];
	sort(S.begin(), S.end());
  	//sort(S,S+N);
	S.erase(unique(S.begin(), S.end()), S.end());
	cout << S.size() << endl;
}


Measured memory_bytes: 9516
#include <iostream>
#include <string>
#define foor for(int i=0;i<n;i++)
#define yn cout<<"Yes"<<endl;else cout<<"No"<<endl;
#define ic int a;cin>>a;
#define ic2 ic int b;cin>>b;
#define ic3 ic2 int c;cin>>c;
int s = 0;
using namespace std;
int main() {
	string a; cin >> a;
	if (a == "SUN")cout << 7 << endl;
	else if (a == "MON")cout << 6 << endl;
	else if (a == "TUE")cout << 5 << endl;
	else if (a == "WED")cout << 4 << endl;
	else if (a == "THU")cout << 3 << endl;
	else if (a == "FRI")cout << 2 << endl;
	else cout << 1 << endl;
}

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

using namespace std;

using ll = long long;
using Pi = pair<int, int>;
using Pl = pair<ll, ll>;
using Ti = tuple<int, int, int>;
using Tl = tuple<ll, ll, ll>;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define F first
#define S second
#define Get(t, i) get<(i)>((t))
#define all(v) (v).begin(), (v).end()
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reps(i, f, n) for(int i = (int)(f); i < (int)(n); i++)
#define each(a, b) for(auto& a : b)

const int inf = 1 << 25;
const ll INF = 1LL << 55;

// Least Common Ancestor (Doubling)
struct LCA
{
  vector< vector<int> > tree, parent;
  vector<int> depth;
  int log_V;
  LCA(int V)
  {
    log_V = 1;
    while((1 << log_V) <= V) log_V++;
    tree.resize(V);
    parent.resize(log_V, vector<int>(V, -1));    
    depth.resize(V);
  }
  void add_edge(int f, int t)
  {
    tree[f].emplace_back(t);
    tree[t].emplace_back(f);    
  }
  void dfs(int u, int p, int d)
  {
    parent[0][u] = p;
    depth[u] = d;
    for(auto v : tree[u]) {
      if(v != p) dfs(v, u, d + 1);
    }
  }
  void init(int root = 0)
  {
    dfs(root, -1, 0);
    for(int i = 0; i + 1 < log_V; i++) {
      for(int v = 0; v < parent[i].size(); v++) {
	if(parent[i][v] < 0) parent[i + 1][v] = -1;
	else parent[i + 1][v] = parent[i][parent[i][v]];
      }
    }
  }
  int trace(int u, int v)
  {
    if(depth[u] > depth[v]) swap(u, v);
    for(int i = 0; i < log_V; i++) {
      if((depth[v] - depth[u]) >> i & 1) v = parent[i][v];
    }
    if(u == v) return u;
    for(int i = log_V-1; i >= 0; i--) {
      if(parent[i][u] != parent[i][v]) u = parent[i][u], v = parent[i][v];
    }
    return parent[0][u];
  }
  int dist(int u, int v) {
    return depth[u] + depth[v] - 2*depth[trace(u, v)];
  }
};


int main()
{
  int n; cin >> n;
  LCA lca(n);
  rep(i, n) {
    int k; cin >> k;
    while(k--) {
      int c; cin >> c;
      lca.add_edge(i, c);
    }
  }
  lca.init();
  int q; cin >> q;
  while(q--) {
    int u, v; cin >> u >> v;
    cout << lca.trace(u, v) << endl;
  }
  return 0;
}

Measured memory_bytes: 18196
#include <bits/stdc++.h>
using namespace std;
#define __ <<" "<<
#define ___ <<" "
#define bash push_back
#define ALL(x) x.begin(),x.end()
//#define int long long

struct IoSetup {
    IoSetup() {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout <<fixed<<setprecision(12);
        cerr <<fixed<<setprecision(12);
    }
}IoSetup;

typedef long long ll;
typedef pair < int , int >  pii;
static constexpr const signed int INF = 0x3f3f3f3f;
static constexpr const signed long long LINF = 0x3f3f3f3f3f3f3f3fLL;
static constexpr const signed int SMOD = 1000000007;
static constexpr const signed int NMOD = 998244353;
static constexpr const signed int dx[]={1,0,-1,0,1,1,-1,-1};
static constexpr const signed int dy[]={0,-1,0,1,-1,1,-1,1};

inline bool inside(int x,int y,int w,int h){return (x>=0 && y>=0 && x<w && y<h);}
template<class T>bool chmax(T &a, const T &b){return(a=max(a,b))==b;}
template<class T>bool chmin(T &a, const T &b){return(a=min(a,b))==b;}
inline int qp(int a,ll b,int mo){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}

int n, d, a;
vector<pii> v;
int imos[202020];

signed main() {

    cin >> n >> d >> a;
    
    for(int i = 0; i < n; i++) {
        int b, c;
        cin >> b >> c;
        v.bash({b, c});
    }

    sort(ALL(v));
    ll sum = 0;
    for(int i = 0, r = 0; i < n; i++) {
        imos[i+1] += imos[i];
        if(imos[i+1] * a>= v[i].second) continue;
        
        while(r < n &&v[r+1].first <= v[i].first + d + d) r++;

        ll lim = v[i].second - imos[i+1]*a;
        sum += (lim+a-1)/a;
        
        imos[i+1] += (lim+a-1)/a;
        imos[r+2] -= (lim+a-1)/a;
        
    }

    cout << sum << endl;
  
    return 0;
}



Measured memory_bytes: 2800
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    a,b,c,d=map(int,input().split())
    print(max(0,min(d,b)-max(a,c)))
resolve()

Measured memory_bytes: 38384
/*input
3
-10 5 -4
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	ios_base::sync_with_stdio(false);
	ll x;
	cin >> x;
	pair<ll, ll>ans;
	cin >> ans.first;
	ans.second = -1e15;
	ll y = ans.first;
	while (cin >> x)
	{
		ans = {x + max(ans.first, ans.second), -x + max(ans.first - 2 * y, ans.second + 2 * y)};
		y = x;
	}
	cout << max(ans.first, ans.second) << endl;
}

Measured memory_bytes: 256
/*
Keep clam  Believe youself
*/
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<stack>
#include<set>
#include<cmath>
#define Xiaobo main
#define DEBUG(x) cerr<<#x<<": "<<(x)<<endl
using namespace std;
const int maxn=2e5+7;
const int mod=1e9+7;
const double eps=1e-15;
const double pi=acos(-1);
const int INF=0x3f3f3f3f;
typedef long long ll;
ll read(){ll c = getchar(),Nig = 1,x = 0;while(!isdigit(c) && c!='-')c = getchar();if(c == '-')Nig = -1,c = getchar();while(isdigit(c))x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar();return Nig*x;}
ll gcd(ll a,ll b){ return b==0?a:gcd(b,a%b);}
//别急 dp找状态 问题看看本身的规律 贪心找方法
int Xiaobo()
{
	unsigned long long n,k;
	cin>>n;
	if(n&1) {
		cout<<0<<'\n';
		return 0;
	}
	ll ans=0;
	for(k=10;k<=n;k*=5) {
		ans+=n/k;
	}
	cout<<ans<<'\n';
	return 0;
}


Measured memory_bytes: 256
N,M=map(int,input().split())
C=[]
for i in range(N):
    C.append(list(map(int,input().split())))
D=sorted(C, key=lambda x: x[0])
#print(D)
i=0
sum1=0
while M>0:
    d=min(M,D[i][1])
    sum1+=D[i][0]*d
    M=M-d
    i=i+1
print(sum1)

Measured memory_bytes: 29792
using System;

namespace ITP1_9_C
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int tarou = 0;
            int hanako = 0;

            for (int i = 0; i < n; i++)
            {
                string data = Console.ReadLine();
                string t = data.Split(' ')[0];
                string h = data.Split(' ')[1];
                
                switch(string.Compare(t,h))
                {
                    case 1:  //太郎の勝ち
                        tarou += 3;
                        break;
                    case -1:  //花子の勝ち
                        hanako += 3;
                        break;
                    default: //引き分け
                        tarou++;
                        hanako++;
                        break;
                }
            }
            Console.WriteLine("{0} {1}", tarou, hanako);
        }
    }
}



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

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}

struct UnionFind{
    std::vector<int> data;
    UnionFind(int size):data(size,-1){}
    bool unite(int x,int y) {
        x=root(x);y=root(y);
        if(x!=y){
            if(data[y]<data[x])std::swap(x,y);
            data[x]+=data[y];data[y]=x;
        }
        return x!=y;
    }
    bool find(int x,int y) {
        return root(x)==root(y);
    }
    int root(int x) {
        return data[x]<0?x:data[x]=root(data[x]);
    }
    int size(int x) {
        return -data[root(x)];
    }
};


int main() {
	int n = ri();
	if (n == 1) {
		std::cout << 1 << std::endl;
		return 0;
	}
	int x[n];
	int y[n];
	for (int i = 0; i < n; i++) x[i] = ri(), y[i] = ri();
	std::set<std::pair<int, int> > changes;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < i; j++) {
			std::pair<int ,int> cur = {x[i] - x[j], y[i] - y[j]};
			if (cur.first < 0) cur.first = -cur.first, cur.second = -cur.second;
			changes.insert(cur);
		}
		
	int res = n;
	for (auto &change : changes) {
		UnionFind uni(n);
		for (int i = 0; i < n; i++)
			for (int j = 0; j < i; j++) {
				if ((x[i]-x[j] == change.first && y[i] - y[j] == change.second ) ||
					(x[j]-x[i] == change.first && y[j] - y[i] == change.second )) uni.unite(i, j);
				}
		std::set<int> all;
		for (int i = 0; i < n; i++) all.insert(uni.root(i));
		res = std::min<int>(res, all.size());
	}
	std::cout << res << std::endl;	
	return 0;
}


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

int main()
{
    long long N, K;
    cin >> N >> K;

//    if(abs(N - K) >= N)
//    {
//        cout << N << endl;
//        return 0;
//    }
//
//    else
//    {
//        N = abs(N - K);
//        cout <<  N << endl;
//
//        goto a;
//    }
    if(N >= K)
        N = N % K;

    if(N > abs(N - K))
        cout << abs(N - K) << endl;
    else
        cout << N << endl;

    return 0;

}


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

using namespace std;

int m, p, ans=0;

int main()

{    cin>>m>>p;

     for(int i=4;i<=m;++i)

           for(int j=22;j<=p;++j)

           {

                   int x=j/10, y=j%10;

                   if(x<=1 || y<=1)

                        continue;

                   if(x*y==i)

                             ans++;

           }

      cout<<ans<<endl;

     return 0;

}



Measured memory_bytes: 256
import java.util.Scanner;

class Main{
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        String input1 = input.nextLine();
        String[] str = input1.split(" ");
        int a = Integer.parseInt(str[0]);
        int b = Integer.parseInt(str[1]);
        int c = Integer.parseInt(str[2]);
        int count = 0;
        for(int i=a; i<=b; i++){
            if(c%i == 0){
                count = count + 1;
            }
        }
        System.out.println(count);
    }
}


Measured memory_bytes: 26292
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <cassert>
#include <utility>
#include <iomanip>
#include <chrono>
#include <random>
#include <bitset>

using namespace std;

#define sz(x) (int) x.size()
#define unique(x) x.erase(unique(x.begin(), x.end()), x.end())
#define all(a) a.begin(), a.end()
#define sqr(x) ((x) * (x)) 
#define y1 aksjdaskdjksjfksdjf
#define left kdnvldvoiwejifejg
#define right lkdsjflksdjfdjfk
#define prev asdasfsadjkjsdfjs
#define tm aklsjdasjdasjdkdjjf
#define lcm hddalkwjeidjjhasda
#define random_shuffle asdasdd

int n;
long long ans;

int main() { 

  cin >> n;
  for (int i = 0; i < n; i++) {
    int x;
    scanf("%d", &x);
    ans += x - 1;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define ii pair<int, int>
#define int long long
using namespace std;

const int mod = 998244353;
vector<ii> hold;
int st[800005];
int n, k;

void upd(int id, int l, int r, int i, int val)
{
    if (l > i || r < i)
        return;

    if (l == r)
    {
        st[id] = (st[id] + val) % mod;
        return;
    }

    int mid = (l + r) / 2;
    upd(id * 2, l, mid, i, val);
    upd(id * 2  + 1, mid + 1, r, i, val);

    st[id] = (st[id * 2] + st[id * 2 + 1]) % mod;
}

int get(int id, int l, int r, int u, int v)
{
    if (r < u || l > v)
        return 0;

    if (u <= l && r <= v)
        return st[id];

    int mid = (l + r) / 2;
    return (get(id * 2, l, mid, u, v) + get(id * 2 + 1, mid + 1, r, u, v)) % mod;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> k;

    for (int i = 1; i <= k; i++)
    {
        int x, y;
        cin >> x >> y;
        hold.emplace_back(x, y);
    }
    upd(1, 1, n, 1, 1);

    for (int i = 1; i <= n; i++)
    {
        int add = 0;
        for (auto j : hold)
            if (i - j.fi >= 0)
                add = (add + get(1, 1, n, i - j.se, i - j.fi)) % mod;
        upd(1, 1, n, i, add);
    }
    cout << get(1, 1, n, n, n);
}


Measured memory_bytes: 7756
require 'set'; require 'prime'
INF=Float::INFINITY; MOD=10**9+7
n,m = gets.chomp.split.map(&:to_i)
k = []
n.times do
  k.push gets.chomp.split.map(&:to_i).slice(1, m)
end

ans = 0
1.upto(m).each do |i|
  if k.all?{|man| man.include?(i)}
    ans += 1
  end
end

puts ans


Measured memory_bytes: 2172
#include<bits/stdc++.h>
#define fori(j,n) for(ll i=j;i<n;i++)
#define forb(n,j) for(ll i=n-1;i>=0;i--)
#define endl "\n"
#define pb push_back
#define ll long long
#define mp make_pair
#define ff first
#define ss second
#define vec vector<ll>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

void wldd()
{
	ll n;
	cin >> n;
	ll a[n];
	fori(0, n)
	{
		cin >> a[i];
	}
	ll c = 0;
	sort(a, a + n);
	for (ll i = 0; i < n - 2; i++)
	{
		for (ll j = i + 1; j < n - 1; j++)
		{
			for (ll k = j + 1; k < n; k++)
			{
				if (a[i] + a[j] > a[k] and (a[i] != a[j] and a[i] != a[k] and a[j] != a[k]))
				{
					c++;
					//cout << a[i] << " " << a[j] << " " << a[k] << endl;
				}
			}
		}
	}
	cout << c;
}

int32_t main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	IOS;
	/*ll t;
	cin >> t;
	while (t--)*/ wldd();
	return 0;
}

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

using namespace std;

struct Bipartite_Matching
{
  vector< vector< int > > graph;
  vector< int > match, alive, used;
  int timestamp = 0;

  Bipartite_Matching(int n)
  {
    graph.resize(n);
    alive.assign(n, 1);
    used.assign(n, 0);
    match.assign(n, -1);
  }

  void add_edge(int u, int v)
  {
    graph[u].push_back(v);
    graph[v].push_back(u);
  }

  bool dfs(int v)
  {
    used[v] = timestamp;
    for(int i = 0; i < graph[v].size(); i++) {
      int u = graph[v][i], w = match[u];
      if(alive[u] == 0) continue;
      if(w == -1 || (used[w] != timestamp && dfs(w))) {
        match[v] = u;
        match[u] = v;
        return (true);
      }
    }
    return (false);
  }

  int bipartite_matching()
  {
    int ret = 0;
    for(int i = 0; i < graph.size(); i++) {
      if(alive[i] == 0) continue;
      if(match[i] == -1) {
        ++timestamp;
        ret += dfs(i);
      }
    }
    return (ret);
  }

  int back(int k)
  {
    match[match[k]] = -1;
    match[k] = -1;
    ++timestamp;
    dfs(k);
    return (match[k]);
  }

  void decide(int k)
  {
    alive[match[k]] = 0;
    alive[k] = 0;
  }

};

int main()
{
  int N;
  scanf("%d", &N);
  --N;
  Bipartite_Matching flow(N + N);
  for(int i = 0; i < N; i++) {
    for(int j = 0; j < N; j++) {
      int k;
      cin >> k;
      if(k) flow.add_edge(j, N + i);
    }
  }
  auto get = flow.bipartite_matching();
  if(get < N) {
    cout << "no" << endl;
  } else {
    cout << "yes" << endl;
    for(int i = 0; i < N; i++) {
      printf("%d\n", flow.back(i) - N + 1);
      flow.decide(i);
    }
  }
}

Measured memory_bytes: 3420
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <iterator>
#include <math.h>
#include <cmath>
#include <deque>
#include <limits>
#include <numeric>

#define INF 100000000
#define MOD 1000000007

#define ll long long

using namespace std;

int main() {

	ll n, max;

	ll a[3005] = {};
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	
	
	ll ans = 0;

	for (int i = 0; i < n; i++)
	{
		
			ans += a[i] - 1;
	}
	
	cout << ans << endl;
}



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

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

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

    ll Ccnt = (B/C) - ((A-1)/C+1) + 1;
    ll Dcnt = (B/D) - ((A-1)/D+1) + 1;
    ll E = gcd(C, D) * (C/gcd(C,D)) * (D/gcd(C,D));
    ll Ecnt = (B/E) - ((A-1)/E+1) + 1;

    // cout << Ccnt << " " << Dcnt << " " << CDcnt << endl;

    cout << (B-A+1) - (Ccnt+Dcnt - Ecnt) << endl;
}


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

using namespace std;
using ll = long long;

int main() {
  int A, B, C, X, Y;
  cin >> A >> B >> C >> X >> Y;
  ll price = 0 * 2 * C + max(0, X - 0) * A + max(0, Y - 0) * B;
  for (int i = 1; i < 100001; ++i) {
    ll price_sub = i * 2 * C + max(0, X - i) * A + max(0, Y - i) * B;
    if (price > price_sub) {
      price = price_sub;
    }
  }
  cout << price << endl;
  return 0;
}


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

int main() {
    int n, m, k; cin >> n >> m >> k;
    for (int i = 0; i <= n; i++) for (int j = 0; j <= m; j++) {
        if (i * j + (n - i) * (m - j) == k) {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}

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

int main() {
    string S, T;
    cin >> S >> T;

    bool check = false;
    for(int i = 0; i < S.size(); i++) {
        int string_size = S.size() - 1;
        char back_string = S.at(string_size);
        char front_string = S.at(0);
        
        S.erase(S.begin());
        S.push_back(front_string);

        for(int i = 0; i < S.size() - 1; i++) {
            
        }

        //cout << S << endl;
        
        if(S == T) {
            check = true;
        }
    }

    if(check) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
}


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <utility>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int dx[]={-1,0,0,1};
int dy[]={0,0,-1,0};
int main()
{
    int n;
	cin>>n;
	while(n--){
		int panel[10]={};
		for(int i=0;i<10;i++){
			for(int j=0;j<10;j++){
				int tmp;
				cin>>tmp;
				panel[i]|=tmp<<j;
			}
		}
		for(int i=0;i<(1<<10);i++){//1??????ans?????????
			int ans[10]={};
			ans[0]=i;
			for(int j=0;j<9;j++){//????????????ans????¨????
				for(int k=0;k<10;k++){//?????????????????°???
					int tmp=0;
					for(int l=0;l<4;l++){
						int nx=k+dx[l],ny=j+dy[l];
						if(0<=nx&&nx<10&&0<=ny&&ny<9)tmp+=(ans[ny]>>nx)&1;
					}
					if((tmp+(panel[j]>>k)&1)%2)ans[j+1]|=1<<k;
				}
			}
			int check=ans[8];
			for(int j=0;j<10;j++){
				if((ans[9]>>j)&1){
					for(int k=-1;k<=1;k++){
						int x=j+k;
						if(0<=x&&x<10){
							if((check>>x)&1)check&=~(1<<x);
							else check|=1<<x;
						}
					}
				}
			}
			if(check==panel[9]){
				for(int y=0;y<10;y++){
					for(int x=0;x<10;x++){
						int tmp=(ans[y]>>x)&1;
						printf(x==9?"%d\n":"%d ",tmp);
					}
				}		
				break;
			}
		}
	}
    return 0;
}

Measured memory_bytes: 1144
#!/usr/bin/perl

my ($K,$N) = map { $_ - 0 } split(/\s+/,<STDIN>);
my @A = map { $_ - 0 } split(/\s+/,<STDIN>);

my $mx = -1;

for(my $i=0;$i<$N;$i++){
  my $n = ( ( $i+1 >= $N ) ? $A[$i+1 - $N]+$K : $A[$i+1] );
  my $d = $n - $A[$i];
  
  if( $d > $mx ){
    $mx = $d;
  }
}

my $r = $K - $mx;
print "$r\n";




Measured memory_bytes: 36556
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = input()
	basis = []
	ans = 0
	for i in range(n-1, -1, -1):
		if s[i] == "0":
			for b in basis:
				a[i] = min(a[i], a[i]^b)
			if a[i]:
				basis.append(a[i])
		else:
			for b in basis:
				a[i] = min(a[i], a[i]^b)
			if a[i]:
				ans = 1
				break
	print(ans)

Measured memory_bytes: 68644
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define FORR(i, a, b) for (int i = b - 1; i >= a; --i)
#define REP(i, n) FOR(i, 0, n)
#define REPR(i, n) FORR(i, 0, n)

const int inf = 999999999;
const int mod = 1e9 + 7;
const long double pi = 3.141592653589793238462643383279502884197;
const long double eps = 1e-7;

int main() {
	cin.tie(0);
	string s;
	cin >> s;
	for (int i = 0; i<s.size(); ++i) {
		if (s[i] == '1') s[i] = '9';
		else if (s[i] == '9')s[i] = '1';
	}
	cout << s;


	system("pause");
	return 0;
}

Measured memory_bytes: 504
#include <iostream>
#include <vector>
#include <cmath>
#include <limits>

using namespace std;

//??????????????\?????????????????§??????????±?????????¢?????´?????????
// #include<limits>?????\???????????¨

int maxv(int T){

	int Rt;//?????????????????????
	int Rmin;//???????????§???????°???????
	int Max = numeric_limits<int>::min();//?????§??????

	cin >> Rt;
	Rmin = Rt;

	for (int t = 0; t < T-1; t++){
		cin >> Rt;

		if (Max < Rt - Rmin)Max = Rt - Rmin;
		if (Rt < Rmin)Rmin = Rt;

	}

	return Max;

}



int main(){

	int n;
	cin >> n;

	cout<<maxv(n)<<endl;

	return 0;
}

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

int main() {
	int N, ans = 0;
	cin >> N;
	vector<int> B(N);
	for (int i = 0;i < N - 1;i++) {
		cin >> B[i];
	}
	for (int i = 0;i < N - 2;i++) {
		ans += min(B[i], B[i + 1]);
	}
	ans += B[0] + B[N - 2];
	cout << ans << endl;
}

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

int main(){
   int n;
  scanf("%d",&n);
  int a[n][3];

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


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

int main() {
	int N, K;
	string S;
	cin >> N >> K >> S;
	int ans = 1;
	for (int l = 0, r = 1, operate = S[0] == '0' ? 1 : 0;r < N;++ r) {
		if (r < N && S[r - 1] == '1' && S[r] == '0') { // rを追加したら操作回数が増えた時
			++ operate;
			if (operate > K) { // 反転回数がオーバーした
				++ l;
				while (S[l - 1] != '0' || S[l] != '1') ++ l;
				-- operate;
			}
		}
		ans = max(ans, r - l + 1);
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 512
#include <stdio.h>
#include <math.h>
#include <stdbool.h>
int main(void)
{
    char *S,*R;
    S = (char*)malloc(sizeof(char)*3);
    R = (char*)malloc(sizeof(char)*3);
    scanf("%s",S);
    scanf("%s",R);
    int count = 0;
    for(int i=0;i<3;i++){
        if(S[i]==R[i]){
            count++;
        }
    }
    printf("%d",count);
    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 7;

int main(){
	ios::sync_with_stdio(false); cin.tie(nullptr);
	LL n, m; cin >> n >> m;
	unordered_map<LL, int> hs1, hs2;
	for(LL i = 2; i <= n / i; ++ i){
		while(n % i == 0){
			++ hs1[i]; n /= i;
		}
	}
	if(n > 1) ++ hs1[n];
	for(LL i = 2; i <= m / i; ++ i){
		while(m % i == 0){
			++ hs2[i]; m /= i;
		}
	}
	if(m > 1) ++ hs2[m];
	int ans = 1;
	for(auto it : hs1){
		if(hs2.count(it.first)) ++ ans;
	}
	cout << ans << '\n';
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
using namespace std;
#define MOD 1000000007
#define INF 1<<30
#define LINF (ll)1<<62
#define rep(i,n) for(ll i=0; i<(n); i++)
#define REP(i,a,b) for(ll i=(a); i<(b); i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> P;
typedef vector<pair<ll, ll>> vpl;



int main(){
    ll n,m,c; cin >> n >> m >> c;
    vl b(m);
    rep(i,m) cin >> b[i];
    ll ans = 0;
    ll a;
    rep(i,n){
        ll sum = 0;
        rep(j,m){
            cin >> a;
            sum += a * b[j];
        }
        if(sum > -c) ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(){
		char s[100005];
		scanf("%s",s);
		int length_s=0;
		while(s[length_s]!=0)length_s++;
		int i;
		for(i=length_s-1;i>=0;){
			if(s[i]=='m'&&s[i-1]=='a'&&s[i-2]=='e'&&s[i-3]=='r'&&s[i-4]=='d')i-=5;
			else if(s[i]=='e'&&s[i-1]=='s'&&s[i-2]=='a'&&s[i-3]=='r'&&s[i-4]=='e')i-=5;
			else if(s[i]=='r'&&s[i-1]=='e'&&s[i-2]=='m'&&s[i-3]=='a'&&s[i-4]=='e'&&s[i-5]=='r'&&s[i-6]=='d')i-=7;
			else if(s[i]=='r'&&s[i-1]=='e'&&s[i-2]=='s'&&s[i-3]=='a'&&s[i-4]=='r'&&s[i-5]=='e')i-=6;
			else break;
		}
		//printf("%d",length_s);
		if(i<=0)puts("YES");
		else puts("NO");

		return 0;
}


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

using namespace std;

//#define MULTITEST
//#define _DEBUG

#define x first
#define y second
#define mp make_pair
#define pb push_back
#define sqr(a) ((a) * (a))
#define sz(a) int(a.size())
#define all(a) a.begin(), a.end()
#define forn(i, n) for(int i = 0; i < int(n); i++) 
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)

typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;

template <class A, class B> ostream& operator << (ostream& out, const pair<A, B> &a) {
	return out << "(" << a.x << ", " << a.y << ")";
}

template <class A> ostream& operator << (ostream& out, const vector<A> &v) {
	out << "[";
	forn(i, sz(v)) {
		if (i) out << ", ";
		out << v[i];
	}
	return out << "]";
}

mt19937 rnd(time(NULL));

const int INF = int(1e9);
const li INF64 = li(1e18);
const int MOD = int(1e9) + 7;
const ld EPS = 1e-9;
const ld PI = acos(-1.0);

const int N = 100 * 1000 + 13;

int d, t, s;

bool read() {
	if (scanf("%d %d %d", &d, &t, &s) != 3)
		return false;
	return true;
}

void solve() {
	if (t * s >= d) {
		printf("Yes\n");
	}
	else {
		printf("No\n");
	}
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);

	int tt = clock();

#endif

	cerr.precision(15);
	cout.precision(15);
	cerr << fixed;
	cout << fixed;

#ifdef MULTITEST
	int tc;
	scanf("%d", &tc);
	while (tc--) {
		read();
#else
	while (read()) {
#endif
		solve();

#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif

	}
	}

Measured memory_bytes: 3660
#include <iostream>

using namespace std;

int main(void){
    long long int x1;
    long long int x2;
    long long int x3;
    long long int x4;
    long long int x5;

    cin >> x1 >> x2 >> x3 >> x4 >> x5;

    if(x1 == 0){
        cout << "1" << endl;
    }
    else if(x2 == 0){
        cout << "2" << endl;
    }
    else if(x3 == 0){
        cout << "3" << endl;
    }
    else if(x4 == 0){
        cout << "4" << endl;
    }
    else if(x5 == 0){
        cout << "5" << endl;
    }

    return 0;
}

Measured memory_bytes: 3624
#include <stdio.h>
int main(void)
{
  int k,x,y,n,sum=0;
  scanf("%d%d%d%d",&n,&k,&x,&y);
  if(n<=k)
  {
    sum=n*x;
  }
  else
  {
    sum=k*x+(n-k)*y;
  }
  printf("%d\n",sum);
  return 0;
}


Measured memory_bytes: 128
# ALDS1_7_A: Rooted Trees

class Node
  attr_accessor :id, :parent, :left_child, :right_sub

  def depth
    @parent.nil? ? 0 : 1 + @parent.depth
  end

  def parent_id
    @parent.nil? ? -1 : @parent.id
  end

  def child_ids
    child_ids = []
    child     = @left_child
    until child.nil?
      child_ids << child.id
      child = child.right_sub
    end
    child_ids
  end

  def type
    return 'root' if parent.nil?
    return 'leaf' if child_ids.empty?
    'internal node'
  end
end

n_nodes = gets.to_i
tree    = Array.new(n_nodes).map { Node.new }

n_nodes.times do
  id, n_child_ids, *child_ids = gets.split.map &:to_i
  tree[id].id = id
  next if child_ids.empty?

  leftmost = child_ids[0]
  tree[id].left_child = tree[leftmost]

  child_ids.each_with_index do |child_id, i|
    r_sib_id = child_ids[i + 1]
    tree[child_id].right_sub = tree[r_sib_id] unless r_sib_id.nil?
    tree[child_id].parent    = tree[id]
  end
end

tree.each do |n|
  puts "node #{n.id}: parent = #{n.parent_id}, " << 
       "depth = #{n.depth}, #{n.type}, #{n.child_ids}"
end

Measured memory_bytes: 29660
#include <bits/stdc++.h>
using namespace std;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  string w, t;
  int num{0};
  getline(cin, w);
  while (getline(cin, t)) {
    if (t == "END_OF_TEXT") break;
    transform(t.begin(), t.end(), t.begin(), ::tolower);
    stringstream ss{t};
    while (getline(ss, t, ' ')) {
      if (!t.compare(w)) ++num;
    }
  }
  cout << num << '\n';
}



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

using namespace std;

typedef long long ll;

const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = (ll)1e9 + 7;

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

  deque<int> que;
  que.push_back(1);
  vector<int> dist(K + 5, INF);
  dist[1] = 1;

  while (not que.empty()) {
    int u = que.front(); que.pop_front();
    if (u == 0) { break; }

    int v = (u * 10) % K;
    if (dist[v] > dist[u]) {
      dist[v] = dist[u];
      que.push_front(v);
    }

    v = (u + 1) % K;
    if (dist[v] > dist[u] + 1) {
      dist[v] = dist[u] + 1;
      que.push_back(v);
    }
  }
  int ans = dist[0];
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 896
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <functional>
#include <limits.h>
#include <set>
#include <map>
#include <tuple>
using namespace std;

#define ll long long
#define ull unsigned long long
#define rep(i,N) for (ll i=0;i<N;i++)
#define loop(i,N,M) for(ll i=N;i<M;i++)
#define MAX(v) *max_element(v.begin(),v.end())
#define MIN(v) *min_element(v.begin(),v.end())
#define SORTL2S(type,v) sort(v.begin(),v.end(),greater<type>())
#define SORTS2L(type,v) sort(v.begin(),v.end())
#define SORTMF(v,func) sort(v.begin(),v.end(),func)

template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T &val) {
	std::fill((T*)array, (T*)(array + N), val);
}

ll N,M;

void solve() {
    cin >> N >> M;
    ll Right = N,Left=1;
    rep(i,M) {
        ll L,R;
        cin >> L >> R;
        Left = max(Left,L);
        Right = min(Right,R);
    }

    cout << (Right-Left+1 < 0 ? 0 : Right-Left+1);

	return;
}

int main() {

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

Measured memory_bytes: 256
/*author @dhanush*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define boost ios_base::sync_with_stdio(false);cin.tie(NULL)
#define pb push_back
#define se second
#define fi first
bool possible(ll mid, vector<ll>arr, ll k)
{
  for (auto x : arr)
  {
    k -= ceil(((1.0) * x) / mid) - 1;
  }
  if (k >= 0)
    return true;
  else
    return false;
}
int main()
{


  ll n, k;
  cin >> n >> k;
  ll l = 1, r = INT_MIN;
  vector<ll>arr(n);
  for (int i = 0; i < n; i++)
  {
    cin >> arr[i];
    r = max(arr[i], r);
  }
  ll ans = l;
  while (l <= r)
  {
    ll mid = l + (r - l) / 2;
    if (possible(mid, arr, k))
    {
      ans = mid;
      r = mid - 1;
    }
    else
    {
      l = mid + 1;
    }
  }
  cout << ans << endl;

}





Measured memory_bytes: 6284
n, m = map(int, input().split())
a = []
b = []

for i in range(m):
    x, y = map(int, input().split())
    a.append(x)
    b.append(y)

for i in range(n):
    count = 0
    for j in range(m):
        if a[j] == i+1:
            count += 1
        if b[j] == i+1:
            count += 1
    print (count)


Measured memory_bytes: 3060
n = int(input())
h = list(map(int,input().split()))
#print(h,n)

h_max = max(h)
ans = 0
for i in range(h_max):
    j = 0
    while j <= n-1:
        if h[j] == 0:
            j += 1
        else:
            while j <= n-1:
                if h[j] == 0:
                    ans += 1
                    j += 1
                    break
                elif j == n-1:
                    h[j] -= 1
                    ans += 1
                    j += 1
                    break
                else:
                    h[j] -= 1
                    j += 1
print(ans)

Measured memory_bytes: 39536
s = int(input())

visited = set()
visited.add(s)
m = 2
if s % 2 == 0:
    s = s / 2
else:
    s = 3 * s + 1

while s not in visited:
    visited.add(int(s))

    m += 1
    if s % 2 == 0:
        s = s / 2
    else:
        s = 3 * s + 1
print(m)

Measured memory_bytes: 38472
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;
import std.container.rbtree;

void main()
{
    auto N = readln.chomp.to!int;
    auto as = readln.split.to!(int[]);
    int[] bs;
    bs.length = N;
    foreach (i, a; as) bs[a-1] = i.to!int + 1;

    auto rbt = redBlackTree(0, N+1);
    long s;
    foreach (int i; 0..N) {
        auto a = bs[i];
        auto l = rbt.lowerBound(a).back;
        auto r = rbt.upperBound(a).front;
        s += (a-l).to!long * (r-a).to!long * (i+1).to!long;
        rbt.insert(a);
    }
    writeln(s);
}

Measured memory_bytes: 19856
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAXN 100000
#define LL long long
int n,h,w;LL ans;
struct edge{
	int u,v,w;
}e[MAXN+1];
int fa[MAXN*2+1],siz[MAXN*2+1],used[MAXN*2+1];
int read(){
	int x=0,F=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')F=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*F;
}
bool cmp(edge s1,edge s2){
	return s1.w>s2.w;
}
int xfind(int x){
	if(fa[x]==x)return x;
	return fa[x]=xfind(fa[x]);
}
int main()
{
	n=read(),h=read(),w=read();
	for(int i=1;i<=n;i++)
	e[i]=(edge){read(),read()+MAXN,read()};
	for(int i=1;i<=MAXN*2;i++)fa[i]=i,siz[i]=1;
	sort(e+1,e+n+1,cmp);
	for(int i=1;i<=n;i++){
		int a=xfind(e[i].u),b=xfind(e[i].v);
		if(a==b){
			if(siz[a]>=used[a]+1){
				used[a]++;
				ans+=e[i].w;
			}
		}else{
			if(siz[a]+siz[b]>=used[a]+used[b]+1){
				used[a]++;
				ans+=e[i].w;
			}
			used[a]+=used[b];
			siz[a]+=siz[b];
			fa[b]=a;
		}
	}
	printf("%lld",ans);
}

Measured memory_bytes: 4224
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <string>
#include <iostream>
#include <fstream>
#include <algorithm>
#include <assert.h>
#include <ctype.h>
#include <limits.h>
#include <math.h>
#include <cmath>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <bitset>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <sstream>

using namespace std;
const double PI = acos(-1.0);
const double EPS = 1e-11;
typedef long long ll;
const ll MOD = 1000000007;
const int N = 100000 + 7;
typedef unsigned long long ull;

//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
void fast() {
    std::ios_base::sync_with_stdio(0);
    cin.tie(0);
}

/*                What if i lose? only losers think like that. But the answer is you will lose rate.                */


ll n, k, x;
vector<ll> arr;

int main() {
#ifndef ONLINE_JUDGE
    freopen("Input.txt", "r", stdin);
    freopen("Output.txt", "w", stdout);
#endif
    fast();

    cin >> n >> k;
    arr.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    sort(arr.begin(),arr.end());

    if(arr[arr.size()-1]==0&&k&1)
        return puts("0"),0;

    ll ans = 1;
    if(k&1 && arr[arr.size()-1]<0){
        for(int i=arr.size()-1;k;i--,k--){
            ans*=arr[i];
            ans=(ans%MOD+MOD)%MOD;
        }
        return cout<<ans<<endl,0;
    }

    int ptr1=0,ptr2=arr.size()-1;
    if(k&1){
        ans=arr[arr.size()-1];
        k--;
        ptr2--;
    }

    while(k){
        if(arr[ptr1]*arr[ptr1+1]>arr[ptr2]*arr[ptr2-1]){
            k-=2;
            ans*=arr[ptr1];
            ans=(ans%MOD+MOD)%MOD;
            ans*=arr[ptr1+1];
            ans=(ans%MOD+MOD)%MOD;
            ptr1+=2;
        }else{
            k-=2;
            ans*=arr[ptr2];
            ans=(ans%MOD+MOD)%MOD;
            ans*=arr[ptr2-1];
            ans=(ans%MOD+MOD)%MOD;
            ptr2-=2;
        }
    }
    cout<<ans<<endl;

    return 0;
}		

Measured memory_bytes: 4788
#include<bits/stdc++.h>
using namespace std; 
typedef long long ll;
#define pb push_back
#define fi first
#define se second 
int cnt[10004];
int a[200005];
int b[200005];
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n,p;
	cin>>n>>p;
	if(p==2 or p==5){
		ll ans = 0;
		for(ll i=0;i<n;i++){
			char c; 
			cin>>c; 
			int x = c-'0';
			if(x%p==0)ans+=(i+1);
		}
		cout<<ans<<endl;
	}
	else{
		cnt[0] = 1;
		ll ans = 0;
		ll lst = 0;
		for(int i=0;i<n;i++){
			char c; 
			cin>>c; 
			int x = c-'0';
			a[i] = x;
		}
		ll p10 = 1;
		for(int i=n-1;i>=0;i--){
			lst+=a[i]*p10; 
			p10*=10;
			p10%=p;
			lst%=p;
			ans+=cnt[lst];
			cnt[lst]++;
		}
		cout<<ans<<endl;
	}
	return 0;
}


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

#define ll long long
#define rep(A,B,C) for(A=B;A<C;++A)
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std;

/////////////////////////////////////////////////////

ll N;

ll i, j, k;

int main(){
    scanf("%lld", &N);
    printf("%lld", (1000-N%1000)%1000);
    return 0;
}

Measured memory_bytes: 3828
package main

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

var sc = bufio.NewScanner(os.Stdin)

func init() {
	sc.Split(bufio.ScanWords)
	sc.Buffer([]byte{}, math.MaxInt64)
}

func readInt() int {
	sc.Scan()
	r, _ := strconv.Atoi(sc.Text())
	return r
}

func sum(nums []int) int {
	sum := 0
	for _, num := range nums {
		sum += num
	}
	return sum
}

func main() {
	// Input
	var n, m int
	n = readInt()
	t := make([]int, n)
	for i := 0; i < n; i++ {
		t[i] = readInt()
	}
	m = readInt()
	p := make([]int, m)
	x := make([]int, m)
	for i := 0; i < m; i++ {
		p[i], x[i] = readInt(), readInt()
	}

	// Calculate
	for i := 0; i < m; i++ {
		fmt.Println(sum(t) - t[p[i]-1] + x[i])
	}
}


Measured memory_bytes: 640
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Integer arr[] = new Integer[n];

        for (int i = 0; i < n; ++i) {
            arr[i] = sc.nextInt();
        }

        Arrays.sort(arr, Comparator.reverseOrder());

        int layer = 1;
        for (int i = 1; i < n; ++i) {
            if (arr[i-1] > arr[i]) ++layer;
        }

        System.out.println(layer);
    }
}

Measured memory_bytes: 23764
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,k,s,i,j;cin>>n>>k;
    s=(n-1)*(n-2)/2;
    if(k>s){cout<<-1<<endl;return 0;}
    s+=n-1-k;
    cout<<s<<endl;
    for(i=0;i<n-1&&s>0;i++)
        for(j=i+1;j<n&&s>0;j++,s--)
            cout<<i+1<<" "<<j+1<<endl;
}

Measured memory_bytes: 256