akhauriyash/Code-Regression huggingface dataset:
from copy import *
from sys import *
import math
import queue
from collections import defaultdict,Counter,deque
from fractions import Fraction as frac

setrecursionlimit(1000000)

#dp[i][j]: iまでからj枚えらんで和がkになるのは何通り
def main():
	a,b = map(int,input().split())
	print(0 if a<b else 10)

def zip(a):
	mae = a[0]
	ziparray = [mae]
	for i in range(1,len(a)):
		if(mae != a[i]):
			ziparray.append(a[i])
			mae = a[i]
	return ziparray

def is_prime(n):
	if n < 2: return False

	for k in range(2, int(math.sqrt(n)) + 1):
		if n % k == 0:
			return False

	return True

def list_replace(n,f,t):
	return [t if i==f else i for i in n]

def base_10_to_n(X, n):
	X_dumy = X
	out = ''
	while X_dumy>0:
		out = str(X_dumy%n)+out
		X_dumy = int(X_dumy/n)
	if(out == ''): return '0'
	return out

def gcd(m,n):
	x = max(m,n)
	y = min(m,n)
	while(x%y!=0):
		z = x%y
		x = y
		y = z
	return y

class queue():
	def __init__(self):
		self.q = deque([])
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.popleft()
	def size(self):
		return len(self.q)
	def debug(self):
		return self.q

class stack():
	def __init__(self):
		self.q = []
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.pop()
	def size(self):
		return len(self.q)
	def debug(self):
		return self.q

class graph():
	def __init__(self):
		self.graph = defaultdict(list)
	def addnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].append(t)
		self.graph[t].append(f)
	def rmnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].remove(t)
		self.graph[t].remove(f)
	def linked(self,f):
		return self.graph[f]

class dgraph():
	def __init__(self):
		self.graph = defaultdict(set)
	def addnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].append(t)
	def rmnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].remove(t)
	def linked(self,f):
		return self.graph[f]

main()

