akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using Pll = pair<ll, ll>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(v) v.begin(), v.end()
#define sz(x) ((int) x.size())
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define F first
#define S second
const int MOD = 1000000007;
template<class T> void print(const T& t){ cout << t << endl; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(){
  ll s;
  cin >> s;
  bool a = true;
  bool b = true;
  ll c = s % 100;
  ll d = s / 100;
  if(c>12||c==0){
    a = false;
  }
  if(d>12||d==0){
    b = false;
  }
  if(a==true&&b==true){
    print("AMBIGUOUS");
  }
  else if(a==true&&b==false){
    print("YYMM");
  }
  else if(a==false&&b==true){
    print("MMYY");
  }
  else{
    print("NA");
  }
}

Measured memory_bytes: 256
/* Bismillahir Rahmanir Rahim */
#include<bits/stdc++.h>
#include<vector>
#include<cmath>
#include<string>
#define   mod          1000000007
#define   lp(i,n)      for(int i=1;i<=n;i++)
#define   lpp(i,a,b)    for(int i=a,i<=b;i++)
#define   stlp(i,n)    for(int i=0;i<n;i++)
#define   ll           long long int
#define   ull          unsigned long long int
#define   tst          int t;cin>>t;while(t--)
#define   pb           push_back
#define   vi           vector<int>v
#define   vs           vector<string>v
#define   rslt(x)      cout<<x<<endl;
#define   mp(x,y)      make_pair(x,y)
#define   yes          rslt("yes")
#define   YES          rslt ("YES")
#define   Yes          rslt ("Yes")
#define   srt(v)       sort(v.begin(),v.end())
#define   gcd(a,b)     __gcd(a,b)
#define   lcm(a,b)     (a*gcd(a,b))/b
#define   max          1000007
#define   str          int s[200000]

using namespace std;
int main()
{
    ll x,y,z;
    cin>>x>>y>>z;
    ll a = x/y;
    if(x%y)
        a++;
    cout<<a*z<<endl;




    return 0;
}


Measured memory_bytes: 3608
k, n = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(lambda x: x+k, a))
a1 = a+b
c=9999999999999999999999
for i in range(n):
  c = min(abs(a1[i] - a1[i+n-1]),c)
print(c)

Measured memory_bytes: 26436
n, m = map(int, input().split())
p = [0]*m
s = [0]*m
for i in range(m):
    p[i], s[i] = input().split()
    p[i] = int(p[i])

ac = [0]*n
wa = [0]*n

ans_count = 0
penalty_count = 0

for i in range(m):
    if s[i] == "AC":
        ac[p[i]-1] += 1
        if ac[p[i]-1] == 1:
            ans_count += 1
            penalty_count += wa[p[i]-1]
    else:
        wa[p[i]-1] += 1

print(ans_count, penalty_count)

Measured memory_bytes: 14836
#include <iostream>
using namespace std;
typedef long long ll;
int main(){
    int n;
    cin >> n;
    ll cnt = 0;
    for (int i=1;i<=n;i++){
        if (i % 3 == 0 && i % 5 == 0){
        } else if (i % 3 == 0){
        } else if (i % 5 == 0){
        } else {
            cnt+=i;
        }
    }
    cout << cnt;
    return 0;
}

Measured memory_bytes: 3192
#include<iostream>
#include<cmath>
using namespace std;
#define EPS 1e-10

double a,b,c,d,e,f,g,h;
double det(){
	double dx1,dy1,dx2,dy2;
	dx1 = a-c;
	dy1 = b-d;
	dx2 = e-g;
	dy2 = f-h;
	return dx1*dy2 - dy1*dx2;
}
int main(){
	int n;
	cin>>n;
	while(n--){
		cin>>a>>b>>c>>d>>e>>f>>g>>h;
		cout<<(fabs(det())<EPS?"YES":"NO")<<endl;
	}
	return 0;
}

Measured memory_bytes: 1224
#include <cassert>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
#include <random>
#include <memory>
#include <utility>
#include <limits>
#include "limits.h"
 
#define rep(i, a, b) for (long long (i) = (a); i < (b); i++)
#define all(i) i.begin(), i.end()
#define debug(i) std::cerr << "debug " <<"LINE:"<<__LINE__<<"  "<< #i <<":"<< i << std::endl

 
template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, std::pair<T1, T2> pa) {
  return os << pa.first << " " << pa.second;
}
 
template <typename T>
std::ostream& operator<<(std::ostream& os, std::vector<T> vec) {
  for (int i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");
  return os;
}
 
template<typename T1,typename T2>
inline bool chmax(T1& a,T2 b){return a<b && (a=b,true);}
 
template<typename T1,typename T2>
inline bool chmin(T1& a,T2 b){return a>b && (a=b,true);}
 
long long pow_mod(long long a, long long b, long long mod=-1) {
  if ((a == 0)||(mod!=-1&&a%mod==0)) {
    return 0;
  }
 
  long long x = 1;
 
  while (b > 0) {
    if (b & 1) {
      x = (mod!=-1)?(x * a) % mod:x*a;
    }
    a = (mod!=-1)?(a * a) % mod:a*a;
    b >>= 1;
  }
  return x;
}
 
// const long long MOD = 998244353;
const long long MOD = 1e9 + 7;

using ll = long long;
using P = std::pair<ll, ll>;

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

  ll n;
  std::string s;

  std::cin>>n;
  std::cin>>s;

  std::map<std::pair<std::string,std::string>,ll> dic;

  for(ll bit=(1ll<<n) -1;bit>=0;bit--){
    std::string a="",b="";
    rep(i,0,n){
      if((bit>>i)&1)a+=s[i];
      else b+=s[i];
    }

    dic[{a,b}]++;
  }

  ll ans=0;

  for(ll bit=(1ll<<n) -1;bit>=0;bit--){
    std::string a="",b="";
    rep(i,0,n){
      if((bit>>i)&1)a+=s[2*n-1-i];
      else b+=s[2*n-1-i];
    }

    ans+=dic[{a,b}];
  }

  std::cout<<ans<<"\n";

  return 0;
}

Measured memory_bytes: 91904
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        try (InputReader in = new InputReader(); PrintWriter out = new PrintWriter(System.out)) {
            new Main().solve(in, out);
            out.flush();
        }
    }

    void solve(InputReader in, PrintWriter out) {
        String s = in.next();
        Map<Character, Integer> map = new HashMap<>();
        char tmp = '\0';
        for (char c : s.toCharArray()) {
            map.merge(c, 1, Integer::sum);
            tmp = c;
        }

        if (map.size() == 2 && map.get(tmp) == 2) {
            out.println("Yes");
        } else {
            out.println("No");
        }
    }
}

