akhauriyash/Code-Regression huggingface dataset:
import java.util.Arrays;
import java.util.Scanner;

public class Main
{
	static final Scanner s = new Scanner(System.in);

	public static void main(String... args)
	{
		int num = Integer.parseInt(s.nextLine());
		for(int i = 0; i < num; i++)
		{
			char[] arr = s.nextLine().toCharArray();
			Arrays.sort(arr);
			int min = Integer.parseInt(new String(arr));
			reverse(arr);
			int max = Integer.parseInt(new String(arr));
			System.out.println(max - min);
		}
	}
	
	static void reverse(char[] arr)
	{
		int l = arr.length;
		for(int i = 0; i < arr.length / 2; i++)
		{
			char tmp = arr[i];
			arr[i] = arr[l - i - 1];
			arr[l - i - 1] = tmp;
		}
	}
}

Measured memory_bytes: 17136
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<n; i++)
#define PI 3.14159265359
#define INF 1000100100000000000
#define MOD 1000000007
#define all(x) (x).begin(),(x).end()
typedef long long ll;
#define P pair<int, int>
#define PP pair<P,P>
#define T tuple<int,int,int> 
using namespace std;

int main(){
  int n,m,Q; cin >> n >> m >> Q;
  vector<vector<int> > train(n,vector<int>(n+1,0));
  rep(i,m){
      int L,R; cin >> L >> R;
      L--;
      train[L][R]++;
  }

  rep(i,n)rep(j,n){
      train[i][j+1]+=train[i][j];
  }
 
  vector<int> ans(Q,0);

  rep(i,Q){
    int p,q; cin >> p >> q;
    p--;
    for(int j=p; j<q; j++){
        ans[i]+=train[j][q]-train[j][0];
    }
  }

  rep(i,Q) cout << ans[i] << endl;
return 0;
}

Measured memory_bytes: 4600
#include "bits/stdc++.h"
#define Rep(i,n) for(int i=0;i<(int)(n);i++)
#define For(i,n1,n2) for(int i=(int)(n1);i<(int)(n2);i++)
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define RREP(i,n) for(ll i=((ll)(n)-1);i>=0;i--)
#define FOR(i,n1,n2) for(ll i=(ll)(n1);i<(ll)(n2);i++)
#define RFOR(i,n1,n2) for(ll i=((ll)(n1)-1);i>=(ll)(n2);i--)
#define all(a)  (a).begin(),(a).end()
#define IOS std::cin.tie(0),std::ios::sync_with_stdio(false)

namespace idaten {

	using namespace std;
	using ll = int_fast64_t;
	using ull = uint_fast64_t;
	using P = std::pair<int64_t, int64_t>;
	template<typename T1, typename T2> inline bool chmin(T1& a, T2 b) { if (a > b) { a = b; return 1; }return 0; }
	template<typename T1, typename T2> inline bool chmax(T1& a, T2 b) { if (a < b) { a = b; return 1; }return 0; }
	template<class Type>struct is_vector : std::false_type {};
	template<class ValueType, class Alloc>struct is_vector<std::vector<ValueType, Alloc>> : std::true_type {};
	template <typename T> inline std::ostream& operator << (std::ostream& out, const std::vector<T>& v) {
		if (v.empty())return out;
		constexpr bool is_vector_v = is_vector<T>::value;
		if (is_vector_v)for (auto itr = v.begin(); itr != v.end();)out << (*itr), out << ((++itr != v.end()) ? "\n" : "");
		else for (auto itr = v.begin(); itr != v.end();)out << (*itr), out << ((++itr != v.end()) ? " " : "");
		return out;
	}
	inline void put() {}
	template<class T> inline void put(const T& first) { std::cout << first << "\n"; }
	template<class T, class... N> inline void put(const T& first, const N& ... rest) { std::cout << first << " "; put(rest...); }
	inline void putn() {}
	template<class T, class... N> inline void putn(const T& first, const N& ... rest) { std::cout << first << "\n"; putn(rest...); }

	void solve() {
		IOS;
		int n;
		string s;
		cin >> s;
		n = s.size();
		//reverse(all(s));
		vector<int> d(n + 1, 0);
		d[0] = 1;
		REP(i, n) {
			d[i + 1] = d[i] * 10;
			d[i + 1] %= 2019;
		}
		vector<ll> a(n + 1, 0);
		reverse(all(s));
		REP(i, n) {
			a[i + 1] = a[i] + d[i] * (s[i] - '0');
			a[i + 1] %= 2019;
		}
		ll res = 0;
		vector<ll> cnt(2019, 0);
		REP(i, n + 1) {
			cnt[a[i]]++;
		}
		REP(i, 2019) {
			res += cnt[i] * (cnt[i] - 1) / 2;
		}
		put(res);
	}
} // namespace idaten

int main() {
	idaten::solve();
	return 0;
}


Measured memory_bytes: 5928
#include<bits/stdc++.h>
#include <math.h>// isupper, islower, isdigit, toupper, tolower
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define Rep(i,s,n) for(int i=s;i<n;i++)
#define fi first
#define se second
#define all(c) c.begin(),c.end()
typedef long long int ll;
typedef pair<int, int> P;
typedef long double ld;
void Ans(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}

const ll INF=1001001001;
const ll mod=1000000007;

#define PI 3.14159265359

int main(){
  ld a,b,h,m;
  cin>>a>>b>>h>>m;
  ld n;
  n=a*a+b*b-2.0*a*b*cos((h/6.0+m/360-m/30.0)*PI);
  
  cout<<fixed<<setprecision(10);

  cout<<sqrt(n)<<endl;
}

Measured memory_bytes: 4172
N=int(input())
num=1
factors=[]
for i in range(N,1,-1):
    num*=i

r=2
while num!=1:
    x=0
    while num%r==0:
        num//=r
        x+=1
    if x:
        factors.append(x)
    r+=1

result=1
for i in factors:
    result*=i+1

print(result%1000000007)

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

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

const ll MOD = 1e9 + 7;
const ll inf = 1LL<<60;
const double eps = 1e-9;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
 
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; }

ll PowMod_RepeatSquaring(ll N, ll P, ll M) {
    if (P == 0) return 1;
    if (P%2 == 0) {
        ll t = PowMod_RepeatSquaring(N, P/2, M);
        return t*t % M;
    }
    return N * PowMod_RepeatSquaring(N, P-1, M);
}

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

ll combination(ll a, ll b) {
    if ((a == b) || (b == 0)) {
        return 1;
    }
    if (a < b) return 0;
    ll ret = 1;
    for (ll i = 0; i < b; i++) {
        ret *= (a - i);
        ret %= MOD;
        ret *= modpow(i + 1, MOD - 2);
        ret %= MOD;
    }
    return ret;
}