Measured memory_bytes: 63084
#include <iostream>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
priority_queue<P, vector<P>, greater<P>> red, blue;
map<ll, bool> mp;
ll n, x, y, res;
int main(void){
    // Your code here!
    cin >> n;
    for (ll i = 0; i < n; i++) {
        cin >> x >> y;
        red.push(P(x, y));
    }
    for (ll i = 0; i < n; i++) {
        cin >> x >> y;
        blue.push(P(x, y));
    }
    while (blue.size()) {
        P p1 = blue.top(); blue.pop();
        while (red.size()) {
            P p2 = red.top();
            if (p2.first > p1.first) break;
            red.pop();
            mp[p2.second] = true;
        }
        for (ll i = 0; i < mp.size(); i++) {
            auto itr = mp.begin();
            for (ll j = 1; j < mp.size() - i; j++) itr++;
            if (itr->first > p1.second || !itr->second) continue;
            res++; itr->second = false;
            break;
        }
    }
    cout << res << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <cmath>
#include <stack>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <numeric>
#include <iomanip>


int main()
{
	long long n;
	std::string s;

	std::cin >> n >> s;

	long long x = 0, max = 0;

	for (size_t i = 0; i < s.length(); i++) {
		if (s[i] == 'I') {
			x++;
		} else {
			x--;
		}
		max = std::max(max, x);
	}

	std::cout << max << std::endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, a, n) for (long long i = (a); i < (long long)(n); ++i)
#define REPC(i, a, n) for (long long i = (a); i <= (long long)(n); ++i)
#define ALL(t) t.begin(), t.end()
#define RALL(t) t.rbegin(), t.rend()
#define MATINIT(type, row, col, init) \
  vector<vector<type>>(row, vector<type>(col, init));
#define Yes(cond) cout << (cond ? "Yes" : "No") << endl;
#define YES(cond) cout << (cond ? "YES" : "NO") << endl;
using namespace std;
using LL = long long;
using ULL = unsigned long long;
template <class T>
using VEC = std::vector<T>;
template <class T>
using MAT = std::vector<std::vector<T>>;
void DUMP() { cerr << endl; }
template <class Head, class... Tail>
void DUMP(Head &&head, Tail &&... tail) {
  cerr << head << ", ";
  DUMP(std::move(tail)...);
}
template <typename T>
ostream &operator<<(ostream &os, vector<T> &vec) {
  os << "{";
  for (auto v : vec) os << v << ",";
  os << "}";
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, set<T> &s) {
  os << "{";
  for (auto p : s) os << p << ",";
  os << "}";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, map<T1, T2> &m) {
  os << "{";
  for (auto p : m) os << p << ",";
  os << "}";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, pair<T1, T2> p) {
  os << "[" << p.first << " " << p.second << "]";
  return os;
}

int main() {
  int N;
  cin >> N;
  VEC<pair<LL, LL>> X(N);
  VEC<pair<LL, LL>> I(N);
  REP(i, 0, N) { cin >> X[i].first >> X[i].second; }
  REP(i, 0, N) {
    I[i].first = X[i].first - X[i].second;
    I[i].second = X[i].first + X[i].second;
  }
  auto compare = [](pair<LL, LL> a, pair<LL, LL> b) {
    if (a.second == b.second) {
      return a.first < b.first;
    }
    return a.second < b.second;
  };
  // I={{1,3},{0,3},{3,3},{2,3}};
  // DUMP(I);
  sort(ALL(I), compare);
  // DUMP(I);
  LL end = I[0].second;
  int cnt = 1;
  REP(i, 1, N) {
    if (I[i].first >= end) {
      cnt++;
      end = I[i].second;
    }
  }
  cout<<cnt<<endl;

  return 0;
}


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

int main()
{
    int n;cin>>n;
    vector<int> a(n);
    int i;
    for(i=0;i<n;i++)cin>>a.at(i);
    vector<int> count(1e5,0);
    for(i=0;i<n;i++)count.at(a.at(i))++;
    int ans=0;
    ans=max(count.at(0)+count.at(1),count.at(1e5-2)+count.at(1e5-1));
    for(i=1;i<1e5-1;i++)
    {
        ans=max(count.at(i)+count.at(i-1)+count.at(i+1),ans);
    }
    cout<<ans<<endl;
}


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

int main(){
  int n,a[26],b[26],c[100],k,ans=0;
  char s;
  cin>>n;
  fr(i,n){cin>>s;c[i]=s-'a';}
  fr(i,n){
    fr(j,26){a[j]=0;b[j]=0;}
    k=0;
    fr(j,i) a[c[j]]++;
    for(int j=i;j<n;j++) if(a[c[j]]>0) b[c[j]]++;
    fr(j,26) if(b[j]>0) k++;
    ans=max(ans,k);
  }
  cout<<ans<<endl;
}

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

int main(void) {
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  int s1 = a*b;
  int s2 = c*d;
  cout << (s1 < s2 ? s2 : s1) << endl;
  return 0;
}


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

using namespace std;
int main()
{
    long long n, m, i, j, k = 0;
    long long a[101], c[101], b[101];
    long long f[101][100001] = {0};
    //freopen("test.inp","r",stdin);
    cin >> n >> m;
    for (i = 1; i <= n; i++) cin >> a[i] >> c[i];
    for (i = 1; i <= n; i++)
        for (j = 0;j <= m; j++)
    {
        f[i][j] = f[i-1][j];
        if (j >= a[i] && f[i][j] <= f[i-1][j-a[i]]+c[i])
            f[i][j] = f[i-1][j-a[i]]+c[i];
    }
    cout << f[n][m];
    return 0;
}


Measured memory_bytes: 79104
N, K=map(int, input().split())
A=list(map(int, input().split()))

idx1=A.index(1)

from math import ceil

ans=10000000

for i in range(K):
  left=idx1-i
  right=left+K-1
  if left<0 or right>N-1:
    continue
  tmp=ceil(left/(K-1))+ceil((N-1-right)/(K-1))+1
  ans=min(ans, tmp)

print(ans)

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

int mod = 1000000007;

int N;
string a,b;
int main () {
    cin >> N >> a >> b;
    long long int cnt = 3;
    a[0] = '9';
    b[0] = '9';

    for(int i=1; i<N; i++) {
        if( a[i] == a[i-1] ) continue;
        if( a[i] == b[i] ) cnt *= (a[i-1] == b[i-1] ? 2 : 1);
        else cnt *= ( a[i-1] == b[i-1] ? 2 : 3);
        cnt %= mod;
    }
    cout << cnt << endl;
    return 0;
}

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

#define MAX (10000)
#define INFTY (1<<29)

class DisjoinSet {
public:
    vector<int> rank, p;

    DisjoinSet() {}
    DisjoinSet(int size) {
        rank.resize(size, 0);
        p.resize(size, 0);
        for (int i = 0; i < size; i++)makeSet(i);
    }

    void makeSet(int x) {
        p[x] = x;
        rank[x] = 0;
    }

    bool same(int x, int y) {
        return findSet(x) == findSet(y);
    }

    void unite(int x, int y) {
        link(findSet(x), findSet(y));
    }

    void link(int x, int y) {
        if (rank[x] > rank[y]) {
            p[y] = x;
        }
        else {
            p[x] = y;
            if (rank[x] == rank[y]) {
                rank[y]++;
            }
        }
    }

    int findSet(int x) {
        if (x != p[x]) {
            p[x] = findSet(p[x]);
        }
        return p[x];
    }
};


class Edge{
    public:
    int source,target,cost;
    Edge(int source=0,int target=0,int cost=0):
    source(source),target(target),cost(cost){}
    bool operator<(const Edge &e)const{
        return cost<e.cost;
    }
};

int kruskal(int N,vector<Edge> edges){
    int totalCost=0;
    sort(edges.begin(),edges.end());
    DisjoinSet dest =DisjoinSet(N+1);
    
    for(int i=0;i<N;i++)dest.makeSet(i);

    for(int i=0;i<edges.size();i++){
        Edge e=edges[i];
        if(!dest.same(e.source,e.target)){
            totalCost+=e.cost;
            dest.unite(e.source,e.target);
        }
    }
    return totalCost;
}

int main(void) {
    int N,M,cost;
    int source,target;
    cin >> N >> M;
    vector<Edge> edges;
    for(int i=0;i<M;i++){
        cin>>source>>target>>cost;
        edges.push_back(Edge(source,target,cost));
    }
    cout<<kruskal(N,edges)<<endl;
    return 0;
}



Measured memory_bytes: 5440
#include <iostream>
#include <vector>
#include <array>

using namespace std;
typedef long long ll;
#define REP(i,n) for (ll i = 0; i < (n); ++i)


struct mint{
    static const long long MOD = 1000000007;

    long long v;

    mint() : v(0) {}
    mint(long long x){
        x = x % MOD;
        if(x < 0){ x += MOD; }
        v = x;
    }
    mint& operator+=(mint a){
        v += a.v;
        if(v >= MOD){ v -= MOD; }
        return *this;
    }
    mint& operator*=(mint a){
        v *= a.v;
        v %= MOD;
        return *this;
    }
    mint& operator-=(mint a){
        v -= a.v;
        if(v < 0){ v += MOD; }
        return *this;
    }
    mint& operator/=(mint a){
        return (*this) *= a.inv();
    }

    mint operator*(mint a) const{
        return mint(v) *= a;
    }

    mint operator+(mint a) const {
        return mint(v) += a;
    }

    mint operator-(mint a) const {
        return mint(v) -= a;
    }

    mint operator/(mint a) const {
        return mint(v) /= a;
    }

    mint pow(long long k) const {
        mint res(1),tmp(v);
        while(k){
            if(k&1) res *= tmp;
            tmp *= tmp;
            k >>= 1;
        }
        return res;
    }
    mint inv(){return pow(MOD - 2); }

    static mint comb(long long n, int k){
        mint res(1);
        for(int i = 0; i < k; ++i){
            res *= mint(n - i);
            res /= mint(i + 1);
        }
        return res;
    }

    static mint factorial(long long n){
        mint res(1);
        for(int i = n; i > 1; --i){
            res *= mint(i);
        }
        return res;
    }

    bool operator<(const mint &a) const {
        return v < a.v;
    };
};

mint operator*(long long l, mint r){ return r * l; }

std::ostream& operator<<(std::ostream& stream, const mint& m){
    stream << m.v;
    return stream;
}

ll num_bits(ll x){
    ll ret = 0;
    for(ret = 0; x > 0; ret++, x /= 2){}
    return ret;
}

int main(){
    ll n;
    cin >> n;

    const ll nb = num_bits(n);
    vector<array<mint, 3>> dp(nb);
    if((n >> (nb - 1)) & 1){
        dp.at(nb - 1).at(0) = 1;
        dp.at(nb - 1).at(1) = 1;
    }else{
        dp.at(nb - 1).at(0) = 1;
        dp.at(nb - 1).at(1) = 0;
    }
    dp.at(nb - 1).at(2) = 0;

    for(ll i = nb - 2; i >= 0; --i){
        if((n >> i) & 1){
            dp.at(i).at(0) = dp.at(i + 1).at(0);
            dp.at(i).at(1) = dp.at(i + 1).at(0) + dp.at(i + 1).at(1);
            dp.at(i).at(2) = 2 * dp.at(i + 1).at(1) + 3 * dp.at(i + 1).at(2);
        }else{
            dp.at(i).at(0) = dp.at(i + 1).at(0) + dp.at(i + 1).at(1);
            dp.at(i).at(1) = dp.at(i + 1).at(1);
            dp.at(i).at(2) = dp.at(i + 1).at(1) + 3 * dp.at(i + 1).at(2);
        }
    }
    cout << dp.at(0).at(0) + dp.at(0).at(1) + dp.at(0).at(2) << endl;
    return 0;
}


Measured memory_bytes: 888
import java.io.PrintWriter;
import java.util.LinkedList;
import java.util.Scanner;
import static java.lang.Math.*;

public class Main {

	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);

		MainLoop : while(true){
			String text = scan.next();
			int len = text.length();
			int n = wormToInt(text);
			if(n==-1) break;
			boolean[] pattern = new boolean[(int)pow(3,len)];
			LinkedList<int[]> que = new LinkedList<int[]>();
			que.offer(new int[]{n,0});

			while(!que.isEmpty()){
				int[] ary = que.poll();
				int worm = ary[0],cnt = ary[1];

				if(pattern[worm]) continue;
				pattern[worm]=true;

				if(monotonous(worm,len)){
					out.println(cnt);
					continue MainLoop;
				}

				for (int i = 0; i < len-1; i++) {
					if(worm/(int)pow(3,i)%3!=worm/(int)pow(3,i+1)%3){
						for (int j = 0; j < 3 ; j++) {
							if(worm/(int)pow(3,i)%3!=j && worm/(int)pow(3,i+1)%3!=j) que.offer(new int[]{change(worm,i+1,i,j),cnt+1});
						}
					}
				}
			}

			out.println("NA");
		}

		out.flush();
	}

	static int change(int w,int p1,int p2,int color){
		int a = (int)pow(3,p1+1);
		int b = (int)pow(3,p2);
		return w/a*a+w%b+color*(int)(pow(3,p1)+pow(3,p2));
	}

	static boolean monotonous(int w,int len){
		int color = w%3;
		for (int i = 1; i < len; i++) {
			if(color!=w/(int)pow(3,i)%3) return false;
		}
		return true;
	}

	static int wormToInt(String w){
		if(w.equals("0")) return -1;
		int x=0;
		for (int i = w.length()-1; i >=0; i--) {
			switch(w.charAt(i)){
				case 'r' : x=x*3+0; break;
				case 'g' : x=x*3+1; break;
				case 'b' : x=x*3+2; break;
			}
		}
		return x;
	}
}