class InputReader implements AutoCloseable {
    private final Scanner sc = new Scanner(System.in);

    String next() {
        return this.sc.next();
    }

    int nextInt() {
        return Integer.parseInt(this.sc.next());
    }

    long nextLong() {
        return Long.parseLong(this.sc.next());
    }

    double nextDouble() {
        return Double.parseDouble(this.sc.next());
    }

    @Override
    public void close() {
        this.sc.close();
    }
}


Measured memory_bytes: 30292
#include <bits/stdc++.h>
#define ll long long int
#define ld long double
#define big 1e18

using namespace std;


int main()

{

ios_base::sync_with_stdio(false);
cin.tie(NULL);



  //  ll t;
  //  cin>>t;
   // while(t--)
   {
       ll N;
       cin>>N;
       ll H[N]={0};

       for(ll i=0; i<N; i++)
       {
           cin>>H[i];
       }

       ll c=0;
       ll mi=big;
       for(ll i=0; i<N; i++)
       {
           if(H[i]<mi)
           {
               mi=H[i];
           }
       }
       for(ll i=0; i<N; i++)
       {
           H[i]-=mi;
       }

       c+=mi;

     /*   for(ll i=0; i<N; i++)
        {
            cout<<H[i]<<" ";
        }
        cout<<endl;
        */

      // cout<<c<<endl;
       //continue;

       while(true)
       {
           ll flag=0;

           for(ll g=0; g<N; g++)
           {
                   flag+=H[g];
           }

           if(flag==0)
           {
               break;
           }

               ll i=0;
               while(i<N)
               {

                   ll mi1=big;
               if(H[i]==0 && i<N)
               {


              while(i<N && H[i]==0)
              {
                  i++;
              }

               }
               else
               {
                  ll in=i;

              while( i<N && H[i]!=0)
              {
                   if(H[i]<mi1)
                  {
                      mi1=H[i];
                  }
                  i++;
              }

             ll la=i-1;

              for(ll g=in; g<=la; g++)
              {
                  H[g]-=mi1;
              }
              c+=mi1;

               }

          }


           flag=0;

           for(ll g=0; g<N; g++)
           {
                   flag+=H[g];
           }

           if(flag==0)
           {
               break;
           }
       }

       cout<<c<<endl;



   }


return 0;

}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;

namespace ExhaustiveSearch
{
    internal class Program
    {
        private static int[] array;
        public static void Main(string[] args)
        {
            var n = int.Parse(ReadLine());
            array = ReadLine().Split(' ').Select(int.Parse).ToArray();
            var q = int.Parse(ReadLine());
            var ask = ReadLine().Split(' ').Select(int.Parse);

            foreach (var i in ask)
            {
                WriteLine(Solve(0,i) ? "yes":"no");
            }
        }

        private static bool Solve(int i, int m)
        {
            if (m == 0) return true;
            if (i >= array.Length) return false;
            var res = Solve(i + 1, m) || Solve(i + 1, m - array[i]);
            return res;
        }
    }
}


Measured memory_bytes: 18300
import java.lang.Math;
import java.util.Arrays;
import java.util.Scanner;

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

        int N = sc.nextInt();
        int[] h = new int[N+1];

        for (int i = 0; i < N; i++) {
            h[i+1] = sc.nextInt();
        }

        int[] dp = new int[N+1];
        dp[N] = 0;
        dp[N-1] = Math.abs(h[N] - h[N-1]);

        for (int i = N-2; i >= 1; i--) {
            dp[i] = Math.min(Math.abs(h[i] - h[i+1]) + dp[i+1], Math.abs(h[i] - h[i+2]) + dp[i+2]);
        }

        // System.out.println(Arrays.toString(dp));

        System.out.println(dp[1]);
    }
}


Measured memory_bytes: 50748
#include<bits/stdc++.h>
using namespace std;
int ans;
string s,t;
void END(){
  cout<<ans<<endl;
  exit(0);
}
string dfs(int depth){
  if(!depth)return t;
  string x=dfs(depth-1);
  string res=x;
  for(int i=0;i<t.size();i++){
    res+=(t[i]+x);
    if(res.size()>s.size())END();
  }
  return res;
}
bool ch(string x){
  int p=0;
  x+='@';
  for(int i=0;i<s.size();i++){
    if(s[i]==x[p])p++;
  }
  return p==x.size()-1;
}
int main(){
  cin>>s>>t;
  for(int i=0;;i++){
    string x=dfs(i);
    if(ch(x))ans++;
    else END();
  }
}



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

int a, b;

bool ok(string s) {
    if(s[a] != '-') return false;

    for(int i=0; i<a; i++) {
        if(!(s[i] >= '0' && s[i] <= '9')) return false;
    }

    int cnt = 0;
    for(int i=a + 1; i<s.size(); i++) {
        cnt++;
        if(!(s[i] >= '0' && s[i] <= '9')) return false;
    }

    if(cnt != b) return false;
    return true;
}

int main() {
    string s;
    cin>>a>>b>>s;

    if(ok(s)) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;

    return 0;
}


Measured memory_bytes: 256
#include <math.h>
#include <iostream>
#include <iomanip>

using namespace std;

int main()
{
	double a, b, c, d, e, f;
	while(cin >> a >> b >> c >> d >> e >> f)
	{
		double x = (c*e - b*f) / (a*e - b*d);
		double y = (c - a*x) / b;

		x = ( (double)( (int)(x * 1000) ) ) / 1000;
		y = ( (double)( (int)(y * 1000) ) ) / 1000;

		cout << setiosflags(ios::fixed) << setprecision(3);
		cout << x << " " << y << endl;
	}
	return 0;
}

Measured memory_bytes: 1284
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define yesno(flg) if(flg){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define vi vector<int>
#define pb push_back
#define i197 1000000007
#define MAX_N 200002
using namespace std;

typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<Pii,int> Piii;
const ll inf=100000000000000000;
struct edge{
	int myc,to,c,cost;
};
struct pos2{
	int to,from;
	ll cost;
};
struct pos{
	int to;
	ll cost;
};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};