int main()
{
    ll n, a, b;
    cin >> n >> a >> b;

    ll ans = modpow(2, n) - 1;
    ans -= combination(n, a);
    ans -= combination(n, b);
    ans += MOD + MOD;
    ans %= MOD;
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h> 
#include<cmath>
#include<string>
#define pb push_back
#define x first
#define y second
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define all(x) x.begin(),x.end()
#define int long long
using namespace std;
 
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
//void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
 
// look for  all edge cases
//search for a pattern

const int mod = 1e9 + 7;
vector<int> pow10 , pow8;
vector<int> fac;

int power(int x, int y)  
{  
    int res = 1;     // Initialize result  
  
    x = x % mod; // Update x if it is more than or  
                // equal to p 
   
    if (x == 0) return 0; // In case x is divisible by p; 
  
    while (y > 0)  
    {  
        // If y is odd, multiply x with result  
        if (y & 1)  
            res = (res*x) % mod;  
  
        // y must be even now  
        y = y>>1; // y = y/2  
        x = (x*x) % mod;  
    }  
    return res;  
}  

signed main() {    
	ios::sync_with_stdio(0);
	cout.tie(0);
	cin.tie(0);
		
	int n;
	cin >> n;
	
	//debug(power(2 , 10));
	
	pow10.resize(n+1 , 0);
	pow8.resize(n+1 , 0);
	fac.resize(n+1, 0);
	
	fac[0] = 1;
	fac[1] = 1;
	pow10[0] = 1;
	pow10[1] = 10;
	pow8[0] = 1;
	pow8[1] = 8;
	
	for(int i = 2 ; i <= n ; i++){
		pow10[i] = (pow10[i-1]*10)%mod;
		pow8[i] = (pow8[i-1]*8)%mod;
		fac[i] = (fac[i-1]*i)%mod;
	}
	
	int ans = pow10[n];
	//debug(ans);
	int val = 0;
	for(int i =1 ; i <= n; i++){
		
		int temp =  (fac[n-i]*fac[i])%mod;
		temp = power(temp , mod-2);
		//debug(temp);
		temp = (fac[n]*temp)%mod;
		temp = (temp*pow8[n-i])%mod;
		//debug(temp , fac[n-i] ,pow8[n-i]);
		val = (val + temp)%mod;
	}
	//debug(val);
	val = (val * 2)%mod;
	val = (val  + mod)%mod;
	val = (val + pow8[n])%mod;
	ans = (ans - val + mod)%mod;
	cout<<ans;
	
	 
	return 0;
}


Measured memory_bytes: 26568
import java.io.*;
// import java.math.*;
// import java.util.*;
// import java.util.Map.*;
// import java.util.stream.*;

public class Main {
    public static void main (String[] args) throws Exception {
        BufferedReader reader =
            new BufferedReader (new InputStreamReader (System.in));
        int N = Integer.parseInt (reader.readLine());
        System.out.println (String.format ("%.0f", Math.pow (N, 3)));
        return;
    }
}

Measured memory_bytes: 34640
// AUTHOR: ROSHAN SRIVASTAVA
// WEBSITE: https://www.youtube.com/channel/UC6uQdd7kLLOdlHSVklhV7Cw

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007

int n; 

int main(){

#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    cin >> n;
    if(n >= 30) cout<<"Yes\n";
    else cout<<"No\n";
    return 0;
}

Measured memory_bytes: 3632
//g++ -std=gnu++14 a.cpp
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <iostream>
#include <istream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <tuple>
#include <iomanip>
#include <random>
#include <math.h>

using namespace std;

#define ll long long
#define rep(i, n) for(ll i = 0; i < (n); i++)
ll MOD = 1e9 + 7;
int INF = 1 << 30;
ll INFL = 1LL << 60;

int main(){
  string s,t;
  cin >> s >> t;
  vector<vector<ll>> dp(3010,vector<ll>(3010,0));
  vector<vector<ll>> pre(3010,vector<ll>(3010,0));
  //rep(i,3010)rep(j,3010)dp[i][j] = 0;
  rep(i,s.size()){
    rep(j,t.size()){
      if(s.at(i) == t.at(j)){
        dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j]+1);
        pre[i+1][j+1] = 1;
      }else if(dp[i+1][j] >= dp[i][j+1]){
        dp[i+1][j+1] = max(dp[i+1][j+1],dp[i+1][j]);
        pre[i+1][j+1] = 3;
      }else{
        dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j+1]);
        pre[i+1][j+1] = 2;
      }
    }
  }
  /*
  rep(i,s.size()+1){
    rep(j,t.size()+1){
      cout << dp[i][j] << " ";
    }
    cout << endl;
  }
  rep(i,s.size()+1){
    rep(j,t.size()+1){
      cout << pre[i][j] << " ";
    }
    cout << endl;
  }
  */
  string ans = "";
  int i = s.size();
  int j = t.size();
  while(i > 0 && j > 0){
    if(pre[i][j] == 1){
      ans += s.at(i-1);
      i--;
      j--;
    }else if(pre[i][j] == 2){
      i--;
    }else{
      j--;
    }
  }
  //cout << dp[s.size()][t.size()] << endl;
  reverse(ans.begin(),ans.end());
  cout << ans << endl;


}


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

using ll = long long;
using pii = pair<int, int>;

#define vt          vector
#define sz(x)       (int)(x).size()
#define all(x)      (x).begin(), (x).end()
#define rall(x)     (x).rbegin(), (x).rend()
#define fi          first
#define se          second

void solve(int tc) {
    int n;
    cin >> n;
    vt<int> a(n);
    for (int& i : a) cin >> i;
    
    int cur = a[0];
    ll sum = 0;
    for (int i = 1; i < n; i++) {
        if (cur > a[i]) sum += cur - a[i];
        cur = max(cur, a[i]);
    }

    cout << sum;
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);

    int tcs = 1;
    for (int tc = 1; tc <= tcs; tc++) solve(tc);
}


Measured memory_bytes: 3968
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int x;
    int y;
    cin >> x;
    cin >> y;
    if (y<x*2||y>x*4||y%2==1){
        cout << "No";
    }
    else {
        cout << "Yes";
    }
}


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

using namespace std;

#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define per(i, a, b) for (auto i = (b) - 1; i >= (a); --i)
#define trav(x, v) for (auto &x : v)

#define sz(x) int((x).size())
#define eb(x...) emplace_back(x)
#define ff first
#define ss second

using ll = int64_t;

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

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

	int n; cin >> n;
	int a[n]; rep(i, 0, n) cin >> a[i];
	ll f[n][n];
	per(l, 0, n) {
		f[l][l] = 0;
		rep(r, l + 1, n) {
			f[l][r] = f[l + 1][r];
			rep(m, l + 1, r) ckmin(f[l][r], f[l][m] + f[m + 1][r]);
			rep(i, l, r + 1) f[l][r] += a[i];
		}
	}
	cout << f[0][n - 1];
}