Measured memory_bytes: 54908
S = list(input())

num = [0]*26

num_A = ord("A")

for s in S:
    num[ord(s)-num_A] += 1

if num[ord(S[0])-num_A] == 1 or num[ord(S[1])-num_A] == 1 or num[ord(S[2])-num_A] == 1 or num[ord(S[3])-num_A] == 1:
    print("No")
elif num[ord(S[0])-num_A] == 4 or num[ord(S[1])-num_A] == 4 or num[ord(S[2])-num_A] == 4 or num[ord(S[3])-num_A] == 4:
    print("No")
else:
    print("Yes")
    

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

int main()
{
    int err;
    int N;
    struct INPUTDATA{
        double x;
        char u[4];
    };
    struct INPUTDATA *indata;
    int i;
    double j_sum, b_sum;
    double sum;

    err = scanf("%d", &N);

    indata = (struct INPUTDATA*)malloc(sizeof(struct INPUTDATA) * N);
    for(i=0;i<N;i++){
        err = scanf("%lf %s", &indata[i].x, (char*)&indata[i].u);
    }

    sum = 0;
    j_sum = b_sum = 0;
    for(i=0;i<N;i++){
        //printf("%lf %s\n", indata[i].x, indata[i].u);
        sum += indata[i].x;
        if( indata[i].u[0] == 'J'){
            j_sum += indata[i].x;
        }else if( indata[i].u[0] == 'B'){
            b_sum += indata[i].x * 380000.0;
        }
    }
    sum = j_sum + b_sum;
//    printf("%lf, %lf", j_sum, b_sum);

    printf("%lf", sum);


    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int a[20000000];
int main(int argc, char const *argv[]) {
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  for (int i = 0; i < n; i++)
    cin >> a[i];
  sort(a, a + n);
  cout << a[0];
  for (int i = 1; i < n; i++)
    cout << " " << a[i];
  cout << endl;
  return 0;
}



Measured memory_bytes: 10996
#include <iostream>
#include <cmath>
#include <string>
#include <numeric>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <limits>
using namespace std;
#define MOD 1000000007
#define INF 1000000009
#define ll long long
#define rep(i_, start, end) for(ll i_=(ll)start; i_<(ll)end; i_++)
#define print(a) cout << a << endl;
#define printarray(a, len) rep(ii,0,len) cout << a[ii] << " ";
#define printarray2(aa, len) rep(ij,0,len) printarray(aa[ij], aa[ij].size()); print("");
 
int main(){
  ll n;
  cin >> n;
  ll N = 100003;
  vector<ll> is_prime;
  vector<ll> prime_list;
  rep(i, 0, N+1){
    is_prime.push_back(1);
  }
  for(ll i=2; i <= N; i++){
    if(is_prime[i] == 1){
      for (ll num = i * 2; num <= N; num += i){
        is_prime[num] = 0;
      }
      prime_list.push_back(i);
      if (i >= n) break;
    }
  }
  print(prime_list[ prime_list.size() - 1 ]);
  
  return 0;
}

Measured memory_bytes: 1400
#include <bits/stdc++.h>
#define rep(i,s,n) for(int i=s;i<n;i++)
#define pb push_back
#define all(x) (x).begin(),(x).end()
using namespace std;
using P=pair<int,int>;
using G=vector<vector<int>>;
using ll=long long;
ll N;

const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
int n,m;
int ans=0;

vector<vector<int>> grid;
vector<ll> H, S;
vector<bool> seen;
vector<ll>sum;
vector<int> pl;

int main(int argc, char **argv){
	int n; cin>>n;
	vector<ll> x(n);
	rep(i,0,n) cin>>x[i];

	vector<ll> x2(n); x2=x;

	sort(all(x2));

	ll m1,m2;
	m1=x2[n/2 -1]; m2=x2[n/2];

	rep(i,0,n){
		if(x[i]<=m1) cout<<m2<<endl;
		else cout<<m1<<endl;
	}
}


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

int main()
{

int N;cin>> N;
int Tab[N];
for(int i=0;i<N;i++)
    cin >> Tab[i];
int DP[N];
DP[0]=0;
DP[1]=abs(Tab[0]-Tab[1]);

for(int i=2;i<N;i++)
    DP[i]=min(DP[i-2]+abs(Tab[i-2]-Tab[i]), DP[i-1]+abs(Tab[i-1]-Tab[i]) );

cout<<DP[N-1];
}

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

int32_t main() {

	int k; cin >> k;

	int r = 7;

	set<int> rem;
	int i = 1;
	while(true) {

		if(r % k == 0) {
			cout << i << endl;
			break;
		}

		r = r % k;

		if(rem.find(r) == rem.end()) {
			rem.insert(r);
			r = r * 10 + 7;
		}

		else {
			cout << -1 << endl;
			break;
		}

		i ++;
	}

}

Measured memory_bytes: 50496
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

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

    vector<int> dp(n, 1e9);
    dp[0] = 0;
    for(int i = 0; i < n; i++)
    {
        if(i + 1 < n)
            dp[i + 1] = min(dp[i + 1], dp[i] + abs(h[i] - h[i + 1]));
        if(i + 2 < n)
            dp[i + 2] = min(dp[i + 2], dp[i] + abs(h[i] - h[i + 2]));
    }

    cout << dp[n - 1];

    return 0;
}


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