vector<pos> vec[100001];
ll dpV[100001];
ll dpU[100001];
ll dp[100001][4];
int main() {
	int n,m;
	int s,t,u,v;
	cin>>n>>m>>s>>t>>u>>v;

	rep(i,m){
		int a,b;
		ll c;
		cin>>a>>b>>c;
		vec[a].push_back(pos{b,c});
		vec[b].push_back(pos{a,c});
	}
	rep(i,n){
		dpU[i+1]=inf;
		dpV[i+1]=inf;
		dp[i+1][0]=inf;
		dp[i+1][1]=inf;
		dp[i+1][2]=inf;
		dp[i+1][3]=inf;
	}
	auto calc = [](pos2 l,pos2 r){return l.cost > r.cost;};
	priority_queue<pos2,vector<pos2>,decltype(calc)> que(calc);
	que.push(pos2{v,v,0});
	while(!que.empty()){
		pos2 p2=que.top();que.pop();
		if(p2.cost>=dpV[p2.to])continue;
		dpV[p2.to]=p2.cost;
		for(auto it:vec[p2.to]){
			que.push(pos2{it.to,p2.to,p2.cost+it.cost});
		}
	}
	que.push(pos2{u,u,0});
	while(!que.empty()){
		pos2 p2=que.top();que.pop();
		if(p2.cost>=dpU[p2.to])continue;
		dpU[p2.to]=p2.cost;
		for(auto it:vec[p2.to]){
			que.push(pos2{it.to,p2.to,p2.cost+it.cost});
		}
	}
	ll r=dpU[v];

	que.push(pos2{s,s,0});
	while(!que.empty()){
		pos2 p2=que.top();que.pop();
		if(p2.cost>dp[p2.to][0])continue;
		dp[p2.to][1]=min(dp[p2.to][1],min(dp[p2.from][1],dpV[p2.to]));
		dp[p2.to][2]=min(dp[p2.to][2],min(dp[p2.from][2],dpU[p2.to]));
		dp[p2.to][3]=min(min(dp[p2.to][3],dp[p2.from][3]),min(dp[p2.to][1]+dpU[p2.to],dp[p2.to][2]+dpV[p2.to]));
		if(dp[p2.to][0]==p2.cost)continue;
		dp[p2.to][0]=p2.cost;
		for(auto it:vec[p2.to]){
			que.push(pos2{it.to,p2.to,p2.cost+it.cost});
		}
	}


//	rep(i,n)cout<<dpU[i+1]<<endl;
	cout<<min(r,dp[t][3])<<endl;

	return 0;
}



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

using namespace std;

#define pb push_back
#define fi first
#define se second
#define FastIO ios_base::sync_with_stdio(false); cin.tie(NULL);
typedef long long ll;

int dp[100000];

int main(){
    int n,k;
    cin >> n >> k;
    int h[n];
    for(int i = 0; i < n; i++) cin >> h[i];
    for(int i = 0; i < n; i++) dp[i] = INT_MAX;

    dp[0] = 0;
    for(int i = 1; i < n; i++)
        for(int j = i-1; j >= i-k && j >= 0; j--)
            dp[i] = min(dp[i], abs(h[i] - h[j]) + dp[j]);

    cout << dp[n-1];
    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<(n); ++i)