Measured memory_bytes: 1536
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
int main(int argc, char const *argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(0);
    int n,cnt=0;
    cin>>n;
    for(int i=1;i<=n;i++) {
        int x; cin>>x;
        if(x%2 and i%2) cnt++;
    }
    cout<<cnt<<endl;
}

Measured memory_bytes: 3568
#include<bits/stdc++.h>
using namespace std;
int main()
{
   int a,b,c;
   while(cin>>a>>b>>c)
   {
       int sum=0;
       sum=b*10+c;
      // cout<<"sum="<<sum<<endl;
       sum=a*100+sum;
      // cout<<sum<<endl;
       if(sum%4==0)
       {
           cout<<"YES"<<endl;
       }
       else
       {
           cout<<"NO"<<endl;
       }

   }


   return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i < (n); i++)
#define RREP(i, s, n) for (int i = s; i < (n); i++)
#define ALL(a) a.begin(), a.end()
#define RALL(a) a.rbegin(), a.rend()
using namespace std;
using ll = long long;
typedef pair<int, int> pint;
typedef pair<ll, ll> pll;
const ll MOD = 1000000007;
const ll INF = MOD * MOD;
const int inf = (1<<29);

int main() {

    set<int> st;
    for(int i = 0; i < 3; i++) {
        int t;
        cin >> t;
        st.insert(t);
    }

    cout << st.size() << endl;

    return 0;
}

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

vector<int> G[100010];

int f(int v) {
	int ret = 0;
	map<int, int> cnt;
	for(auto c : G[v]) {
		int res = f(c);
		cnt[res]++;
	}

	for(auto x : cnt) {
		if(ret < x.first) ret = x.first;
		ret += x.second;
	}
	return ret;

}

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

	int N;
	cin >> N;
	for(int i = 2; i <= N; i++) {
		int a;
		cin >> a;
		G[a].push_back(i);
	}

	cout << f(1) << endl;
}

Measured memory_bytes: 18176
var arr=readLine()!
var ba:[Bool] = arr.characters.map { if(String($0) == "0") { return false } else { return true }  }

var prev = ba[0]
var j: Int = 0
var c: Int = 0

for j = 1; j < ba.count; j+=1 {
  if( prev == ba[j] ) {
    ba[j] = !ba[j]
    c += 1
  }
  prev = ba[j]
}

print( c )

Measured memory_bytes: 4080
#include<bits/stdc++.h>
#define int long long int
#define mod 998244353 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
int32_t main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output1.txt","w", stdout);
    #endif
    int n;
    cin>>n;
    int a[n];
    for (int i = 0; i < n; ++i)
    {
        cin>>a[i];
    }
    int ans=0,s;
    s=a[0];
    for (int i = 1; i < n; ++i)
    {
        s=max(s,a[i]);
        ans+=(s-a[i]);
    }
    cout<<ans;
    #ifndef LOCAL_DEFINE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
    #endif
    return 0;
}       

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

using ll = long long;

const int INF = 1001001001;
const ll INF_LL = 1001001001001001001LL;