int main()
{
    int n,k;
    cin>>n>>k;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    sort(a,a+n);
    ll s=0;
    for(int i=0;i<n-k;i++)
    {
        s+=(ll)a[i];
    }
    cout<<s;
    return 0;
}


Measured memory_bytes: 1024
#include<iostream>
#include<string>
using namespace std;
int main()
{
    string s,p;
    cin>>s>>p;
    bool a=false;
    for(int i=0;i<s.size();i++){
        int count=0;
        for(int j=0;j<p.size();j++){
            if(s[(i+j)%s.size()]==p[j%p.size()])
                count++;
        }
        if(count==p.size())
            a=true;
    }
    if(a==true)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 3164
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
 
using namespace std;
using ll = long long;
using P = pair<int, int>;
 
int main() {
    int a,b,c;
    cin >> a >> b >> c;
    if(a < b && b < c){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
}



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

#ifdef _PRINTDEBUG
  #include "lib/printdebug.hpp"
#else
  #define printdebug(...) 1
#endif
#define MOD_1_000_000_007 (1000000007LL)
#define LINF (1LL<<60)
#define rep(i, n)   for (long long i = 0; i <  (long long)(n); i++)
#define rep1(i, n)  for (long long i = 1; i <  (long long)(n); i++)
#define rep2(i, n)  for (long long i = 2; i <  (long long)(n); i++)
#define rep0c(i, n) for (long long i = 0; i <= (long long)(n); i++)
#define rep1c(i, n) for (long long i = 1; i <= (long long)(n); i++)
#define rep2c(i, n) for (long long i = 2; i <= (long long)(n); i++)
#define repc0(n, i) for (long long i = (long long)(n); i >= 0; i--)
#define repc1(n, i) for (long long i = (long long)(n); i >= 1; i--)
#define repc2(n, i) for (long long i = (long long)(n); i >= 2; i--)
#define REP(i, n, m) for (long long i = (long long)(n); i < (long long)(m); i++)

namespace solver {
  using namespace std;
  typedef long long ll;

  ll K;

  void init() {
    scanf("%lld", &K);
  }

  void solve() {
    queue<ll> que;
    rep(i, 9) que.push(i+1);
    ll ans = 0;
    rep(k, K) {
      ans = que.front(); que.pop();
      if(ans%10 != 0) que.push(10*ans+ans%10-1);
      que.push(10*ans+ans%10);
      if(ans%10 != 9) que.push(10*ans+ans%10+1);
    }
    cout << ans << endl;
  }
}

int main() {
  solver::init();
  solver::solve();
  return 0;
}

Measured memory_bytes: 1792
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String S = sc.next();
		sc.close();
		
		int minDiff = 1000;
		for(int i = 0;i <= S.length()-3;++i) {
			int cap = Math.abs(753 - Integer.parseInt(S.substring(i, i+3)));
			if(minDiff > cap) {
				minDiff = cap;
			}
		}
		
		System.out.println(minDiff);
	}
}


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

namespace AtCorder
{
	public class Program
	{
		/// <summary>
		/// ABC 102
		/// </summary>
		public static void Main()
		{
			var n = int.Parse(ReadLine());
			int answer = n;
			if(n % 2 == 1)
			{
				answer = 2 * n;
			}
			WriteLine(answer);
		}
	}
}


Measured memory_bytes: 13140
n,x=map(int,input().split())

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

al.sort()

count=0

for i in range(n) :
  d=x-al[i]
  if d<0 :
    break
  
  if i==n-1 and d>0 :
    break
  
  x=x-al[i]
  #print(x)
  count+=1
print(count)

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

int main() {

  int N = 0;
  cin >> N;
  int M = 0, P = 0;
  M = N - N / 100 * 100; 
  P = M - M / 10 * 10;
  
  if(N / 100 == 7){
    cout << "Yes" << endl;
  }
  
  else if(M / 10 == 7){
    cout << "Yes" << endl;
  }
  
  else if(P == 7){
    cout << "Yes" << endl;
  }
  
  else{
    cout << "No" << endl;
  }

}


Measured memory_bytes: 3592
#include <stdio.h>

int gojo(int, int);

int main(int argc, char const *argv[]) {
  int N, X, x[100001], ans = 0;
  scanf("%d%d", &N, &X);
  for (int i = 0; i < N; i++) {
    scanf("%d", &x[i]);
    x[i] -= X;
    if (x[i] < 0) x[i] *= -1;
    if (ans < x[i]) ans = x[i];
  }

  for (int i = 0; i < N; i++) {
    if (x[i] == 0) continue;
    ans = gojo(ans, x[i]);
  }

  printf("%d", ans);

  return 0;
}

int gojo(int x, int y) {
  int temp;
  while (y != 0) {
    temp = x;
    x = y;
    y = temp % y;
  }
  return x;
}

Measured memory_bytes: 512
S = input()
N = int(len(S))
a = 0
for i in range(0,int((N-1)/2)):
    if S[i] == S[-i-1]:
        a += 1
        
left = []
for i in range(0,int((N-1)/2)):
  left += S[i]
for i in range(0,int((N-1)/4)):
    if left[i] == left[-i-1]:
        a += 1

right = []
for i in range(0,int((N-1)/2)):
  right += S[-i-1]
for i in range(0,int((N-1)/4)):
    if right[i] == right[-i-1]:
        a += 1