#define repr(i, a, b) for (int i=a; i<(b); ++i)
#define reprev(i, n) for (int i=n-1; i>=0; --i)
#define reprrev(i, a, b) for (int i=b-1; i>=(a); --i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
    cout << fixed << setprecision(10);
    
    int n, m; cin >> n >> m;
    int ma = m/n;
    // 有りうるa
    // mの約数
    vector<int> my;
    repr(x, 1, sqrt(m+1)) {
        if (m % x == 0) {
            my.emplace_back(x);
            my.emplace_back(m/x);
        }
    }
    // sort(my);
    int ans = 1;
    for (auto x: my) {
        if (m % x == 0 && m / x >= n) {
            ans = max(ans, x);
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
N, M = map(int, input().split())
E = [[] for i in range(N)]
R = []
for i in range(M):
    a, b = map(int, input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)
    R.append((a-1, b-1))

def Bridge(a, b):
    Cost = [51 for i in range(N)]
    Cost[a] = 0
    Q = [a]
    while Q:
        now = Q.pop(0)
        for next in E[now]:
            if now != a or next!=b:
                if Cost[next] == 51:
                    Cost[next] = Cost[now] + 1
                    Q.append(next)
    if Cost[b] == 51:
        return True
    else:
        return False

ans = 0
for r in R:
    if Bridge(r[0], r[1]):
        ans += 1
print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i, n) for(int i = 1; i <= n; i++)
template<class T> inline int chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline int chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF = 1<<29;
const ll LINF = 1LL<<58;
const int mod = 1000000007;

int main(){
    int a, b;
    cin >> a >> b;
    for (int i = 0; i < 10000; i++) {
        double x = i * 1.0;
        if(floor(x * 0.08) == a && floor(x * 0.1) == b){
            cout << i << endl;
            return 0;
        }
    }
    cout << -1 << endl;
    return 0;
}

Measured memory_bytes: 256
# abc118_b.py
# https://atcoder.jp/contests/abc118/tasks/abc118_b

# B - Foods Loved by Everyone /
# 実行時間制限: 2 sec / メモリ制限: 1024 MB
# 配点 : 200点

# 問題文
# カツサンドくんはオムライスが好きです。
# 他にも明太子や寿司、クリームブリュレやテンダーロインステーキなどが好きで、これらの食べ物は全て、誰もが好きだと信じています。
# その仮説を証明するために、N人の人に M種類の食べ物について好きか嫌いかの調査を行いました。
# 調査の結果、i番目の人は Ai1 番目, Ai2 番目, ..., AiKi番目の食べ物だけ好きだと答えました。
# N人全ての人が好きだと答えた食べ物の種類数を求めてください。

# 制約
#     入力は全て整数である。
#     1≤N,M≤30
#     1≤Ki≤M
#     1≤Aij≤M
#     各 i(1≤i≤N) について Ai1,Ai2,...,AiKiは全て異なる。

# 入力
# 入力は以下の形式で標準入力から与えられる。
# N M
# K1 A11 A12 ... A1K1
# K2 A21 A22 ... A2K2
# :
# KN AN1 AN2 ... ANKN

# 出力
# N人全ての人が好きだと答えた食べ物の種類数を出力せよ。

# 入力例 1
# 3 4
# 2 1 3
# 3 1 2 3
# 2 3 2

# 出力例 1
# 1

# 3人全員が好きだと答えた食べ物は 3 番目の食べ物だけなので 1を出力します。

# 入力例 2
# 5 5
# 4 2 3 4 5
# 4 1 3 4 5
# 4 1 2 4 5
# 4 1 2 3 5
# 4 1 2 3 4

# 出力例 2
# 0

# カツサンドくんの仮説は全く正しくありませんでした。

# 入力例 3
# 1 30
# 3 5 10 30

# 出力例 3
# 3


def calculation(lines):
    # line = lines[0]
    # N = int(lines[0])
    N, M = list(map(int, lines[0].split()))
    # values = list(map(int, lines[1].split()))
    # values = list()
    # for i in range(N):
    #     values.append(int(lines[i+1]))
    valueses = list()
    for i in range(N):
        valueses.append(list(map(int, lines[i+1].split())))

    dic = dict()
    for values in valueses:
        for i in range(1, len(values)):
            value = values[i]
            if value not in dic.keys():
                dic[value] = 1
            else:
                dic[value] += 1

    result = 0
    for key in dic:
        if dic[key] == N:
            result += 1

    return [result]


# 引数を取得
def get_input_lines():
    line = input()
    N, M = list(map(int, line.split()))
    lines = list()
    lines.append(line)
    for _ in range(N):
        lines.append(input())
    return lines


# テストデータ
def get_testdata(pattern):
    if pattern == 1:
        lines_input = ['3 4', '2 1 3', '3 1 2 3', '2 3 2']
        lines_export = [1]
    if pattern == 2:
        lines_input = ['5 5', '4 2 3 4 5', '4 1 3 4 5', '4 1 2 4 5', '4 1 2 3 5', '4 1 2 3 4']
        lines_export = [0]
    if pattern == 3:
        lines_input = ['1 30', '3 5 10 30']
        lines_export = [3]
    return lines_input, lines_export


# 動作モード判別
def get_mode():
    import sys
    args = sys.argv
    if len(args) == 1:
        mode = 0
    else:
        mode = int(args[1])
    return mode


# 主処理
def main():
    import time
    started = time.time()
    mode = get_mode()
    if mode == 0:
        lines_input = get_input_lines()
    else:
        lines_input, lines_export = get_testdata(mode)

    lines_result = calculation(lines_input)

    for line_result in lines_result:
        print(line_result)

    # if mode > 0:
    #     print(f'lines_input=[{lines_input}]')
    #     print(f'lines_export=[{lines_export}]')
    #     print(f'lines_result=[{lines_result}]')
    #     if lines_result == lines_export:
    #         print('OK')
    #     else:
    #         print('NG')
    # finished = time.time()
    # duration = finished - started
    # print(f'duration=[{duration}]')


# 起動処理
if __name__ == '__main__':
    main()


Measured memory_bytes: 9088
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

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

	vector<int> s(n),t(n),x(n);
	rep(i,n)cin>>s[i]>>t[i]>>x[i];
	
	set<pair<int,int>> st;
	rep(i,q){
		int a;cin>>a;
		st.insert({a,i});
	}
	// 最後に残るやつ
	st.insert({inf,-1});

	// 位置的に降順に見ていくように前処理
	vector<int> ord(n);
	iota(ord.begin(),ord.end(),0);
	sort(ord.begin(),ord.end(),[&](int u,int v){
		return x[u]<x[v];
	});

	// 位置的に最初から見ていって、引っかかった人は弾いていく
	// setのerase関数は弾いた場所を返すので、延々と見て行ける
	vector<int> ans(q,-1);
	for(auto i : ord){
		auto itr=st.lower_bound({-x[i]+s[i],-1});

		// 同じ場所で引っかかる人が居なくなるまで処理
		while(itr->first < -x[i]+t[i]){
			// 答えが確定
			ans[itr->second]=x[i];
			// 次の人が格納される
			itr=st.erase(itr);
		}
	}
	for(auto e:ans) cout << e << endl;

	return 0;
}


Measured memory_bytes: 15232
#include <stdio.h>
#include <vector>

struct edge
{
	int v;
	int dist;
};

using namespace std;

int N;
int coloring[100001];
vector<edge> adj[100001];

void dfs(int cur, int parent, int color)
{
	coloring[cur] = color;

	for (auto &next : adj[cur])
	{
		if (next.v == parent) continue;

		if (next.dist & 1) dfs(next.v, cur, 1 - color);
		else dfs(next.v, cur, color);
	}
}

int main()
{
	scanf("%d", &N);
	
	for (int i = 0; i < N-1; ++i)
	{
		int u, v, w;

		scanf("%d %d %d", &u, &v, &w);
		adj[u].push_back({ v, w });
		adj[v].push_back({ u, w });
	}

	dfs(1, 0, 0);

	for (int i = 1; i <= N; ++i) printf("%d\n", coloring[i]);

	return 0;
}

Measured memory_bytes: 9088
MOD = 10 ** 9 + 7
class Integer
  def to_mod
    self % MOD
  end
end
def fact_mod(a); (1 .. a).inject{|s,v| (s * v).to_mod }; end

N, M = gets.split.map(&:to_i).sort

if M - N > 1
  puts 0
elsif N == M
  puts  (2 * fact_mod(N) ** 2).to_mod
else
  puts (fact_mod(N) ** 2 * M).to_mod
end

Measured memory_bytes: 1788
N = int(input())
L = input().split()
n = int(input())
l = input().split()
dup = []
count = 0
for i in range(N):
    for j in range(n):
        if L[i] == l[j]:
            dup.append(L[i])
            break
dup = list(set(dup))
print(len(dup))


Measured memory_bytes: 6068
n=input()
l=len(n)
pre=[0,1]
for i in range(l):
    c=[0,0]
    d=int(n[i])
    c[0]=min(pre[0]+d,pre[1]+10-d)
    c[1]=min(pre[0]+d+1,pre[1]+10-d-1)
    pre=c
print(pre[0])

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

using Int = long long;
const char newl = '\n';

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);}
template<typename T=int>
vector<T> read(size_t n){
  vector<T> ts(n);
  for(size_t i=0;i<n;i++) cin>>ts[i];
  return ts;
}