int main(void){
  int n,k; cin >> n >> k;
  int ans;
  if(n%k==0) ans = 0;
  else ans = 1;

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


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

using namespace std;

int main(void){
	int A, B, C, X;
	scanf("%d %d %d %d", &A, &B, &C, &X);

	int s = 0;
	for(int i = 0;i <= A;++i){
		for(int j = 0;j <= B;++j){
			for(int k = 0;k <= C;++k){
				if(500*i + 100*j + 50*k == X) ++s;
			}
		}
	}

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

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

const double EPS = 1e-8;
const double INF = 1e12;
typedef complex<double> P;

bool operator < (const P& a, const P& b) {
  return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
}

double cross(const P& a, const P& b) {
  return imag(conj(a)*b);
}
double dot(const P& a, const P& b) {
  return real(conj(a)*b);
}
struct L : public vector<P> {
  L(const P &a, const P &b) {
    push_back(a); push_back(b);
  }
};

int ccw(P a, P b, P c) {
  b -= a; c -= a;
  if (cross(b, c) > 0)   return +1;       // counter clockwise
  if (cross(b, c) < 0)   return -1;       // clockwise
  if (dot(b, c) < 0)     return +2;       // c--a--b on line
  if (norm(b) < norm(c)) return -2;       // a--b--c on line
  return 0;
}

int main() {
  double x1,y1,x2,y2,x3,y3, x, y;
  while(cin >> x1) {
    cin >> y1 >> x2 >> y2 >> x3 >> y3 >> x >> y;
    P a1(x1,y1), a2(x2,y2), a3(x3,y3), a(x,y);

    if (ccw(a1,a2,a)==1 && ccw(a2,a3,a)==1 && ccw(a3, a1, a)==1
      || ccw(a1,a2,a)==-1 && ccw(a2,a3,a)==-1 && ccw(a3, a1, a)==-1)
      cout << "YES";
    else
      cout << "NO";
    cout << endl;
  }
}

Measured memory_bytes: 0
from collections import deque as deque
def IsBridgeBFS(m):#m辺目をぶっこ抜いたDFS
    newlines=[[] for oiejfo in range(N)]
    for k,line in enumerate(lines):
        x,y=line
        if k==m:continue
        newlines[x].append(y)
        newlines[y].append(x)
    stack=deque()
    went=[False]*N
    stack.append(0)
    went[0]=True
    while stack:
        cur=stack.pop()
        for togo in newlines[cur]:
            if not went[togo]:
                went[togo]=True
                stack.append(togo)
    return(not all(went))#bridge:True

N,M=[int(k) for k in input().split()]#N頂点N辺
lines=[[int(j)-1 for j in input().split()]for i in range(M)]

print(sum([IsBridgeBFS(k) for k in range(M)]))

Measured memory_bytes: 3316
package main

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

var sc *bufio.Scanner

const BufferSize = 1024

func nextInt() int {
	if !sc.Scan() {
		panic(nil)
	}
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

type bc struct {
	num int
	t   int
	end int
	pos int
}

type bcs []bc

func (b bcs) Len() int {
	return len(b)
}

func (b bcs) Swap(i, j int) {
	b[i], b[j] = b[j], b[i]
}

func (b bcs) Less(i, j int) bool {
	return b[i].t < b[j].t
}

type ec struct {
	end int
	pos int
}

type ecs []ec

func (h ecs) Len() int           { return len(h) }
func (h ecs) Less(i, j int) bool { return h[i].pos < h[j].pos }
func (h ecs) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

var production bool

func debugf(format string, v ...interface{}) {
	if !production {
		fmt.Printf(format, v...)
	}
}

func answer(reader io.Reader, writer io.Writer) {
	sc = bufio.NewScanner(reader)
	buf := make([]byte, BufferSize)
	sc.Buffer(buf, 1e+6)
	sc.Split(bufio.ScanWords)
	n := nextInt()
	q := nextInt()

	s := make([]bc, 0, n)
	for i := 0; i < n; i++ {
		b := nextInt()
		e := nextInt()
		x := nextInt()
		s = append(s, bc{i, b - x, e - x, x})
	}
	sort.Sort(bcs(s))

	c := make([]ec, 0, n)
	idxS := 0
	debugf("s: %v\n", s)
	for i := 0; i < q; i++ {
		d := nextInt()
		debugf("d[%d]: %v\n", i, d)

		flag := true
		for j := 0; j < len(c); j++ {
			debugf("Check[%d]: %v\n", j, c[j])
			if c[j].end <= d {
				debugf("Remove[%d]\n", j)
				c = c[1:]
				j--
				if flag {
					sort.Sort(ecs(c))
				}
				flag = false
			} else {
				break
			}
		}

		flag = false
		for idxS < n && s[idxS].t <= d {
			if d < s[idxS].end {
				debugf("Push[%d]: %v\n", idxS, s[idxS])
				c = append(c, ec{s[idxS].end, s[idxS].pos})
				if c[0].pos > s[idxS].pos {
					flag = true
				}
			} else {
				debugf("Skip[%d]: %v\n", idxS, s[idxS])
			}
			debugf("c: %v\n", c)
			idxS++
		}
		if flag {
			sort.Sort(ecs(c))
		}

		if len(c) > 0 {
			debugf("Out: %v\n", c[0].pos)
			_, _ = fmt.Fprintf(writer, "%v\n", c[0].pos)
		} else {
			debugf("Out: -1\n")
			_, _ = fmt.Fprintln(writer, "-1")
		}
	}
}

func main() {
	production = true
	answer(os.Stdin, os.Stdout)
}


Measured memory_bytes: 22272
#include <algorithm>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>

using namespace std;

#define reps(i,f,n) for(int i=f; i<int(n); ++i)
#define rep(i,n) reps(i,0,n)

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

const int INF = 1001001001;

int main()
{
	for(;;){
		int bestid;
		int best = -1;
		rep(i, 5){
			int a, b;
			scanf("%d%d", &a, &b);
			if(a==0 && b==0)
				goto end;
			a += b;
			if(best < a){
				bestid = i;
				best = a;
			}
		}
		printf("%c %d\n", bestid+'A', best);
	}
end:
	return 0;
}

Measured memory_bytes: 1028
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<vector>
#include<algorithm>
#include<utility>
#include<string>
#include<cstring>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<iterator>
//#include<math.h>

using namespace std;
#define int long long
/*                      */    //#undef int
#define INF 1000000009
#define INFL 1000000000000000018ll
#define mod 1000000007ll
#define pb push_back
#define fi first
#define se second
#define mk make_pair
typedef pair<int, int> PA;
typedef priority_queue<int> PQ;
typedef priority_queue<PA, vector<PA>, greater<PA> >PQG;

string s;
queue<int> que;

signed main()
{
    cin >> s;
    int N = s.size();
    s = 'a' + s;
    bool flag = false;
    if(s[1] == '0' || s[N - 1] == '0' || s[N] == '1'){
        flag = true;
    }
    s[N] = '1';
    for(int i = 1; i <= N; i++){
        if(s[i] == '1'){
            que.push(i);
        }
        if(s[i] != s[N - i] && i < N){
            flag = true;
        }
    }
    if(flag){
        printf("-1\n");
        return 0;
    }
    for(int i = 1; i < N; i++){
        if(i == que.front()){
            que.pop();
        }
        printf("%lld %lld\n", i, que.front());
    }

    return 0;
}
/*


*/


Measured memory_bytes: 2300
#include <iostream>
#include <set>
#include <vector>
using namespace std;
const long long INF=1e18+7;
long long n, m, s, l, x, y, z,r=0;
vector <pair<long long,long long> > g[200001];
set <pair<long long, long long> > q;
long long d[200001];
int main() {
	for(long long i=0;i<200001;i++)d[i]=INF;
	cin >> m;
	for(long long i=0;i<m-1;i++){
		cin >> x >> y >> z;
		g[x].push_back(make_pair(y,z));
		g[y].push_back(make_pair(x,z));
	}
	cin >> m >> s;
	d[s]=0;
	q.insert(make_pair(d[s],s));
	while(!q.empty()){
		long long t=q.begin()->second;
		q.erase(q.begin());
		for(long long i=0;i<g[t].size();i++){
			long long to=g[t][i].first,tl=g[t][i].second;
			if(d[t]+tl<d[to]){
				q.erase(make_pair(d[to],to));
				d[to]=d[t]+tl;
				q.insert(make_pair(d[to],to));
			}
		}
	}
	for(long long i=0;i<m;i++){
		cin >> x >> y;
		cout << d[x]+d[y] << endl;
	}
	return 0;
}

Measured memory_bytes: 18544
import sys
from math import pi, cos, sqrt
from collections import defaultdict
readline = sys.stdin.buffer.readline
#sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    N = gete(int)
    v = list(geta(int))
    v.sort()

    base = 1

    ans = v[0]
    for vi in v[1:]:
        ans += vi * base
        base *= 2

    print(ans / base)


if __name__ == "__main__":
    main()

Measured memory_bytes: 3316
a, b, c = map(int, input().split())
d, e, f = map(int, input().split())
g, h, i = map(int, input().split())

if a-d==b-e==c-f and a-g==b-h==c-i and a-b==d-e==g-h and a-c==d-f==g-i:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3060
#include<iostream>
using namespace std;
int main(){
    int n,x;
    cin >> n;
    for(int i = 1; i <= n; i++){
        x = i;
        if(x % 3 == 0){
            cout << " " << i;
        } else {
            while(x != 0){
                if(x % 10 == 3){
                    cout <<  " " << i;
                    break;
                } else {
                    x /= 10;
                }
            }
        }
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 3108
/*  /$$                                     /$$
      | $$                                    | $$
  /$$$$$$$  /$$$$$$   /$$$$$$$  /$$$$$$   /$$$$$$$  /$$$$$$   /$$$$$$
 /$$__  $$ /$$__  $$ /$$_____/ /$$__  $$ /$$__  $$ /$$__  $$ /$$__  $$
| $$  | $$| $$$$$$$$| $$      | $$  \ $$| $$  | $$| $$$$$$$$| $$  \__/
| $$  | $$| $$_____/| $$      | $$  | $$| $$  | $$| $$_____/| $$
|  $$$$$$$|  $$$$$$$|  $$$$$$$|  $$$$$$/|  $$$$$$$|  $$$$$$$| $$
 \_______/ \_______/ \_______/ \______/  \_______/ \_______/|__//$$$$$$ /$$$$$$
                                                               |______/|______/

*/
#include <bits/stdc++.h>
#define fastio        ios_base::sync_with_stdio(false); cin.tie(NULL);
#define ln            cout<<endl;
#define vi            vector<int>
#define vll           vector<long long>
#define sortl(vec)    sort(vec.begin(), vec.end());
#define sortr(vec)    sort(vec.rbegin(), vec.rend());
#define forn(i, x, n) for(long long i = x; i < n; i++)
#define revn(i, n, x) for(long long i = n; i >= x ; i--)
#define in(vec)       for(auto &it : vec) cin >> it;
#define loop(vec)     for(auto &it : vec)
#define	out(vec)      for(auto &it : vec) cout << it << " "; ln
#define ll            long long
#define mod           1000000007
#define debug(x)      cout << x << endl;
#define pb            emplace_back
#define mp            make_pair
#define um            unordered_map
#define pii           pair<int, int>
#define pll           pair<ll, ll>
#define f             first
#define s             second
#define pi            3.14159265359
#define CLOCK         cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" secs"<<endl;
using namespace std;

ll power(ll x, ll y, ll p) {
	ll res = 1;
	x = x % p;

	while (y > 0) {
		if (y & 1)
			res = (res * x) % p;

		y = y >> 1;
		x = (x * x) % p;
	}
	return res;
}

ll modulo(ll a, ll b) {
	ll c = a % b;
	return (c < 0) ? c + b : c;
}

int main() {
// in(vec) works for size-defined type vectors

#ifndef ONLINE_JUDGE
	// for getting input from input.txt
	freopen("input1.txt", "r", stdin);
	// for writing output to output.txt
	freopen("output1.txt", "w", stdout);
#endif

	fastio
	ll t = 1;
	while (t--) {
		ll x, n;
		cin >> x >> n;
		vll vec(n);
		in(vec);
		sortl(vec);
		set<ll>se;

		vll diff(101, 0);

		forn(i, 0, n) {
			diff[abs(vec[i] - x)]++;
			se.insert(vec[i]);
		}
		//out(diff)
		if (!diff[0]) {
			cout << x << endl;
			break;
		}
		forn(i, 0, 101) {
			if (diff[i] < 2 && i != 0) {
				if (se.find(x - i) == se.end())
					cout << x - i << endl;
				else
					cout << x + i << endl;
				break;
			}
		}

	}
	CLOCK
	return 0;
}



Measured memory_bytes: 3848
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#define rep(i,n) for(int i=0;i<(n);i++)
#define psortsecond(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.second<b.second;});
#define psortfirst(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.first<b.first;});
#define All(x) (x).begin(),(x).end()
using namespace std;
using pii  = pair<int,int>;
long long gcd(long long a, long long b){return (b == 0 ? a : gcd(b, a%b));}
long long lcm(long long a, long long b){return a*b/gcd(a,b);}
typedef long long ll;
#define MOD 1000000007
#define EPS 10e-8

int main() {
    ll A[4];
    rep(i,3){
        cin >> A[i];
    }
    sort(A,A+3);
    cout << A[0]+A[1] << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define Rep(i,s,n) for(int i=s;i<n;i++)
typedef long long int ll;
typedef pair<int, int> P;
typedef long double ld;
void ans(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}

const ll INF=1001001001;
const ll mod=10000000007;

int main(){
  ll k,n;cin>>k>>n;
  ll a[n];
  rep(i,n){
    cin>>a[i];
  }
  ll an=0;
  rep(i,n-1){
    an=max(an,a[i+1]-a[i]);
  }
  an=max(an,a[0]+k-a[n-1]);
  cout<<k-an<<endl;
}

Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cmath>
#include <algorithm>
#include <map>
#include <sstream>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <functional>
#include <utility>
#include <stdio.h>
#define ll long long
#define MP make_pair
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define PLI pair<ll, int>
#define PIL pair<int, ll>
#define F first
#define S second
#define SHN 1e9
#define LSHN 1e18
using namespace std;
int n;
bool a[110][20];
ll p[110][20];
int c[110];
ll res=-1e18;
int main()
{
	cin >>n;
	for (int i=0;i<n;i++)
	{
		for (int j=0;j<10;j++)
		    cin >>a[i][j];
	} 
	for (int i=0;i<n;i++)
	{
		for (int j=0;j<=10;j++)
		    cin >>p[i][j];
	} 
	for (int i=1;i<(1<<10);i++)
	{
		fill(c,c+n,0);
		for (int j=0;j<10;j++)
		{
			if (!(i & (1<<j))) continue;
			for (int k=0;k<n;k++) if (a[k][j]) c[k]++;
		}
		ll r=0;
		for (int j=0;j<n;j++) r+=p[j][c[j]];
		res=max(res,r); 
	}
	cout <<res;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define MOD 1000000007
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
  
int main()
{
  int N;
  cin >> N;
  vector<int> A(N);
  REP(i, N) cin >> A[i];
  int sum = 0;
  REP(i,N){
    if(A.at(i)%2==0){
      sum++;
    }
  }
  int a = 1;
  REP(i,N){
    a*=3;
  }

  int b = 1;
  REP(i,sum){
    b*=2;
  }
  cout << a-b << endl;
}

Measured memory_bytes: 256
n = int(input())
A = sorted(map(int, input().split()))
L = []
if A[0] >= 0:
  x = A[0]
  for i in range(1, n-1):
    L.append((x, A[i]))
    x -= A[i]
  L.append((A[-1], x))
  M = A[-1] - x
elif A[-1] < 0:
  x = A[-1]
  for i in range(1, n):
    L.append((x, A[n-1-i]))
    x -= A[n-1-i]
  M = x
else:
  for i in range(n):
    if A[i] >= 0:
      border = i
      break
  for i in range(border, n-1):
    L.append((A[0], A[i]))
    A[0] -= A[i]
  x = A[-1]
  for i in range(border):
    L.append((x, A[i]))
    x -= A[i]
  M = x
  
print(M)
for x, y in L:
  print(x, y)

Measured memory_bytes: 19460
"""
# 標準入力取得
## 文字列
 = sys.stdin.readline().rstrip()
 = list(sys.stdin.readline().rstrip())

## 数値
 = int(sys.stdin.readline())
 = map(int, sys.stdin.readline().split())
 = list(map(int, sys.stdin.readline().split()))
 = [list(map(int,list(sys.stdin.readline().split()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

# 0埋め, 小数点出力桁指定時のときの出力
a = 100
b = 0.987654321
print("{0:06d}-{1:6f}".format(a,b))
000100-0.987654

# 文字列をリストに格納
char_list = list("abcd") # ["a","b","c","d"]
"""

import math
import sys
import itertools
import queue
from fractions import gcd

def lcm(a, b):
    return a * b // gcd(a, b)

mod = 1000000007

if __name__ == "__main__":
    S= list(sys.stdin.readline().rstrip())
    N = len(S)

    ans=0
    for i in range(N):
        for j in range(i,N):
            if all("ACGT".count(c) == 1 for c in S[i:j+1]): #all()は中身がすべてTrueならTrueを返す。S部分文字列から１個ずつ取り出して"ACGT".count(c) == 1で判定
                ans = max(ans, j-i+1)
            # print(all("ACGT".count(c) == 1 for c in S[i:j+1]))

    print(ans)


Measured memory_bytes: 5324
#include <iostream>
#include <vector>
#include <cstdlib>  
#include <algorithm>
#include <string>

using namespace std;
 
int main() {
   int n,t;cin>>n>>t;
   int ss =1000000;
   bool ikeru = false;
   for(int i = 0;i<n;i++){
      int c,tt;cin>>c>>tt;
      if(t >= tt){
        ss = min(ss,c);
        ikeru = true;
      }
   }
   if(ikeru == false) cout<<"TLE";
   else cout<<ss;
}

Measured memory_bytes: 3612
#include<bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
#define dbg(x...) do{cout << "\033[32;1m" << #x << "->" ; err(x);} while(0)
void err(){cout << "\033[39;0m" << endl;}
template<template<typename...> class T,typename t,typename... A>
void err(T<t> a,A... x){for (auto v:a) cout << v << ' '; err(x...);}
template<typename T,typename... A>
void err(T a,A... x){cout << a << ' '; err(x...);}
#else
#define dbg(...)
#endif
typedef long long ll;
typedef pair<int,int> pi;
typedef vector<int> vi;
template<class T> using vc=vector<T>;
template<class T> using vvc=vc<vc<T>>;
template<class T> void mkuni(vector<T>&v)
{
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
}
template<class T>
void print(T x,int suc=1)
{
    cout<<x;
    if(suc==1) cout<<'\n';
    else cout<<' ';
}
template<class T>
void print(const vector<T>&v,int suc=1)
{
    for(int i=0;i<v.size();i++)
        print(v[i],i==(int)(v.size())-1?suc:2);
}
const int INF=0x3f3f3f3f;
const int maxn=2e3+7;
const int mod=1e9+7;
ll quick(ll a,ll b)
{
	if(b<0) return 1;
	ll ret=1;
	while(b)
	{
		if(b&1) ret=ret*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ret;
}
ll dp[maxn][maxn];
int main()
{
	int n,k;
	cin>>n>>k;
	dp[0][n+1]=1;
	for(int i=1;i<=k;i++)
	{
		vc<ll> suf(n+3);
		for(int j=n+1;j>=1;j--)
			suf[j]=(suf[j+1]+dp[i-1][j])%mod;
		for(int j=1;j<=n-i+1;j++)
		{
			if(i==k) dp[i][j]=suf[j+1];
			else
				dp[i][j]=(dp[i-1][j]+suf[j+1])%mod;
			//dbg(i,j,dp[i][j]);
		}
	}
	cout<<dp[k][1]*quick(2,n-k-1)%mod<<endl;
}


Measured memory_bytes: 31104
#include <iostream>
#include <cmath>
#include <vector>
#include <cstdlib>
#include <stdio.h>


using namespace std;

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

  char str[6];
  cin >> str;
  int num = 0;
  for(int i = 0; i < 6; i++){
    if(str[i] == '1'){
      num++;
    }
  }

  cout << num << endl;
  return 0;
}


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

using namespace std;

map<int ,int> ans;
int n;
int dispo;

int main(){
  cin>>n;
  
  for(int i=0;i<n;i++){
    cin>>dispo;
    if(ans.count(dispo)==0)
      ans.insert(make_pair(dispo,0));
  }
  cout<<ans.size()<<endl;
                 }
                 
  

Measured memory_bytes: 256
N,C,K = map(int, input().split())

T = [int(input()) for i in range(N)]
sort_T = sorted(T)
a = 1 #バスの乗車人数
cnt = 1 #バスの台数
t = sort_T[0] + K #バスの一人目の到着時刻

for i in range(1,N):
    if a < C and sort_T[i] <= t:
        a +=1
    else:
        a = 1
        cnt += 1
        t = sort_T[i] + K

print(cnt)

Measured memory_bytes: 8280
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, q, r;
  cin >> n >> q >> r;
  vector<int> stop(r);
  for (int i = 0; i < r; i++) {
    int tmp;
    cin >> tmp;
    tmp--;
    stop[i] = tmp;
  }
  vector<vector<int>> dst(n, vector<int>(n));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      dst[i][j] = ((i == j) ? 0 : inf);
    }
  }
  while (q--) {
    int a, b, c;
    cin >> a >> b >> c;
    a--;
    b--;
    dst[a][b] = dst[b][a] = c;
  }
  for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
      if (dst[i][k] == inf) {
        continue;
      }
      for (int j = i + 1; j < n; j++) {
        if (dst[j][k] == inf) {
          continue;
        }
        dst[i][j] = dst[j][i] = min(dst[i][j], dst[i][k] + dst[k][j]);
      }
    }
  }
  int all = 1 << r;
  vector<vector<int>> dp(all, vector<int>(r, inf));
  for (int i = 0; i < r; i++) {
    dp[all - 1][i] = 0;
  }
  for (int ckd = all - 2; ckd >= 0; ckd--) {
    for (int crr = 0; crr < r; crr++) {
      if (!(ckd & (1 << crr))) {
        continue;
      }
      for (int nxt  = 0; nxt < r; nxt++) {
        dp[ckd][crr] = min(dp[ckd][crr], dp[ckd | (1 << nxt)][nxt] + dst[stop[crr]][stop[nxt]]);
      }
    }
  }
  int ans = inf;
  for (int i = 0; i < r; i++) {
    ans = min(ans, dp[1 << i][i]);
  }
  cout << ans << '\n';
}

Measured memory_bytes: 456
#include<bits/stdc++.h>
using namespace std;
bool pd[10]={0};
bool check(int x)
{
	while(x)
	{
		if(pd[x%10])
		{
			return 0;
		}
		x/=10;
	}
	return 1;
}
int main()
{
	int x;
	int n,k;
	
	cin>>n>>k;
	for(int i=1;i<=k;i++)
	{
		cin>>x;
		pd[x]=1;
	}
	int now;
	for(int i=n;i<=100000;i++)
	{
		if(check(i))
		{
			cout<<i<<endl;
			return 0;
		}
	}
	return 0;
}

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

using namespace std;
int main(){
    string a;
    cin>>a;
    for(int x=0;x<(1<<3);x++){
        int sum=a[0]-'0';
        string s;
        s+=a[0];
        for(int i=0;i<3;i++){
            if(x&(1<<i)){
              sum+=a[i+1]-'0';
              s+='+';
              s+=a[i+1];
            }
            else{
                sum-=a[i+1]-'0';
                s+='-';
                s+=a[i+1];
            }
        }
        if(sum==7){
            cout<<s<<"=7"<<endl;
            return 0;
        }
    }
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, m, n) for(int i = m; i < (n); i++)
#define rrep(i,m,n) for(int i = m; i >= n; i--)
#define print(x) cout << (x) << endl;
#define print2(x,y) cout << (x) << " " << (y) << endl;
#define printa(x,n) for(int i = 0; i < n; i++){ cout << (x[i]) << " ";} cout << endl;
#define printa2(x,m,n) for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ cout << x[i][j] << " ";} cout << endl;}
#define printp(x,n) for(int i = 0; i < n; i++){ cout << "(" << x[i].first << ", " << x[i].second << ") "; } cout << endl;
#define INF (1e18)
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
typedef struct{
    ll to;
    ll cost;
} edge;
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} //最大公約数
inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;} //最小公倍数
typedef pair<ll, ll> lpair;
inline vector<ll> factor(ll M){ //素因数分解
    vector<ll> dd;
    if(M == 1){
        dd.push_back(1);
        return dd;
    }
    for(ll i = 2; i*i <= M; i++){
        while(M % i == 0){
            dd.push_back(i);
            M /= i;
        }
    }
    if(M != 1) dd.push_back(M);
    sort(dd.begin(), dd.end());
    return dd;
}
map<ll, ll> mp;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N, P;
    cin >> N >> P;
    vector<ll> dd = factor(P);
    ll n = dd.size();
    ll ans = 1;
    rep(i,0,n){
        mp[dd[i]]++;
        if(mp[dd[i]] % N == 0){
            ans *= dd[i];

        }
    }
    print(ans);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
    #define REP(i, n) for(int i = 0;i < n;i++)
    #define REPR(i, n) for(int i = n;i >= 0;i--)
    #define FOR(i, m, n) for(int i = m;i < n;i++)
    #define FORR(i, m, n) for(int i = m;i >= n;i--)
    #define SORT(v, n) sort(v, v+n);
    #define VSORT(v) sort(v.begin(), v.end());
    #define llong long long
    #define pb(a) push_back(a)
    #define INF 999999999
    using namespace std;
    typedef pair<int, int> P;
    typedef pair<llong, llong> LP;
    typedef pair<int, P> PP;
    typedef pair<llong, LP> LPP;

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

    int main()
    {
       llong N,T;
       cin>>N>>T;
       vector<llong> t(N,0);
        for(llong i=0; i<N; i++){ cin>>t[i];}
       llong sum=0;
       for(llong i=0; i<N-1; i++)
       {
           if(t[i+1]-t[i]>=T)
           {
               sum+=T;
           }
           else
               {
               sum+=t[i+1]-t[i];
               }
       }
       cout<<sum+T<<endl;
    }