if a == int((N-1)/2) + int((N-1)//4 * 2):
	print('Yes')
else :
    print('No')

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace __gnu_pbds;
using namespace std;

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

typedef tree <ll, null_type, less <ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
// order_of_key(val): returns the number of values less than val
// find_by_order(k): returns an iterator to the kth largest element (0-based)

#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
#define sz(a) (ll)(a.size())
#define endl "\n"

template <class Ch, class Tr, class Container>
basic_ostream <Ch, Tr> & operator << (basic_ostream <Ch, Tr> & os, Container const& x) 
{
    os << "{ ";
    for(auto& y : x) 
    {
        os << y << " ";
    }
    return os << "}";
}

template <class X, class Y>
ostream & operator << (ostream & os, pair <X, Y> const& p) 
{
    return os << "[" << p.ff << ", " << p.ss << "]";
}

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

    return gcd(b, a%b);
}

ll modexp(ll a, ll b, ll c)
{   
    a%=c;

    ll ans = 1;

    while(b)
    {
        if(b&1)
        {
            ans = (ans*a)%c;
        }

        a = (a*a)%c;
        b >>= 1;
    }

    return ans;
}

ll nxt()
{
    ll x;
    cin >> x;
    return x;
}

const ll L = 1e5+5;

void solve()
{
    ll n = nxt();
    basic_string <ll> h(n, 0);
    generate(all(h), nxt);

    vector <ll> dp(n, (ll)1e18);

    dp[0] = 0;
    for(ll i=0; i<n; i++)
    {
        if(i + 1 < n)
        {
            dp[i+1] = min(dp[i+1], dp[i] + abs(h[i+1] - h[i]));
        }

        if(i + 2 < n)
        {
            dp[i+2] = min(dp[i+2], dp[i] + abs(h[i+2] - h[i]));
        }
    }

    cout << dp[n-1] << endl;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    ll T = 1;
    // T = nxt();

    while(T--)
    {
        solve();
    }

    return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <cstdint>
#include <unordered_map>
#include <algorithm>

// by noshi91
template <std::uint_fast64_t Modulus> class modint {
    using u64 = std::uint_fast64_t;

public:
    u64 a;

    constexpr modint(const u64 x = 0) noexcept : a(x% Modulus) {}
    constexpr u64& value() noexcept { return a; }
    constexpr const u64& value() const noexcept { return a; }
    constexpr modint operator+(const modint rhs) const noexcept {
        return modint(*this) += rhs;
    }
    constexpr modint operator-(const modint rhs) const noexcept {
        return modint(*this) -= rhs;
    }
    constexpr modint operator*(const modint rhs) const noexcept {
        return modint(*this) *= rhs;
    }
    constexpr modint operator/(const modint rhs) const noexcept {
        return modint(*this) /= rhs;
    }
    constexpr modint& operator+=(const modint rhs) noexcept {
        a += rhs.a;
        if (a >= Modulus) {
            a -= Modulus;
        }
        return *this;
    }
    constexpr modint& operator-=(const modint rhs) noexcept {
        if (a < rhs.a) {
            a += Modulus;
        }
        a -= rhs.a;
        return *this;
    }
    constexpr modint& operator*=(const modint rhs) noexcept {
        a = a * rhs.a % Modulus;
        return *this;
    }
    constexpr modint& operator/=(modint rhs) noexcept {
        u64 exp = Modulus - 2;
        while (exp) {
            if (exp % 2) {
                *this *= rhs;
            }
            rhs *= rhs;
            exp /= 2;
        }
        return *this;
    }
};

using Mint = modint<(int)1e9 + 7>;

int main() {
	int n;
	std::cin >> n;

    std::vector<int> a(n);
    for (auto&& e : a)
        std::cin >> e;

    std::unordered_map<int, int> factor;
    for (auto&& e : a) {
        int x = e;

        for (int i = 2; i * i <= e; ++i) {
            int cnt = 0;

            while (x % i == 0) {
                x /= i;
                ++cnt;
            }

            if (cnt != 0)
                factor[i] = std::max(cnt, factor[i]);
        }

        if (x != 1)
            factor[x] = std::max(factor[x], 1);
    }

    Mint lcm = 1;
    for (auto&& p : factor)
        for (int i = 0; i < p.second; ++i)
            lcm *= p.first;

    Mint ans = 0;
    for (auto&& e : a)
        ans += lcm / e;

    std::cout << ans.a << std::endl;
}

Measured memory_bytes: 768
def gcd(a, b):
	if b == 0:
		return 1
	_max = max(a, b)
	_min = min(a, b)
	rest = _max % _min
	if rest == 0:
		return _min
	else:
		return gcd(_min, rest)

N, X = map(int, raw_input().split())
x = map(int, raw_input().split())
x.sort()
	
for i in range(N):
	if X < x[i]:
		x.insert(i, X)
		break
if len(x) == N:
	x.append(X)
diff = []
for i in range(N):
	d = abs(x[i] - x[i+1])
	diff.append(d)

res = diff[0]
for i in range(N - 1):
	res = gcd(res, diff[i + 1])
print res



Measured memory_bytes: 12216
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int a = Integer.parseInt(sc.next());
        int b = Integer.parseInt(sc.next());
        // aとbの積が偶数なら"Even"、奇数なら"Odd"
        if(a * b % 2 == 0){
            System.out.println("Even");
        }else{
            System.out.println("Odd");
        }
    }
}


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

using namespace std;

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

    int ans = T.size();
    for(int i=0; i<S.size()-T.size()+1;i++)
    {
        int diff=0;
        for(int j=0; j<T.size(); j++)
        {
            if(S[i+j]!=T[j]) diff++;
        }
        ans = min(ans, diff);
    }
    cout << ans << endl;

    return 0;
}

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

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

  vector<int> buka(N + 1, 0);
  for (int i = 2; i <= N; i++) {
    int A;
    cin >> A;
    buka[A]++;
  }

  for (int i = 1; i <= N; i++) {
    cout << buka[i] << endl;
  }

  return 0;
}