//INSERT ABOVE HERE
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int n;
  cin>>n;
  auto as=read(3*n);
  for(int &a:as) a--;

  int add=0;
  vector dp(n,vector(n,-n));


  vector mx(n,-n);
  int all=-n;

  using T = tuple<int, int, int>;
  vector<T> qs;
  auto preupd=[&](int x,int y,int v){
    qs.emplace_back(x,y,v);
  };
  auto upd=[&](int x,int y,int v){
    chmax(dp[x][y],v);
    chmax(dp[y][x],v);
    chmax(mx[x],v);
    chmax(mx[y],v);
    chmax(all,v);
  };
  upd(as[0],as[1],0);


  auto same=[&](int a,int b,int c){return a==b and b==c;};
  for(int i=2;i+3<=(int)as.size();i+=3){
    int x=as[i+0];
    int y=as[i+1];
    int z=as[i+2];

    if(same(x,y,z)){
      add++;
      continue;
    }

    for(int k=0;k<n;k++){
      preupd(x,k,dp[y][k]+(y==z));
      preupd(y,k,dp[z][k]+(z==x));
      preupd(z,k,dp[x][k]+(x==y));

      preupd(x,k,mx[k]);
      preupd(y,k,mx[k]);
      preupd(z,k,mx[k]);
    }

    preupd(x,y,all);
    preupd(y,z,all);
    preupd(z,x,all);

    preupd(x,y,dp[z][z]+1);
    preupd(y,z,dp[x][x]+1);
    preupd(z,x,dp[y][y]+1);

    for(auto [a,b,c]:qs) upd(a,b,c);
    qs.clear();
  }

  int ans=0;
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
      chmax(ans,dp[i][j]+same(i,j,as.back()));
  cout<<ans+add<<newl;
  return 0;
}


Measured memory_bytes: 19500
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef pair<int, int> P;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

void YN(bool flg){if(flg) cout << "YES" << endl; else cout << "NO" << endl;}
void Yn(bool flg){if(flg) cout << "Yes" << endl; else cout << "No" << endl;}
void yn(bool flg){if(flg) cout << "yes" << endl; else cout << "no" << endl;}

int f(int x) {
    int cnt = 0;
    while(x % 2 == 0) {
        x /= 2;
        cnt++;
    }
    return cnt;
}

int main() {
    int n;
    cin >> n;
    int b1 = 0, b2 = 0, b4 = 0;
    rep(i, n) {
        int a;
        cin >> a;
        int t = f(a);
        if(t == 0) b1++;
        else if(t == 1) b2++;
        else b4++;
    }
    //cout << b1 << b2 << b4 << endl;

    bool can = false;
    if(b2 == 0) {
        if(b1 <= b4 + 1) can = true;
    } else {
        if(b1 <= b4) can = true;
    }

    Yn(can);

    return 0;
}


Measured memory_bytes: 256
N = int(input())

if 400 <= N <= 599:
    print(8)
if 600 <= N <= 799:
    print(7)
if 800 <= N <= 999:
    print(6)
if 1000 <= N <= 1199:
    print(5)
if 1200 <= N <= 1399:
    print(4)
if 1400 <= N <= 1599:
    print(3)
if 1600 <= N <= 1799:
    print(2)
if 1800 <= N <= 1999:
    print(1)

Measured memory_bytes: 9160
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
                
#define speedio ios_base::sync_with_stdio(false); cin.tie(NULL);
#define pretime float(clock()-clk)/CLOCKS_PER_SEC
#define max2(a,b) ((a)>(b) ? (a) : (b))   
#define min2(a,b) ((a)<(b) ? (a) : (b)) 
#define rep(i,a,b) for(i=a;i<=b;++i)
#define rev(i,a,b) for(i=a;i>=b;--i) 
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define lli long long int 
#define ins insert
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define PI 3.14159265
#define mod 1000000007
#define inf 1000000000000000

using namespace std;
typedef vector<lli>   vll;
typedef vector<int>   vi;
typedef set<lli>      sll;
typedef set<int>      si;
typedef pair<lli,lli> pll;
typedef pair<int,int> pii;
clock_t clk=clock();       

lli i,j;
void solve(void);

int main()
{
  speedio;
   int t=1;  
  // cin>>t;
   while(t--)
     solve();

  return 0;
}
//
void solve()
{
	lli r,d,x; cin>>r>>d>>x; lli prev=x;
	rep(i,1,10)
    {
    	cout<<r*prev-d<<"\n";
    	prev=r*prev-d;
    }
}

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

typedef long long ll;
const ll MOD = 1000000007;

using namespace std;

string K;
int D, sz;
int dp[10005][105][2];

// index in the string, sum so far % D, rest=1 for restricted digit usage
int solve(int ind, int s, int rest) {
    //base case
    if (ind == sz) {
        if (s == 0)
            return 1;
        else
            return 0;
    } else if (dp[ind][s][rest] != -1)
        return dp[ind][s][rest];

    ll ans = 0;
    int md = 9;
    if (rest == 1) md = K[ind] - '0';
    for (int i = 0; i < md; i++) {
        ans = (ans + solve(ind + 1, (s + i) % D, 0)) % MOD;
    }
    if (rest == 0) {
        ans = (ans + solve(ind + 1, (s + 9) % D, 0)) % MOD;
    } else {
        ans = (ans + solve(ind + 1, (s + md) % D, 1)) % MOD;
    }
    dp[ind][s][rest] = (int)ans;
    return (int)ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> K;
    cin >> D;
    sz = K.length();

    // init dp
    for (int i = 0; i < 10005; i++) {
        for (int j = 0; j < 105; j++) {
            for (int k = 0; k < 2; k++) {
                dp[i][j][k] = -1;
            }
        }
    }

    int ans = solve(0, 0, 1);

    cout << ((ll)ans + MOD - 1) % MOD; // remove the number 0

    return 0;
}

Measured memory_bytes: 9344
#%%
N, M = map(int, input().split())

a = [0] * M
b = [0] * M
c = [[] for _ in range(M)]
for i in range(M):
    a[i], b[i] = map(int, input().split())
    c[i] = list(map(int, input().split()))

inf = float('inf') 
cost = [inf] * (2**N)
cost[0] = 0

movement = []
for i in range(M):
    move = 0
    for j in range(len(c[i])):
        move += 2 ** (c[i][j]-1)
    movement.append(move)

for i in range(2**N):
    for j in range(M):
        move2 = movement[j] 
        if cost[i|move2] > cost[i]+a[j]:
            cost[i|move2] = cost[i]+a[j]

if cost[2**N-1] == inf:
    print(-1)
else:
    print(cost[2**N-1])

Measured memory_bytes: 3388
#include<iostream>
using namespace std;
int x[200000], n, a, b, c, d, p, rell, y[200000];
int main() {
	while (true) {
		cin >> n >> a >> b >> c >> p; if (!n) { break; }
		x[0] = p; rell = 0;
		for (int i = 1; i < 200000; i++) { x[i] = (x[i - 1] * a + b) % c; }
		for (int i = 0; i < n; i++) { cin >> y[i]; }
		for (int i = 0; i < 10001; i++) {
			if (y[rell] == x[i]) { rell++; }
			if (rell == n) { d = i; goto E; }
		}
		d = -1;
	E:;
		cout << d << endl;
	}
}