Measured memory_bytes: 1792
#include<iostream>
#include <algorithm>
#include<string>
#include<cmath>
#include <functional>
using namespace std;
int R(int Cx, int Cy, int x, int y) {
	return abs(x-Cx)+abs(y-Cy);
}
int main(void) {
	int N,M,ans;
	cin >> N >>M;
	if (N == 1)
		ans = M;
	else if (N == 2 && M % 2 == 0)
		ans = M / 2;
	else if (N == 3 && M % 3 == 0)
		ans = M / 3;	
	else {
		for (long int n = 1;n <= M / N + 2;n++) {
			if (M%n == 0 && M / n >= N)
				ans = n;
		}
	}
	cout << ans << endl;
	return 0;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int64_t x,k,d;
  cin >> x >> k >> d;
  int64_t m=0;
  int64_t X=max(x,x*-1);
  if(X/d>k){
    m=X-d*k;
  }
  else if((k-(X/d))%2==0){
    m=X-d*(X/d);
  }
  else{
    m=d*(X/d+1)-X;
  }
  cout << m << endl;
}

Measured memory_bytes: 3588
def bits2tuple(n):
    ret = []
    i = 0
    while (1 << i) <= n:
        if n & (1 << i) != 0:
            ret.append(i)
        i += 1
    return tuple(ret)