Measured memory_bytes: 4052
#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;
char s[105][105];
int n, m, flag;
int cnt[30];
int main() {
	while(scanf("%d%d", &n, &m) != EOF) 
	{
		flag = 0;
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				scanf(" %1c", &s[i][j]);
				cnt[s[i][j] - 'a']++;
			}
		}
		for(int i = 0; i < n; i++)
			for(int j = 0; j < m; j++)s[i][j] = ' ';
		for(int i = 0; i < n / 2; i++) {
			for(int j = 0; j < m / 2; j++) {
				int pos = -1;
				for(int k = 0; k <= 25; k++) {
					if(cnt[k] >= 4) {
						pos = k, cnt[k] -= 4;
						break;
					}
				}
				if(pos == -1)continue;
				s[i][j] = pos + 'a';
				s[n - i - 1][j] = pos + 'a';
				s[i][m - j - 1] = pos + 'a';
				s[n - i - 1][m - j - 1] = pos + 'a';
			}
		}
		if(n & 1) {
			for(int i = 0; i < m / 2; i++) {
				int pos = -1;
				for(int k = 0; k <= 25; k++) {
					if(cnt[k] >= 2) {
						pos = k, cnt[k] -= 2;
						break;
					}
				}
				if(pos == -1)continue;
				s[n / 2][i] = pos + 'a';
				s[n / 2][m - i - 1] = pos + 'a';
			}
		}
		if(m & 1) {
			for(int i = 0; i < n / 2; i++) {
				int pos = -1;
				for(int k = 0; k <= 25; k++) {
					if(cnt[k] >= 2) {
						pos = k, cnt[k] -= 2;
						break;
					}
				}
				if(pos == -1)continue;
				s[i][m / 2] = pos + 'a';
				s[n - i - 1][m / 2] = pos + 'a';
			}
		}
		int pos = 0;
		for(int i = 0; i <= 25; i++)if(cnt[i])pos = i;
		if(n & 1 && m & 1)s[n / 2][m / 2] = pos + 'a';
		for(int i = 0; i <= n / 2; i++) {
			for(int j = 0; j <= m / 2; j++) {
				if(s[i][j] == ' ' || s[i][m - j - 1] == ' ' || s[n - i - 1][m - j - 1] == ' ' || s[n - i - 1][j] == ' ') {
					flag = 1;
					break;
				}
				else if(s[i][j] != s[i][m - j - 1] || s[i][j] != s[n - i - 1][j] || s[n - i - 1][j] != s[n - i - 1][m - j - 1] || s[i][m - j - 1] != s[n - i - 1][m - j - 1]) {
					flag = 1;
				}
			}
		}
		if(flag)printf("No\n");
		else printf("Yes\n");
		memset(cnt, 0, sizeof(cnt));
	}
	return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		new Main().run();
	}
	void run(){
		Scanner sc = new Scanner(System.in);
		while(true){
			int b = sc.nextInt();
			if(b == 0){
				//System.out.println("break");
				break;
			}
			int[] a = new int[b];
			int left,right,searchvalue;
			for(int i=0; i < a.length; i++){
				a[i] = sc.nextInt();
			}
			searchvalue = sc.nextInt();
			left = 0; right = a.length-1;
			System.out.println(solve(left, right, searchvalue, a));
		}
	}

	int solve(int left, int right,int sv,int[] a){
		int index = (left + right) / 2;
		int cnt;
		//System.out.println("left:"+left+" right:"+right+" sv:"+sv+" a[index]:"+a[index]);
		if(a[index] == sv){
			return 1;
		}else if(left > right){
			return 0;
		}else if(a[index] < sv){
			left = index;
			return 1 + solve(++left, right, sv, a);
		}else if(a[index] > sv){
			right = index;
			return 1 + solve(left, --right, sv, a);			
		}
		return 0;
		
		/*
		if(cnt == a.length-1){
			System.out.println(cnt);
			return;
		}
		if(a[(left + right) / 2] < sv){
			System.out.println("left:"+left+" right:"+right);
			if(left <= right){
				left = (left + right) / 2 + 1;
				solve(left, right,sv, a, ++cnt);
			}else{
				System.out.println(++cnt);
			}
		}else if(a[(left + right) / 2] > sv){
			System.out.println("left:"+left+" right:"+right);
			if(left < right){
				right = (left + right) / 2 - 1;
				solve(left, right,sv, a, ++cnt);
			}else{
				System.out.println(++cnt);
			}
		}else{
			System.out.println(++cnt);
		}
		*/
	}
}

Measured memory_bytes: 20340
import java.math.BigInteger;
import java.util.*;

public class Main {
    static int primeCounter = 0;

    public static void main(String args[]) {
        // input

        int numEl;

        Scanner inp = new Scanner(System.in);

        numEl = inp.nextInt();

        for (int i = 0; i < numEl; i++) {
            BigInteger input = new BigInteger(inp.next());

            if (input.isProbablePrime(5)) {
                primeCounter++;
            }
        }

        System.out.println(primeCounter);
    }
}


Measured memory_bytes: 50944
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a; i< (int)(b); ++i)
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
typedef long double ld;
using ll=long long;
using namespace std;
const auto mod=1e9+7;


int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(20);
  
  int n,m; cin >> n >> m;
  int ma=0, mi=mod;
  rep(i,0,m) {
  	int l,r; cin >> l >> r;
  	ma=max(ma,l);
  	mi=min(mi,r);
  }
  if(mi>=ma)cout << (mi-ma+1) << endl;
  else cout << 0 << endl;
 }

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

int main(int argc, char const* argv[])
{
  int n, y;
  std::cin >> n >> y;

  for (int i = 0; i <= n; ++i) {
    for (int j = 0; j <= n - i; ++j) {
      int k = n - i - j;
      if (i * 10000 + j * 5000 + k * 1000 == y) {
        std::cout << i << " " << j << " " << k << std::endl;
        return 0;
      }
    }
  }

  std::cout << "-1 -1 -1" << std::endl;
  return 0;
}

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

class Program
{
    static void Main(string[] args)
    {
        var num = ToInt32(ReadLine());
        var ar = Array.ConvertAll(ReadLine().Split(' '), int.Parse);
        var sum = new long[num+1];
        sum[0] = 0;
        var dic = new Dictionary<long, long> { [0] = 1 };
        for(var i = 1; i <= num; i++)
        {
            sum[i] = sum[i - 1] + ar[i-1];
            if (dic.ContainsKey(sum[i])) dic[sum[i]]++;
            else dic[sum[i]] = 1;
        }
        var result = 0L;
        foreach(var d in dic.Values)
        {
            result += Calculation.Combination(d, 2);
        }
        WriteLine(result);
    }

    private const string ALFA = "abcdefghijklmnopqrstuvwxyz";
    private const int MOD = 1000000007;
}

public class Calculation
{
  
    public static long Combination(long num1, long num2)
    {
        if (num1 < num2) return 0;
        var p1 = num1;
        var p2 = num2;
        for (long i = 1; i < num2; i++)
        {
            p1 *= num1 - i;
            p2 *= num2 - i;
        }
        return p1 / p2;
    }
}

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

int main() {
    char a,b;
    cin >> a >> b;
    if ((a == 'H' and b == 'H') || (a == 'D' and b == 'D')) {
        cout << 'H' << endl;
    }
    else {
        cout << 'D' << endl;
    }
}

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

vector<size_t> vUnique(vector<size_t> vec){
  std::sort(vec.begin(), vec.end());
  vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
  return vec;
}