Measured memory_bytes: 1944
/* ****GT_18**** */

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
#define ll          long long
#define pb          push_back
#define	endl		'\n'
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define INF			1000000000000000
#define rep(i,a,b)	for(ll int i=a;i<b;i++)
#define repr(i,a,b) for(ll int i=a;i>=b;i--)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 

using namespace std;
using namespace __gnu_pbds;

#define N  1000005

ll dp[N][4];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int TESTS=1;
//	cin>>TESTS;
	while(TESTS--)
	{
		ll n;
		cin>>n;
		dp[0][0]=8;
		dp[0][1]=1;
		dp[0][2]=1;
		dp[0][3]=0;
		rep(i,1,n){
			dp[i][0]=(dp[i-1][0]*8)%hell;
			dp[i][1]=(dp[i-1][0]*1 + (dp[i-1][1]*9)%hell)%hell;
			dp[i][2]=(dp[i-1][0]*1 + (dp[i-1][2]*9)%hell)%hell;
			dp[i][3]=(dp[i-1][1]*1 + dp[i-1][2]*1 + (dp[i-1][3]*10)%hell)%hell;
		}
		cout<<dp[n-1][3]<<endl;
	}
	return 0;
}

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

#define MAX 100

int main() {
  int h, w;
  char buf;
  int i, j;
  
  cin >> h >> w;
  
  for (i = 0; i < (h + 2); i++) {
    cout << '#';
    for (j = 0; j < w; j++) {
      if ((i != 0) && (i != (h + 1))) {
        cin >> buf;
        cout << buf;
      } else {
        cout << '#';
      }
    }
    cout << '#' << endl;
  }
}

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

typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pl;

const int INT_INF = 2147483646;
const ll LL_INF = 9223372036854775807;
const double PI=3.1415926535897932;

bool SecondCompare(const pair<int,int> &a,const pair<int,int> &b)
{
       return a.second<b.second;
}
 
bool SecondCompareDes(const pair<int,int> &a,const pair<int,int> &b)
{
       return a.second>b.second;
}

ll minll(ll a, ll b){
    if(a >= b)  return b;
    else    return a;
}

ll maxll(ll a, ll b){
    if(a >= b)  return a;
    else    return b;
}

ll n;

int main(){
    cin >> n;
    if(n % 2 == 0)  cout << n << endl;
    else
    {
        cout << n*2LL << endl;
    }
    
}

Measured memory_bytes: 256
n,l = map(int,input().split())
pai = []
for i in range(1,n+1):
    pai.append(l+i-1)
#print(pai)
if 0 in pai:
    print(sum(pai))
else:
    if min(pai)>0:
        print(sum(pai)-min(pai))
    else:
        print(sum(pai)-max(pai))

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

int n, m, q;
int ans = 0;
vector<vector<int>> a;
vector<int> p;

void solve(int depth) {
    if (depth == n) {
        int cnt = 0;
        for (int i = 0; i < q; ++i) {
            if (p[a[i][1]] - p[a[i][0]] == a[i][2]) {
                cnt += a[i][3];
            }
        }
        ans = max(ans, cnt);
    }
    else if (depth == 0) {
        for (int i = 1; i < m + 1; ++i) {
            p[0] = i;
            solve(depth + 1);
        }
    } else {
        for (int i = p[depth - 1]; i < m + 1; ++i) {
            p[depth] = i;
            solve(depth + 1);
        }
    }
}

int main() {
    cin >> n >> m >> q;
    a.assign(q, vector<int>(4));
    for (int i = 0; i < q; ++i) {
        for (int j = 0; j < 4; ++j) {
            cin >> a[i][j];
        }
        --a[i][0];
        --a[i][1];
    }
    p.assign(n, 0);
    solve(0);
    cout << ans << endl;
}


Measured memory_bytes: 3612
n = int(input())
A = list(map(int, input().split()))

ans = 0
for i in range(len(A)):
    if i == len(A)-1:
        break
    else:
        front = A[i]
        behind = A[i+1]
        if front <= behind:
            pass
        else:
            ans += (front - behind)
            A[i+1] = front

print(ans)

Measured memory_bytes: 32224
#![allow(unused_macros)]
#![allow(dead_code)]
#![allow(unused_imports)]

use itertools::Itertools;
use text_io::*;

const U_INF: usize = 1 << 60;
const I_INF: isize = 1 << 60;

fn main() {
    let d: usize = read!();
    let mut n: usize = read!();

    let m = 100usize.pow(d as u32);
    if n == 100 {
        n = 101
    };
    println!("{}", m * n);
}


Measured memory_bytes: 2136
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")

using namespace std;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
typedef long long ll;
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REP(i,num,n) for(int i=num, i##_len=(n); i<i##_len; ++i)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
#define print(x) (cout << (x) << endl)
#define pb push_back
#define mp make_pair
#define sz(x) int(x.size())
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
#define fs first
#define sc second
// 多倍長
#include <boost/rational.hpp>
#include <boost/multiprecision/cpp_int.hpp>
using boost::rational;
using boost::multiprecision::cpp_int;

const int INF = 1e9;
const ll LLINF = 1e16;
const ll MOD = 1e9+7;
template<class T> inline void add(T &a, T b){a = ((a+b) % MOD + MOD) % MOD;};

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}
 
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
 

// 指定した文字cが文字列に何文字入ってるか
ll stringcount(string s, char c) {
    return count(s.cbegin(), s.cend(), c);
}


// 割り算の切り上げ処理
template<typename T>
T rp(T a, T b) {
  return (a + b - 1) / b;
}

// 桁和
template<typename T>
T digsum(T n) {
    T res = 0;
    while(n > 0) {
        res += n%10;
        n /= 10;
    }
    return res;
}

// 回文判定
bool kai (string s) {
    string t{s};
    reverse(begin(t), end(t));
    return s == t;
}

using pint = pair<int, int>;
using pll = pair<ll, ll>;

ll syu[101000];
int main(void)
{
    cout.tie(0);
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    ll n;
    cin >> n;
    vector<ll> a(n);
    ll sum = 0;
    rep(i, n) {
        cin >> a[i];
        syu[a[i]]++;
        sum += a[i];
    }
    ll q;
    cin >> q;
    rep(i, q){
        ll b,c;
        cin >> b >> c;
        sum -= b * syu[b];
        sum += c * syu[b];
        syu[c] += syu[b];
        syu[b] = 0;
        print(sum);
    }
    




}