def main():
    N, M = map(int, input().split())

    kM = []
    skM = []
    for _ in range(M):
        sk = list(map(int, input().split()))
        k = sk.pop(0)

        kM.append(k)
        skM.append(sk)

    pM = list(map(int, input().split()))

    ans = 0
    for bits in range(0, 1 << N):
        on_switch = list(map(lambda x: x + 1, bits2tuple(bits)))

        all_on = True
        for p, k, sk in zip(pM, kM, skM):
            if len(set(on_switch) & set(sk)) % 2 != p:
                all_on = False
                break

        if all_on:
            ans += 1

    print(ans)


main()


Measured memory_bytes: 3064
import sys
input = sys.stdin.readline
from fractions import gcd
from collections import Counter

"""
適当に部分集合Xをとり、凸包 S として、Sに1点計上すればよい
これだと2^N点得られる
ただし、凸包の面積が0となる場合が例外
空集合、1点の場合と、線分の場合を除外する

"""

MOD = 998244353
N = int(input())
XY = [[int(x) for x in input().split()] for _ in range(N)]

answer = pow(2,N,MOD)
answer -= N + 1# 空、1点
for i,(x,y) in enumerate(XY):
    # i を選び、i+1番目以上のうちいくつかを選んで線分とする
    pts = []
    for x1, y1 in XY[i+1:]:
        dx, dy = x1-x, y1-y
        g = gcd(dx, dy)
        dx //= g
        dy //= g
        # 標準化
        if dx < 0:
            dx, dy = -dx, -dy
        elif dx == 0:
            dy = 1
        pts.append((dx,dy))
    c = Counter(pts)
    for v in c.values():
        answer -= pow(2,v,MOD) - 1