int main() {
  size_t N,Q;
  size_t A[100000 + 1];
  vector<size_t>Alist;
  for(int i = 0;i < 100000 + 1;++i){
    A[i] = 0;
  }
  
  cin >> N;
  for(size_t i = 0;i < N;++i){
    size_t t;
    cin >> t;
    A[t]++;
    Alist.push_back(t);
  }
  Alist = vUnique(Alist);
  
  size_t sum = 0;
  for(size_t j = 0;j < Alist.size();++j){
    sum += A[Alist[j]] * Alist[j];
  }

  
  cin >> Q;
  for(size_t i = 0;i < Q;++i){
    size_t b,c;
	cin >> b;
    cin >> c;
    A[c] += A[b];
    sum += A[b] * (c - b);
    A[b] = 0;
    cout << sum << endl;
  }
}


Measured memory_bytes: 5584
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;
namespace mp = boost::multiprecision;
#define ll long long
#define cpp mp::cpp_int
#define rep(i, n) for(int i = 0; i < n; i++)
#define rrep(i, n) for(int i = 1; i <= n; i++)
#define drep(i, n) for(int i = n-1; i >= 0; i--)
#define srep(i, s, t) for (int i = s; i < t; i++)
#define vi vector<int>
#define P pair<ll, ll>
int mod = 1'000'000'000 + 7;
struct edge {
    int to;
    ll cost;
};

void COME_LET_THE_GAMES_BEGIN() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << setprecision(20);
}

int main() {
    COME_LET_THE_GAMES_BEGIN();
    int N;
    cin >> N;
    vector<vector<P>> G(N);
    for (int i = 0; i < N - 1; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        G[u].push_back(P(v, w));
        G[v].push_back(P(u, w));
    }
    vector<ll> d(N, LLONG_MAX);
    d[0] = 0;
    priority_queue<P > q;
    q.push(P(-d[0], 0));
    while (q.size()) {
        P p = q.top();
        q.pop();
        p.first = -p.first;
        if (p.first > d[p.second])continue;
        for (auto z:G[p.second]) {
            if (d[z.first] > p.first + z.second) {
                d[z.first] = p.first + z.second;
                q.push(P(-d[z.first], z.first));
            }
        }
    }
    for (int i = 0; i < N; i++) {
        cout << (d[i] & 1) << endl;
    }
}

Measured memory_bytes: 8704
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;

#define big ((ll)(1e9) + 7)

int main()
{
  int n;
  cin >> n;
  string s;
  cin >> s;
  ll r, g, b;
  r = 0;
  g = 0;
  b = 0;
  for (int i = 0; i < n; i++)
  {
    if (s.at(i) == 'R')
      r++;
    else if (s.at(i) == 'G')
      g++;
    else
      b++;
  }

  ll count = r*g*b;

  for (int i = 0; i < n; i++)
  {
    for (int j = i + 1; j < n; j++)
    {
      if (s.at(i) == s.at(j))
      {
        continue;
      }
      int k =2*j-i;
      if (k >= n)
      {
        break;
      }
      if ((s.at(i) != s.at(k)) && (s.at(j) != s.at(k)))
      {
        count--;
      }
    }
  }

  cout << count << endl;
  return 0;
}


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

using pii = pair<int, int>;

// 1-indexed
class rolling_hash {
public:
    rolling_hash(std::string const& s)
        : n(s.size()),
          mod({999999937LL, 1000000007LL})
    {
        for(int i = 0; i < 2; ++i) {
            hs[i].resize(n + 1);
            p[i].resize(n + 1);
            hs[i][0] = 0;
            p[i][0] = 1;
            for(int j = 0; j < n; ++j) {
                hs[i][j + 1] = (hs[i][j] * base + s[j]) % mod[i];
                p[i][j + 1] = p[i][j] * base % mod[i];
            }
        }
    }

    // s[i...]
    long long query(int idx, int i) const {
        return hs[i][idx];
    }
    // s[l + 1...r]
    long long query(int l, int r, int i) const {
        return ((hs[i][r] - hs[i][l] * p[i][r - l]) % mod[i] + mod[i]) % mod[i];
    }

    long long query(int l, int r, int idx, char before, char after) {
        long long res = query(l, r, 0);
        if(idx <= l || r < idx) {
            return res;
        }
        res = (res - (before - after) * p[0][r - idx]) % mod[0];
        res = (res + mod[0]) % mod[0];
        return res;
    }

private:
    int n;
    std::vector<long long> hs[2];
    std::vector<long long> p[2];

    const std::array<long long, 2> mod;
    static const long long base = 29LL;
};


int main() {
    string S;
    cin >> S;
    rolling_hash hs(S);
    int Q;
    cin >> Q;
    while(Q--) {
        int l, r, t;
        cin >> l >> r >> t;
        if(hs.query(l - 1, r - t, 0) == hs.query(l + t - 1, r, 0)) {
            cout << "Yes" << endl;
        } else {
            int lb = 0, ub = r - l + 1 - t;
            while(ub - lb > 1) {
                int m = (lb + ub) / 2;
                if(hs.query(l - 1 + m, r - t, 0) != hs.query(l + t - 1 + m, r, 0)) {
                    lb = m;
                } else {
                    ub = m;
                }
            }

            char before1 = S[l + t - 1 + lb];
            char after1 = S[l - 1 + lb];
            char before2 = S[l - 1 + lb];
            char after2 = S[l - 1 + lb + t];
            if(hs.query(l + t - 1, r, l + t + lb, before1, after1) == hs.query(l - 1, r - t, l + t + lb, before1, after1)
                || hs.query(l + t - 1, r, l + lb, before2, after2) == hs.query(l - 1, r - t, l + lb, before2, after2)) {
                cout << "Yes" << endl;
            } else {
                cout << "No" << endl;
            }
            //cout << "bef1: " << before1 << " aft1: " << after1 << endl;
            //cout << "bef2: " << before2 << " aft2: " << after2 << endl;
            //cout << "idx1: " << l + t + lb << endl;
            //cout << "idx2: " << l + lb << endl;
        }
    }
}


Measured memory_bytes: 6372
blue={}
red={}
n=int(input())
for i in range(n):
    s=input()
    blue[s]=blue.get(s,0)+1
m=int(input())
for i in range(m):
    t=input()
    red[t]=red.get(t,0)+1

mx=0
for k,v in blue.items():
    mx=max(mx,blue[k]-red.get(k,0))
print(mx)