Measured memory_bytes: 4980
#include<bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define int long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;

const int N = 1e5+6;
int n, a[N], b[N];
map <int, int> joy;

signed main(){
	cin >> n;
	for (int i=1; i<=n; i++){
		int u; cin >> u;
		for (int j=2; j*j*j<=u; j++){
			while (u%(j*j*j) == 0){
				u /= (j*j*j);
			}
		}
		a[i] = u; joy[u]++;
		int y = 1;
		for (int j=2; j*j*j<=u; j++){
			if (u%j == 0){
				y *= j;
				if (u%(j*j) != 0) y *= j;
				while (u%j == 0) u /= j;
			}
		}
		int u1 = sqrt(u);
		if (u1*u1 == u) y *= u1;
		else y *= u*u;
		b[i] = y;
	}
	int res = 0;
	if (joy[1]){
		res++;
		joy[1] = 0;
	}
	for (int i=1; i<=n; i++){
		res += max(joy[a[i]], joy[b[i]]);
		joy[a[i]] = 0; joy[b[i]] = 0;
	}
	cout << res;
}



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

#define ll long long
#define ull unsigned long long 
#define endl '\n'
#define pii pair<int, int>
#define all(a) a.begin(),a.end()
template <typename T>
inline T gcd(T a, T b) { while (b != 0) swap(b, a %= b); return a; }

int main(){
    ll n, m;
    cin >> n >> m;
    if(2*n <= m){
        m -= 2*n;
        cout << n + m/4;
    }
    else{
        cout << m/2;
    }
}



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

using ull = unsigned long long;

int main() {

    int n;
    int q;

    cin >> n;

    vector<ull> v(n);
    ull sum = 0;

    map<ull, ull> x;


    for(int i = 0; i < n; ++i) {
        ull num;
        cin >> num;

        if(x.find(num) == x.end())
            x[num] = 1;
        else
            x[num]++;
        
        sum += num;

    }


    cin >> q;

    for(int i = 0; i < q; ++i) {
        ull a, b;

        cin >> a >> b;
        
        if(x.find(a) != x.end()) {

            sum -= x[a] * a;
            sum += x[a] * b;

            if(x.find(b) == x.end())
                x[b] = x[a];
            else
                x[b] += x[a];

            x.erase(a);

        }

        cout << sum << endl;

    }



    return 0;

}

Measured memory_bytes: 8012
#include<bits/stdc++.h>
using namespace std;
typedef  long long ll;
using vll=vector<ll>;
using vi=vector<int>;

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}

//pow(llpow,modpow)
template<class T> ll llpow(ll x,T n){ll ans=1;if(x==0)ans=0;while(n){if(n&1)ans*=x;x*=x;n>>=1;}return ans;}
long long modpow(long long a, long long n, long long mod) {long long res = 1;while (n > 0) {if (n & 1) res = res * a % mod;a = a * a % mod;n >>= 1;}return res;}
//最大公約数
template<class T> inline T gcd(T x,T y){if(y==0)return x; else {return gcd(y,x%y);}}
//最小公倍数
template<class T> inline T lcm(T x,T y){return x/gcd(x,y)*y;}
//逆元
long long modinv(long long a, long long m) {long long b = m, u = 1, v = 0;while (b) {long long t = a / b;a -= t * b; swap(a, b);u -= t * v; swap(u, v);}u %= m;if (u < 0) u += m;return u;}

#define rep(i, begin_i, end_i) for (ll i = (ll)begin_i; i < (ll)end_i; i++)

int INF = 1<<30;

using pii=pair<int,int>;

int main( ){
    int n,x,y;
    cin>>n>>x>>y;
    vector<int> conne[n];
    x--;y--;
    rep(i,0,n-1){
        conne[i].push_back(i+1);
        conne[i+1].push_back(i);
    }
    conne[x].push_back(y);
    conne[y].push_back(x);
    vll ans(n,0);

    rep(start,0,n){
        vector<int> res(n,INF);
        queue<pair<int,int> > q;
        q.emplace(start,0);
        while(!q.empty()){
            pii t=q.front();q.pop();
            chmin(res[t.first],t.second);

            for(int e : conne[t.first]){
                if(res[e]>t.second+1){
                    q.emplace(e,t.second+1);
                }
            }
        }
        rep(c,start+1,n){
            int t=res[c]-1;
            ans[t]++;
        }
    }
    rep(i,0,n-1){
        cout<<ans[i]<<endl;
    }
    return 0;
}




Measured memory_bytes: 384
while True:
    N,M=map(int,raw_input().split())
    if N==M==0:break
    r=input()
    L=[[False]*1261 for i in range(10001)]
    P=[[] for i in range(10001)]
    for i in range(r):
        t,n,m,s=map(int,raw_input().split())
        if s:
            P[m].append(t)
        else:
            temp=P[m].pop()
            for j in range(temp,t):
		L[m][j]=True
    q=input()
    for	i in range(q):
        ts,te,m=map(int,raw_input().split())
	cnt=0
	for j in range(ts,te):
            if L[m][j]:
		cnt+=1
        print cnt

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


using namespace std;
#define rep(i,n) for (int i = 0; i < (int)(n); ++i)
#define reps(i,n) for (int i = 1; i <= (int)(n); ++i)
#define repd(i,n) for (int i = (int)(n - 1); i >= 0; --i)
#define repds(i,n) for (int i = (int)(n); i > 0; --i)
#define loop(i,x,n) for (int i = (int)(x); i < (n); ++i)
#define loops(i,x,n) for (int i = (int)(x); i <= (n); ++i)
#define loopd(i,x,n) for (int i = (int)(x); i > (n); --i)
#define loopds(i,x,n) for (int i = (int)(x); i >= (n); --i)
#define itrep(i,s) for (auto i = begin(s); i != end(s); ++i)
#define itrepd(i,s) for (auto i = --end(s); i != begin(s); --i)
#define all(f,x,...) [&](decltype(x)& whole) { return (f)(begin(whole), end(whole), ##__VA_ARGS__); }(x)
#define rall(f,x,...) [&](decltype(x)& whole) { return (f)(rbegin(whole), rend(whole), ##__VA_ARGS__); }(x)
using ll = long long;
using ld = long double;
constexpr ll inf = static_cast<ll>(1e17);
constexpr int iinf = static_cast<int>(1e9);
constexpr double dinf = 1e10;
constexpr ld ldinf = 1e17;
ll mod = static_cast<ll>(1e9 + 7);
std::ostream& endn(std::ostream& os) { return os.put(os.widen('\n')); }
template<class T> constexpr int sz(const T& a) { return (int)a.size(); }
template<class T> constexpr T pow2(const T a) { return a * a; }
template<class T, class ... Args> constexpr T mins(T& a, Args... args) { return a = min<T>({ a, args... }); }
template<class T, class... Args> constexpr T maxs(T& a, Args... args) { return a = max<T>({ a,args... }); }
template<typename A, size_t N, typename T>
void fillArray(A(&array)[N], const T& val) { std::fill((T*)array, (T*)(array + N), val); }