answer %= MOD
print(answer)

Measured memory_bytes: 5112
#include <stdio.h>
int newline[12];
int oldline[12];
int main() {
	while(1) {
		int i, j, N;
		scanf("%d", &N);
		if(N == 0) break;
		for(i = 0; i < N; ++ i) {
			scanf("%d", &oldline[i]);
			newline[i] = 0;
		}
		int count = 0;
		while(1) {
			for(i = 0; i < N; ++ i) for(j = 0; j < N; ++ j) if(oldline[j] == oldline[i]) newline[i] ++;
			int flag = 1;
			for(i = 0; i < N; ++ i) {
				if(newline[i] != oldline[i]) flag = 0;
				oldline[i] = newline[i];
				newline[i] = 0;
			}
			if(flag) {
				printf("%d\n", count);
				printf("%d", oldline[0]);
				for(i = 1; i < N; ++ i) printf(" %d", oldline[i]);
				printf("\n");
				break;
			}
			count++;
		}
	}
	return 0;
}

Measured memory_bytes: 604
#include <iomanip>
#include <iostream>
#include <math.h>
using namespace std;
const int N=3e3+10;
const long double pi=acosl(-1);
int main(){
	int n;
  long long int tot;
	long double x=0,y=0,l,t[N],pos;
	cin>>n>>l;
	for(int i=1;i<=n;i++)cin>>t[i];
	for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++){
		pos=(t[i]+t[j])*pi/l;
		x+=cos(pos)*(n-j-j+i+i);
		y+=sin(pos)*(n-j-j+i+i);
	}
	tot=1LL*n*(n-1)*(n-2)/6;
	cout<<fixed<<setprecision(20)<<x/tot<<' '<<fixed<<setprecision(20)<<y/tot<<endl;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdint>