Measured memory_bytes: 8996
#include <algorithm>
#include <cstdlib>
#include<iostream>
#include<vector>
#include<map>
#include<cmath>
using namespace std;
int N;
bool is_ok(int N){
    for(int i_four=0;i_four<=25;i_four++){
        for(int i_seven=0;i_seven<=15;i_seven++){
            if(N==i_four*4+i_seven*7) return true;
        }
    }
    return false;
}
int main(int argc, char const *argv[])
{
    cin>>N;
    if(is_ok(N)){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        // write your code here

        Scanner sc = new Scanner(System.in);
        String[] s = sc.next().split("");

        for (int i = 0; i < s.length / 2; i++) {
            if (!s[i].equals(s[s.length - 1 - i])) {
                System.out.println("No");
                return;
            }
        }

        // 前半が回文

        for (int i = 0; i < s.length / 4; i++) {
            if (!s[i].equals(s[s.length / 2 - 1 - i])) {
                System.out.println("No");
                return;
            }
        }

        // 後半が回文

        for (int i = s.length / 2; i < s.length; i++) {
            if (!s[i].equals(s[s.length - 1 - i])) {
                System.out.println("No");
                return;
            }
        }

        System.out.println("Yes");
    }
}

Measured memory_bytes: 23764
D=Dict{Char,Int}()
N=parse(Int,readline())
for i=1:N
	s=readline()
	D[s[1]]=get(D,s[1],0)+1
end
ans=0
u=['M','A','R','C','H']
for a=u,b=u,c=u
	if a==b||b==c||c==a
		continue
	end
	ans+=get(D,a,0)*get(D,b,0)*get(D,c,0)
end
println(div(ans,6))


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

int main() {
  //clock_t start, end; //開始時刻・終了時刻
  //double req_time; //所要時間
  //start = clock();
  
  int N;
  vector<int> d;
  int ans;

  cin >> N;
  d.resize(N);
  for (int i=0; i<N; i++){
      cin >> d.at(i);
  }
  
  sort(d.begin(),d.end());
  d.erase(unique(d.begin(), d.end()), d.end());
  ans = d.size();
  cout << ans << endl;

  //end = clock();
  //req_time = (double)(end-start) / CLOCKS_PER_SEC;
  //cout << "Required Time : " << req_time << endl;
  }

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

using ll = long long;
using namespace std;

#define int ll

#define rep(i, a) for (int i = 0; (i) < (int) (a); (i)++)
#define reps(i, a, b) for (int i = (int) (a); (i) < (int) (b); (i)++)
#define rrep(i, a) for (int i = (int) a-1; (i) >= 0; (i)--)
#define rreps(i, a, b) for (int i = (int) (a)-1; (i) >= (int) (b); (i)--)
#define MP(a, b) make_pair((a), (b))
#define PB(a) push_back((a))
#define all(v) (v).begin(), (v).end()
#define PERM(v) next_permutation(all(v))
#define UNIQUE(v) sort(all(v));(v).erase(unique(all(v)), v.end())
#define CIN(type, x) type x;cin >> x
#define TRUE__  "Yes"
#define FALSE__ "No"
#define PRINT(f) if((f)){cout << (TRUE__) << endl;}else{cout << FALSE__ << endl;}
#define YES(f) if((f)){cout << "YES" << endl;}else{cout << "NO" << endl;}
#define Yes(f) if((f)){cout << "Yes" << endl;}else{cout << "No" << endl;}
#define MINV(v) min_element(all(v))
#define MAXV(v) max_element(all(v))
#define MIN3(a, b, c) min(min(a, b), c)
#define MIN4(a, b, c, d) min(MIN3(a, b, c), d)
#define MIN5(a, b, c, d, e) min(MIN4(a, b, c, d), e)
#define MIN6(a, b, c, d, e, f) min(MIN5(a, b, c, d, e), f)
#define MAX3(a, b, c) max(max(a, b), c)
#define MAX4(a, b, c, d) max(MAX3(a, b, c), d)
#define MAX5(a, b, c, d, e) max(MAX4(a, b, c, d), e)
#define MAX6(a, b, c, d, e, f) max(MAX5(a, b, c, d, e), f)
#define RANGE(a, b, c) ((a) <= (b) && (b) < (c))
#define RANGE2D(a, b, c, d, e, f) (RANGE((a), (c), (e)) && RANGE((b), (d), (f)))
#define chmin(a, b) a = min(a, (b))
#define chmin3(a, b, c) a = MIN3(a, (b), (c))
#define chmin4(a, b, c, d) a = MIN4(a, (b), (c), (d))
#define chmin5(a, b, c, d, e) a = MIN5(a, (b), (c), (d), (e))
#define chmin6(a, b, c, d, e, f) a = MIN6(a, (b), (c), (d), (e), (f))
#define chmax(a, b) a = max(a, (b))
#define chmax3(a, b, c) a = MAX3(a, (b), (c))
#define chmax4(a, b, c, d) a = MAX4(a, (b), (c), (d))
#define chmax5(a, b, c, d, e) a = MAX5(a, (b), (c), (d), (e))
#define chmax6(a, b, c, d, e, f) a = MAX6(a, (b), (c), (d), (e), (f))
#define fcout cout << fixed << setprecision(12)

#define RS resize
#define CINV(v, N) do {\
	v.RS(N);\
	rep(i, N) cin >> v[i];\
} while (0);

#define RCINV(v, N) do {\
	v.RS(N);\
	rrep(i, N) cin >> v[i];\
} while (0);
#define MOD 1000000007

template<class T>
inline T GET() {
	T x;
	cin >> x;
	return x;
}


void init();
void solve();

signed main()
{
	init();
	solve();
}

int A, B;
vector<vector<int>> v;

void init()
{
	cin >> A >> B;
	v.RS(100, vector<int>(100, 0));
	reps(i, 50, 100) {
		rep(j, 100) {
			v[i][j] = 1;
		}
	}
}

void solve()
{
	rep(i, A-1) {
		int c = 1 + (i % 23) * 2;
		int r = 51 + (i / 23) * 2;
		v[r][c] = 0;
	}
	rep(i, B-1) {
		int c = 1 + (i % 23) * 2;
		int r = 1 + (i / 23) * 2;
		v[r][c] = 1;
	}
	cout << "100 100" << endl;
	rep(i, 100) {
		rep(j, 100) {
			cout << (v[i][j] == 0 ? '.' : '#');
		}
		cout << endl;
	}
}




Measured memory_bytes: 384
#include <iostream>
using namespace std;
int main(void){
    int a, b;
    cin >> a >> b;
   if(a == 0){
       if(b == 100){
           cout << 101 << endl;
       }else{
           cout << b << endl;
       }
       
   }else if(a == 1){
       if(b == 100){
           cout << 101*b << endl;
       }else{
       cout << 100*b << endl;
       }
   }else{
       if(b == 100){
           cout << 1010000 << endl;
       }else{
           cout << 10000*b << endl;
       }
   }
}


Measured memory_bytes: 256