class UnionFind {
public:
    UnionFind() :data(0) {}
    UnionFind(int size) : data(size, -1) { }
    void resize(int size) { *this = { size }; }
    bool unionset(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 findset(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)]; }
private:
    std::vector<int> data;
};


int n, m, k;
int a[100005], b[100005], c[100005], d[100005];
int s[100005], t[100005];
void solve() {
    cin >> n >> m >> k;
    rep(i, m) cin >> a[i] >> b[i];
    rep(i, k) cin >> c[i] >> d[i];

    UnionFind uf(n);
    rep(i, m) uf.unionset(a[i] - 1, b[i] - 1);
    rep(i, m) {
        if (uf.findset(a[i] - 1, b[i] - 1)) {
            ++s[a[i] - 1]; ++s[b[i] - 1];
        }
    }
    rep(i, k) {
        if (uf.findset(c[i] - 1, d[i] - 1)) {
            ++t[c[i] - 1]; ++t[d[i] - 1];
        }
    }

    rep(i, n) cout << max(0, uf.size(i) - 1 - s[i] - t[i]) << " ";
    cout << endn;

}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
    cout << flush;
    return 0;
}


Measured memory_bytes: 3584
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;

#define repr(i, n) for(int i = n; i >= 0; i--)
#define reprl(i, n) for(ll i = n; i >= 0; i--)
#define all(v) v.begin(), v.end()
ll gcd(ll a,ll b) {
  return b? gcd(b,a%b): a;  
}
ll lcm(ll a,ll b) {
  return a*b/gcd(a,b);
}
bool isLowerCase(char c){
  return (c>='a'&&c<='z');
}
const string outputYesNo(bool ans){
  return (ans?"Yes":"No");
}
const ll mod=1000000007;
int main() {
  int n,m;cin>>n>>m;
  vector<int> a(n);
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  sort(all(a));
  multimap<int,int> bc;
  for(int i=0;i<m;i++){
    int b,c;cin>>b>>c;
    bc.insert(pair<int,int>(c,b));
  }
  vector<int> d(n);
  int idx=0;
  for(auto it=bc.rbegin();it!=bc.rend();++it){
    for(int i=0;i<it->second;i++){
      d[idx++]=it->first;
      if(idx>=n){
        break;
      }
    }
    if(idx>=n){
      break;
    }
  }
  sort(all(d),greater<int>());
  ll sum=0;
  for(int i=0;i<n;i++){
    sum+=max(a[i],d[i]);
  }
  cout<<sum<<endl;
  return 0;
}

Measured memory_bytes: 5760
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll P=1e9+7,V=(P+1)>>1;
const int N=3005;
int n,q,a[N]; ll f[N][N],g[N][N],ans,s=1;
int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	cin>>n>>q;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){
		f[i][j]=(a[i]<a[j]); g[i][j]=(a[i]>a[j]);
	}
	while(q--){
		int x,y; scanf("%d%d",&x,&y);
		f[x][y]=f[y][x]=(f[x][y]+f[y][x])*V%P;
		g[x][y]=g[y][x]=(g[x][y]+g[y][x])*V%P;
		for(int i=1;i<=n;i++) if(i!=x && i!=y){
			f[x][i]=f[y][i]=(f[x][i]+f[y][i])*V%P;
			g[x][i]=g[y][i]=(g[x][i]+g[y][i])*V%P;
			f[i][x]=f[i][y]=(f[i][x]+f[i][y])*V%P;
			g[i][x]=g[i][y]=(g[i][x]+g[i][y])*V%P;
		}
		(s*=2)%=P;
	}
	for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) (ans+=g[i][j])%=P;
	cout<<ans*s%P<<endl;
	return 0;
}


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

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

const long long INF = 1LL<<60;

int main(){
    int H, N; // Hが敵のHPで、Nが魔法の種類
    cin >> H >> N;
    vector<int> A(N), B(N); // Aが攻撃、Bが消費するMP
    for (int i=0; i<N; i++){
        cin >> A[i] >> B[i];
    }

    vector<vector<long long> > dp(N+1, vector<long long>(H+1, INF)); //二重配列dpは、pythonでいうところのリストが多重になっている構造で、そのn行目アドレスにおいて、H+1列分のvectorを持っているはず。
    dp[0][0] = 0;

    for (int h=0; h<=H; h++){
        for (int n=0; n<N; n++){
            dp[n+1][h] = min(dp[n][h], dp[n+1][max(0, h-A[n])] + B[n]);
        }
    }
    cout << dp[N][H] << endl;
}


Measured memory_bytes: 78592
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    d = collections.defaultdict(list)
    def kf(e):
        na = []
        for i in range(3):
            na.append(sorted([(e[j]-e[i])%60 for j in range(3)]))
        return tuple(min(na))

    for h in range(24):
        for m in range(60):
            for s in range(60):
                a = h * 5 + m // 12
                k = kf([a,m,s])
                d[k].append((h*3600+m*60+s))

    def to_time(i):
        h = i // 3600
        m = i // 60 % 60
        s = i % 60
        return '{:02d}:{:02d}:{:02d}'.format(h,m,s)

    def f(n):
        a = [LI() for _ in range(n)]
        cs = [d[kf(a[i])] + [inf] for i in range(n)]
        mr = inf
        mi = -1
        for i in range(60*60*24):
            t = i
            for j in range(n):
                c = cs[j][bisect.bisect_left(cs[j], i)]
                if t < c:
                    t = c
            tr = t - i
            if mr > tr:
                mr = tr
                mi = i
        return '{} {}'.format(to_time(mi), to_time(mi+mr))

    while 1:
        n = I()
        if n == 0:
            break
        rr.append(f(n))

    return '\n'.join(map(str, rr))


print(main())



Measured memory_bytes: 12480