#include <vector>
#include <algorithm>

int main() {
  size_t N, K;
  scanf("%zu %zu", &N, &K);

  if (N == K)
    return !printf("1\n");

  std::vector<int> A(N);
  for (size_t i=0; i<N; ++i) {
    scanf("%d", &A[i]);
  }

  --K, --N;
  printf("%zu\n", (K+N-1)/K);
}


Measured memory_bytes: 640
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Linq;

namespace GreatOceanView {
	class Program {
		static void Main(string[] args) {
			var n = Console.ReadLine();
			var heights = Helper<int>.ReadLine();
			var border = heights[0];
			var oceanViewCount = 0;
			foreach (var height in heights) {
				if (height >= border) {
					oceanViewCount++;
					border = height;
				}
			}
			Console.WriteLine(oceanViewCount);
		}
	}

	public static class Helper<T> {
		public static T[] Read(int count) {
			var result = new T[count];
			for (int index = 0; index < count; index++) {
				result[index] = (T)TypeDescriptor.GetConverter(typeof(T)).ConvertFromString(Console.ReadLine());
			}
			return result;
		}

		public static T[] ReadLine() {
			var input = Console.ReadLine();
			var inputs = input.Split(' ');
			var result = new T[inputs.Count()];
			for (int index = 0; index < inputs.Count(); index++) {
				result[index] = (T)TypeDescriptor.GetConverter(typeof(T)).ConvertFromString(inputs[index]);
			}
			return result;
		}
	}
}


Measured memory_bytes: 14432
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()
#define downque(que)  priority_queue<ll> que;
#define upque(que) priority_queue<ll, vector<int>, greater<int>> que;
using namespace std;
typedef long long ll;
const int MOD = 1e9+7;


int main(){
  string s;  cin>>s;
  ll k; cin>>k;
  int n=s.size();
  string t=s+s+s+s;
  ll c1=0,c2=0,c3=0,c4=0;
  
  
  FOR(i,1,t.size()){
      if(t[i]==t[i-1]){
        t[i]='A';
        if(i<n)c1++;
        else if(i<n*2)c2++;
        else if(i<n*3)c3++;
        else c4++;
      }
  }

  ll res;
  if(k==1)res=c1;
  else if(k==2)res=c1+c2;
  else if(k%2==0)res=c1+(c2+c3)*((k-2)/2)+c4;
  else if(k%2==1)res=c1+(c2+c3)*((k-1)/2);
  
  cout<<res<<endl;


}

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

int main()
{
  int n; cin>>n;
  int a[n];
  rep(i, n) {
    cin >> a[i];
  }

  string mode = "init";
  int ans = 1;

  for(int i = 0; i < n-1; i++){
    if (mode == "init") {
      if(a[i] < a[i+1]) {
        mode = "plus";
      } else if (a[i] > a[i+1]) {
        mode = "minus";
      }
    // 単調非減少
    } else if (mode == "plus") {
      if(a[i] > a[i+1]) {
        ans++;
        mode = "init";
      }
    // 単調非増加
    } else if (mode == "minus") {
      if(a[i] < a[i+1]) {
        ans++;
        mode = "init";
      }
    }
  }
  cout << ans << endl;
  return 0;
}

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

int main() {
    int K, A, B, i, flag = 0;
    cin >> K >> A >> B;
    for (i = A; i <= B; i++) {
        if (i % K == 0) flag++;
    }
    if (flag > 0) cout << "OK" << endl;
    else cout << "NG" << endl;
}

Measured memory_bytes: 3632
#include<stdio.h>
int main()
{
  int A[100];
  int N;
  int i,j,tmp,cnt=0;
  int flag;
  scanf("%d",&N);
  for(i=0;i<N;i++)
    {
      scanf("%d",&A[i]);
    }
  flag = 1;
  while(flag)
    {
      flag=0;
      for(i=0;i<N-1;i++)
	{
	  for(j=N-1;j>0;j--)
	    {
	      if(A[j]<A[j-1])
		{
		  tmp=A[j-1];
		  A[j-1]=A[j];
		  A[j]=tmp;
		  flag = 1;
		  cnt++;
		}
	    }
	}
    }
  for(i=0;i<N;i++)
    {
      printf("%d",A[i]);
      if(i!=N-1)printf(" ");
    }
  printf("\n");
  printf("%d\n",cnt);
  return 0;
}

Measured memory_bytes: 604
#include<stdio.h>
#define MAX 100000
int n,k;
long long T[MAX];

int calculate(long long P) {
  int i = 0,j;
  for(j = 0;j < k;j++) {
    long long s = 0;
    while(s + T[i] <=P) {
      s += T[i];
      i++;
      if(i==n)return n;
    }
  }
  return i;
}

int binary(void) {
long long left = 0,mid;
long long right = (long long)MAX*MAX;
while(right - left > 1) {
  mid = (left + right) / 2;
  int hantei = calculate(mid);
  if(hantei >= n) right = mid;
  else left = mid;
}
return right;
}

int main()  {
  int i;
  scanf("%d%d",&n,&k);
  for(i = 0;i<n;i++) scanf("%lld", &T[i]);
 long long ans = binary();
  printf("%lld\n",ans);
  return 0;

}

Measured memory_bytes: 1376
#include <iostream>

using namespace std;

int main(void)
{
  int A,B,tmp;
  string S;

  cin>>A>>B;
  cin>>S;

  tmp=A+B;
  
  for(int i=0;i<S.length();i++){
    if(S[i]>='0' && S[i]<='9')
      tmp--;
  }

  cout<<((S[A]=='-' && tmp==0) ? "Yes" : "No")<<endl;

  return 0;
}


Measured memory_bytes: 256