akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;


int main(void){
  int h,w,i,j;
  string g[1005];
  queue<P> q;
  
  cin >> h >> w;
  for (i=0;i<h;i++) cin >> g[i];
  
  for (i=0;i<h;i++) for (j=0;j<w;j++){
    if (g[i][j]=='#') q.push(P(i,j));
  }
  
  int qs,t=0,ni,nj;
  int di[4]={1,0,-1,0},dj[4]={0,1,0,-1};
  P p;
  while (q.size()>0){
    qs=q.size();
    
    for (i=0;i<qs;i++){
      p=q.front();
      q.pop();
      for (j=0;j<4;j++){
        ni=p.first+di[j];
        nj=p.second+dj[j];
        if (ni>=0 && ni<h && nj>=0 && nj<w && g[ni][nj]=='.'){
          g[ni][nj]='#';
          q.push(P(ni,nj));
        }
      }
    }
    
    t++;
    
  }
  
  cout << t-1 << endl;
  
  return 0;
}

Measured memory_bytes: 9488
# B - Collatz Problem

s = int(input())
a = [0]
a.append(s)

def f(n):
    if n%2 == 0:
        return n//2
    else:
        return 3*n + 1

i = 2
while True:
    a.append(f(a[i-1]))
    if a[-1] in a[:-1]:
        print(len(a)-1)
        break
    i += 1

Measured memory_bytes: 3060
n,q=map(int,input().split())
s=input()
a=[0]
for i in range(1,len(s)):
  a.append(a[i-1]+(s[i-1:i+1]=='AC'))
for i in range(q):
  l,r=map(int,input().split())
  print(a[r-1]-a[l-1])

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

int main() {
  string S;
  cin >> S;
  bool  b = true;
  for(int i = 0; i < S.size(); i++) {
    if(S.at(i) != S.at(S.size()-i-1)) {
      b = false;
    }
  }
  if(b) {
    cout << "Yes";
  }
  else {
    cout << "No";
  }
}


Measured memory_bytes: 256
/*
  AUTHOR:SOURABH
  CREATED:26:01:20
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ordered_set tree<ll , null_type, less< ll >, rb_tree_tag, tree_order_statistics_node_update>
#define ll long long int
#define ld long double
#define fi first
#define se second
#define pb push_back
#define pob pop_back
#define W while
#define fn(i,x) for(i=0;i<x;i++)
#define fs(i,s,x) for(i=s;i<x;i++)
#define fr(i,x) for(i=x;i>=0;i--)
#define fit(it,s) for(it=s.begin();it!=s.end();it++)
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vii vector<int>
#define vll vector<ll>
#define mii map<int,int>
#define mll map<ll,ll>
#define mod 1000000007
#define MAX 100005
#define M 32

using namespace std;
using namespace __gnu_pbds;

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

    //freopen("in.txt","r",stdin);
    //freopen(2 "out.txt","w",stdout);

    ll n,c=0;
    cin>>n;
    W(n)
    {
        c++;
        n/=2;
    }
    cout<<(ll)(pow(2,c)+.5)-1;
    return 0;
}





Measured memory_bytes: 512
n,k = gets.split.map(&:to_i)
rsp = gets.split.map(&:to_i)
t = gets.chomp

def point(x)
    if x == 'r'
        2
    elsif x == 's'
        0
    else
        1
    end
end

dp = Array.new(n,true)
ans = 0

0.upto(k-1) {|i| ans += rsp[point(t[i])]}

k.upto(n-1) do |i|
    if t[i] == t[i-k]
        if dp[i-k]
            dp[i] = false
        else
            ans += rsp[point(t[i])]
        end
    else
        ans += rsp[point(t[i])]
    end
end

p ans

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

string DIR = "RLUD";
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

int64_t chmax(int64_t& a, int64_t b){
    a = max(a, b);
}
int64_t chmin(int64_t& a, int64_t b){
    a = min(a, b);
}

int main(){
    int N;
    vector<int64_t> X[4], Y[4];
    cin >> N;
    for(int i=0; i<N; i++){
        int64_t x, y;
        char c;
        cin >> x >> y >> c;
        x *= 2;
        y *= 2;
        int d = DIR.find(c);
        X[d].push_back(x);
        Y[d].push_back(y);
    }
    vector<int64_t> xs[4], ys[4];
    for(int k=0; k<4; k++){
        if(X[k].size()){
            xs[k] = {*max_element(X[k].begin(), X[k].end()), *min_element(X[k].begin(), X[k].end())};
            ys[k] = {*max_element(Y[k].begin(), Y[k].end()), *min_element(Y[k].begin(), Y[k].end())};
        }else{
            xs[k] = {0, 0};
            ys[k] = {0, 0};
        }
    }

    vector<int64_t> cand;
    for(int k1=0; k1<4; k1++) for(int k2=0; k2<4; k2++){
        for(int64_t x1 : xs[k1]) for(int64_t x2 : xs[k2]){
            int64_t d = abs(x1-x2);
            cand.push_back(d);
            cand.push_back(d/2);
        }
        for(int64_t y1 : ys[k1]) for(int64_t y2 : ys[k2]){
            int64_t d = abs(y1-y2);
            cand.push_back(d);
            cand.push_back(d/2);
        }
    }

    const int64_t INF = 1e9;
    int64_t ans = 1e18;
    for(int64_t d : cand){
        int64_t xmax = -INF, ymax = -INF, xmin = INF, ymin = INF;
        for(int k=0; k<4; k++) for(int i=0; i<X[k].size(); i++){
            int64_t x = X[k][i] + dx[k] * d;
            int64_t y = Y[k][i] + dy[k] * d;
            chmax(xmax, x);
            chmin(xmin, x);
            chmax(ymax, y);
            chmin(ymin, y); 
        }
        int64_t res = (xmax-xmin) * (ymax-ymin);
        chmin(ans, res);
    }
    double Ans = (double) ans / 4;
    cout << fixed << setprecision(10) << Ans << endl;
    return 0;
}


Measured memory_bytes: 2256
// #include<iostream>
// #include<vector>
// #include<algorithm>
// #include<map>
// #include<cstring>
// #include<math.h>
// #include<bitset>
// #include<queue>
// #include<set>
// #include<iomanip>
// #include<math.h>
// #include<assert.h>
// #include<string>
// #include<cstdlib>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr ll INF = 1LL << 40;
const double INFD = 1e100;
const ll mod = 1000000007;
const double PI = 3.1415926535897932384626433832795028841971;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
// ----------------------------------------------------------------------------


int main(){
  int N,M,Q;
  cin >> N >> M >> Q;
  vector<int> L(200010),R(200010);
  vector<vector<int>> X(509, vector<int> (509,0));
  vector<vector<int>> C(509, vector<int> (509,0));
  for(int i=1; i<=M; i++){
    cin >> L[i] >> R[i];
    X[L[i]][R[i]]++;
  }
  for(int i=1; i<=N; i++){
    for(int j=1; j<=N; j++){
      C[i][j] = C[i][j-1] + X[i][j];
    }
  }
  for(int i=1; i<=Q; i++){
    int p,q;
    cin >> p >> q;
    int sum=0;
    for(int j=p; j<=q; j++){
      sum += C[j][q] - C[j][p-1];
    }
    cout << sum << endl;
  }
  return 0;
}


Measured memory_bytes: 4608
#include<stdio.h>
#include<string.h>
char X[1001], Y[1001];
int  c[1001][1001];
int m, n;
int LCSLength(void)
{
  int i, j;
  m = strlen(X);
  n = strlen(Y);
 
  for( i=1 ; i<=m ; i++ )
    c[i][0] = 0;
  for( j=0 ; j<n ; j++ )
    c[0][j] = 0;
  for( i=1 ; i<=m ; i++ ){
    for( j=1 ; j<=n ; j++ ){
      if(X[i-1]==Y[j-1])
    c[i][j] = c[i-1][j-1]+1;
      else if(c[i-1][j]>=c[i][j-1])
    c[i][j] = c[i-1][j];
      else
    c[i][j] = c[i][j-1];
    }
  }
  return c[i-1][j-1];
} 
int main()
{
  int a[150];
  int i, j, k, q;
  scanf("%d",&q);
  for( i=0 ; i<q ; i++ ){
    scanf("%s",X);
    scanf("%s",Y);
    LCSLength();
    a[i] = LCSLength();
  }
  for( i=0 ; i<q ; i++ ){
    printf("%d\n",a[i]);
  }
 
  return 0;
}

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

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

    int sub = a-b;
    int add = a+b;
    int mult = a*b;

    int intermediateMax = max(add,sub);
    int minimum = max(intermediateMax, mult);

    cout << minimum;
    return 0;
}

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

int mazak(string &s){
	int left = 0;
	int right = s.size()-1;
	int count =0;
	while(left<right){
		if(s[left]!=s[right])
			++count;
		++left; --right;
	}
	return count;
}

int main(){
	
	string a;
	cin>>a;
	cout<<mazak(a);
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
#define MAX 100000
typedef long long ll;

int n, k;
ll T[MAX];

// how many loads can k trucks carry , whose max capacity is P
int check(ll P)
{
    int i = 0;
    for (int j = 0; j < k; j++) {
        ll s = 0;
        while (s + T[i] <= P) {
            s += T[i];
            i++;
            if (i == n) return n;
        }
    }
    return i;
}

int solve()
{
    ll left = 0;
    ll right = 100000 * 10000;  // loads times load's max weight
    ll mid;
    while (right - left > 1) {
        mid = (left + right) / 2;
        int v = check(mid);  // determine mid == P and check the capacity
        if (v >= n) right = mid;
        else left = mid;
    }

    return right;
}

int main()
{
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> T[i];
    ll ans = solve();
    cout << ans << endl;
}


Measured memory_bytes: 3900
#include <iostream>
using namespace std;
int main(void){
   
   int t;
   int sum = 0;
   for(int i = 0; i < 4; i++){
       cin >> t;
       sum += t;
   }
   
   cout << sum / 60 << endl;
   cout << sum % 60 << endl;
    
}



Measured memory_bytes: 3092
fn read<T: std::str::FromStr>() -> T {
  let mut s = String::new();
  std::io::stdin().read_line(&mut s).ok();
  s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
  read::<String>().split_whitespace()
    .map(|e| e.parse().ok().unwrap()).collect()
}

fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
  (0..n).map(|_| read_vec()).collect()
}

pub trait LexicalPermutation {
  /// Return `true` if the slice was permuted, `false` if it is already
  /// at the last ordered permutation.
  fn next_permutation(&mut self) -> bool;
}
impl<T> LexicalPermutation for [T] where T: Ord {
  /// Original author in Rust: Thomas Backman <serenity@exscape.org>
  fn next_permutation(&mut self) -> bool {
    // These cases only have 1 permutation each, so we can't do anything.
    if self.len() < 2 { return false; }

    // Step 1: Identify the longest, rightmost weakly decreasing part of the vector
    let mut i = self.len() - 1;
    while i > 0 && self[i-1] >= self[i] {
      i -= 1;
    }

    // If that is the entire vector, this is the last-ordered permutation.
    if i == 0 {
      return false;
    }

    // Step 2: Find the rightmost element larger than the pivot (i-1)
    let mut j = self.len() - 1;
    while j >= i && self[j] <= self[i-1]  {
      j -= 1;
    }

    // Step 3: Swap that element with the pivot
    self.swap(j, i-1);

    // Step 4: Reverse the (previously) weakly decreasing part
    self[i..].reverse();

    true
  }
}
fn main() {
  let (n, m) = {
    let tmp: Vec<isize> = read_vec();
    (tmp[0], tmp[1])
  };
  let ans = combination(n, 2) + combination(m, 2);
  println!("{}", ans);
}

fn combination(n: isize, r: isize) -> isize {
  if n == 0 || n == 1 { 0 }
  else if r == 0 || r == n { 1 }
  else if r == 1 { n }
  else { combination(n-1, r-1) + combination(n-1, r) }
}

Measured memory_bytes: 4352
n = int(input())
A = [int(i) for i in input().split()]
B = []
if n%2:
	B = [A[n-1-2*i] for i in range(n//2)]
	B.append(A[0])
	B += [A[2*i+1] for i in range(n//2)]
else:
	B = [A[n-1-2*i] for i in range(n//2)]
	B += [A[2*i] for i in range(n//2)]
print(*B)


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

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
    }
    sort(v.begin(), v.end());
    double sum = v[0];
    for (int i = 1; i < n; i++)
    {
        sum =  (sum + v[i]) / 2;
    }
    
    cout << sum << endl;

    return 0;
}

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

using namespace std;

vector<string> ans;
int n,m;
string tostr(int num);

int main(){
	while(1){
		cin >> n >> m;
		if(n == 0 && m == 0) break;
		int nh[100],mh[100];
		int cn = -1,cm = -1;
		int sumn = 0,summ = 0;
		int sumc = 1000;
		for(int i = 0;i < n;i++){
			cin >> nh[i];
			sumn+=nh[i];
		}
		for(int i = 0;i < m;i++){
			cin >> mh[i];
			summ+=mh[i];
		}
		for(int i = 0;i < n;i++){
			for(int j = 0;j < m;j++){
				if((sumn - nh[i] + mh[j]) == (summ - mh[j] + nh[i]) && sumc > nh[i] + mh[j]){
					sumc = nh[i] + mh[j];
					cn = nh[i];
					cm = mh[j];
				}
			}
		}
		if(cn != -1){
			string ts;
			ts += tostr(cn);
			ts += ' ';
			ts += tostr(cm);
			ans.push_back(ts);
		}
		else{
			string ts;
			ts += "-1";
			ans.push_back(ts);
		}
	}
	for(int i = 0;i < ans.size();i++){
		cout << ans[i] << endl;
	}
}

string tostr(int num){
	string str;
	for(int i = num;i > 0;i=i/10){
		str += '0' + (i%10);
	}
	reverse(str.begin(),str.end());
	return str;
}

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

int main()
{
      char str[100];
      cin>>str;
      if(strcmp(str,"ABC")==0)
      {
      	cout<<"ARC"<<endl;
	  }
	  else{
	  	cout<<"ABC"<<endl;
	  }
	
	return 0;
}

Measured memory_bytes: 3592
import math

A,B=map(int,input().split())
ans=100000

for i in range(1,10000):
    a=math.floor(i*0.08)
    b=math.floor(i*0.1)
    if a==A and b==B:
        ans=i
        break
        
print(-1 if ans==100000 else ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18,MOD = 1e9 + 7;
const int INT_INF = 1e9,INT_MOD=1e9+7;
#define rep(i, N) for(int i = 0; i < N; i++)
typedef pair<int, int> Pi;
typedef pair<double, double> P;
signed main(){
    int n,k;cin>>n>>k;
    int ans=0,p;
    rep(i,n){
        cin>>p;
        if(p>=k) ans++;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define LOOP(n) for (int _i = 0; _i < (n); _i++)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define FOR(i, r, n) for (int i = (r); i < (n); ++i)
#define ALL(obj) begin(obj), end(obj)
using namespace std;
using ll = long long;
using ull = unsigned long long;

const int INF = 2100100100;
const int MOD = 1e9 + 7;

// 多次元 vector 生成
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}

int main() {
    // cin.tie(0);
    // ios::sync_with_stdio(false);
    string S;
    cin >> S;
    vector<int> num(4);
    REP(i, 4) { num[i] = S[i] - '0'; }

    REP(bit, 1 << 3) {
        int sum = num[0];
        REP(i, 3) {
            int mask = 1 << i;
            if (bit & mask) {
                sum += num[i + 1];
            } else {
                sum -= num[i + 1];
            }
        }
        if (sum == 7) {
            cout << num[0];
            REP(i, 3) {
                int mask = 1 << i;
                if (bit & mask) {
                    cout << "+" << num[i + 1];
                } else {
                    cout << "-" << num[i + 1];
                }
            }
            cout << "="
                 << "7" << endl;
            return 0;
        }
    }

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <climits>
#include <iomanip>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
vector<int> par(1000000);//それぞれの頂点の親,最大値をsizeにする
vector<int> dis(1000000);//ランク
ll n;
class union_find{
  public:
  void init(){
    for(int i = 0;i < n;i++){
      par[i] = i;//最初、親は自分自身とする
      dis[i] = 0;
    }
  }
  //木の根を求める
  int root(int x){
    if(par[x] == x){
      return x;
    }
    else{
      return par[x] = root(par[x]);
    }
  }
  //xとyが同じ集合に属すか否か
  bool same(int x,int y){
    //cout << x << " " << y << endl;
    return (root(x) == root(y));
  }
  //xとyの属する集合を併合
  void unite(int x,int y){
    x = root(x);
    y = root(y);
    if(x == y)return;
    if(dis[x] < dis[y]){
      par[x] = y;
    }
    else{
      par[y] = x;
      if(dis[x] == dis[y])dis[x]++;
    }
  }
};

//union_find tree;
//tree.init() //これで初期化
//tree.unite(a,b) //aとbのグループを併合
//tree.same(a,b) //aとbが同じグループか(trueかfalse)

int main(){
    ll m;
    cin >> n >> m;
    union_find tree;
    tree.init();
    for(int i = 0;i < m;i++){
        ll a,b;
        cin >> a >> b;
        a--,b--;
        tree.unite(a,b);
    }
    ll res = 0;
  //cout << tree.same(0,1) << " " << tree.same(0,2) << endl;
    for(int i = 0;i < n;i++){
        if(!tree.same(0,i)){
            res++;
            tree.unite(0,i);
        }
    }
    cout << res << endl;
}

Measured memory_bytes: 11032
#include<bits/stdc++.h>
using namespace std;
bool isNotPrime[1000200] = {1,1};
int prime(){
	for(int i = 2;i*i < 1000200;i++){
		for(int j = 2*i;j < 1000200;j+=i){
			isNotPrime[j] = 1;
		}
	}
}
int sc[1050][1050] = {};
int dp[1050][1050][2];
#define T_MAX  1000000
int main(){
	prime();
	int c = 502,t = 1;
	int x = c,y = c;
	int w = -1,h = -1,_w = 1000000,_h = 1000000;
	for(int i = 1;;i+=2){
		//cout<<t<<endl;
		for(int j = 1;j <= i;j++){
			sc[y][x] = t++;
			w = max(x,w);
			h = max(y,h);
			_w = min(x,_w);
			_h = min(y,_h);
			x++;
			if(t > T_MAX)goto next;
		}
		for(int j = 1;j <= i;j++){
			sc[y][x] = t++;
			w = max(x,w);
			h = max(y,h);
			_w = min(x,_w);
			_h = min(y,_h);
			y--;
			//if(x < 0 || y < 0)cout<<"!"<<endl;
			if(t > T_MAX)goto next;
		}
		for(int j = 1;j <= i+1;j++){
			sc[y][x] = t++;
			w = max(x,w);
			h = max(y,h);
			_w = min(x,_w);
			_h = min(y,_h);
			x--;
			//if(x < 0 || y < 0)cout<<"!"<<endl;
			if(t > T_MAX)goto next;
		}
		for(int j = 1;j <= i+1;j++){
			sc[y][x] = t++;
			w = max(x,w);
			h = max(y,h);
			_w = min(x,_w);
			_h = min(y,_h);
			y++;
			//if(x < 0 || y < 0)cout<<"!"<<endl;
			if(t > T_MAX)goto next;
		}
	}
	next:;
	int m,n;
	while(cin>>m>>n,m){
		int sx,sy;
		for(int i = 0;i < 1050;i++){
			for(int j = 0;j < 1050;j++){
				if(sc[i][j] == n)sy = i,sx = j;
				dp[i][j][0] = dp[i][j][1] = -1;
			}
		}
		dp[sy][sx][0] = dp[sy][sx][1] = 0;
		if(!isNotPrime[sc[sy][sx]])dp[sy][sx][0]++,dp[sy][sx][1] = sc[sy][sx];
		int aval = dp[sy][sx][0],aidx = dp[sy][sx][1];
		for(int i = sy;i <= h+1;i++){
			for(int j = 0;j <= w+1;j++){
				if(dp[i][j][0] == -1)continue;
				if(sc[i+1][j] != 0 && sc[i+1][j] <= m){
					int n0 = dp[i][j][0] + !isNotPrime[sc[i+1][j]];
					int n1 = (!isNotPrime[sc[i+1][j]]) ? sc[i+1][j] : dp[i][j][1];
					if(dp[i+1][j][0] == n0 ? dp[i+1][j][1] < n1 : dp[i+1][j][0] < n0){
						dp[i+1][j][0] = n0;
						dp[i+1][j][1] = n1;
					}
					if(dp[i+1][j][0] == aval ? dp[i+1][j][1] > aidx : dp[i+1][j][0] > aval){
						aval = dp[i+1][j][0];
						aidx = dp[i+1][j][1];
					}
				}
				if(sc[i+1][j-1] != 0 && sc[i+1][j-1] <= m){
					int n0 = dp[i][j][0] + !isNotPrime[sc[i+1][j-1]];
					int n1 = (!isNotPrime[sc[i+1][j-1]]) ? sc[i+1][j-1] : dp[i][j][1];
					if(dp[i+1][j-1][0] == n0 ? dp[i+1][j-1][1] < n1 : dp[i+1][j-1][0] < n0){
						dp[i+1][j-1][0] = n0;
						dp[i+1][j-1][1] = n1;
					}
					if(dp[i+1][j-1][0] == aval ? dp[i+1][j-1][1] > aidx : dp[i+1][j-1][0] > aval){
						aval = dp[i+1][j-1][0];
						aidx = dp[i+1][j-1][1];
					}
				}
				if(sc[i+1][j+1] != 0 && sc[i+1][j+1] <= m){
					int n0 = dp[i][j][0] + !isNotPrime[sc[i+1][j+1]];
					int n1 = (!isNotPrime[sc[i+1][j+1]]) ? sc[i+1][j+1] : dp[i][j][1];
					if(dp[i+1][j+1][0] == n0 ? dp[i+1][j+1][1] < n1 : dp[i+1][j+1][0] < n0){
						dp[i+1][j+1][0] = n0;
						dp[i+1][j+1][1] = n1;
					}
					if(dp[i+1][j+1][0] == aval ? dp[i+1][j+1][1] > aidx : dp[i+1][j+1][0] > aval){
						aval = dp[i+1][j+1][0];
						aidx = dp[i+1][j+1][1];
					}
				}

				//cout<<i<<" "<<j<<" "<<dp[i][j][0]<<" "<<dp[i][j][1]<<endl;
			}
		}
		cout<<aval<<" "<<aidx<<endl;
	}


}

Measured memory_bytes: 14868
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <sstream>
#include <algorithm>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <list>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <climits>
#include <bitset>
#include <functional>
#include <numeric>
#include <ctime>
#include <cassert>
#include <cstring>
#include <fstream>

#define rep(i, a, b) for(int (i)=(a); (i)<(b); (i)++)
#define irep(i, a, b) for(int (i)=(a);(i)<=(b);(i)++)
#define rrep(i, a, b) for(int (i)=(a);(i)>=(b);(i)--)

using namespace std;

const int MOD = 1e9 + 7;

int main() {
    int n;
    cin >> n;
    cout << (n / 10 == 9 || n % 10 == 9 ? "Yes" : "No") << endl;
    return 0;
}

Measured memory_bytes: 256
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)


# # # # class Segtree # # # #

#      0
#   1     2
# 3   4  5  6
#       :
# leaf i - n-1+i
# parent   - (i-1)//2
# children - 2*i+1, 2*i+2

class Segtree:
    # modify UNIT and oper depending on the reduce operation

    #UNIT = 0  # sum/or:0 and:fff..f min:BIG max:-BIG gcd:0 lcm:1 ..

    #@classmethod
    #def oper(c,x,y):
    #    return x|y  # sum:+ or/and/min/max/gcd/lcm:(same)

    # call like this: sgt = Segtree(n, 0, lambda x,y: max(x,y))

    def __init__(s,l,unit,oper):
        s.unit = unit
        s.oper = oper
        s.n = 1
        while s.n<l:
            s.n *= 2
        s.ary = [s.unit for i in range(2*s.n-1)]

    def get(s,i):
        return s.ary[i+s.n-1]

    def set(s,i,v):
        k = i+s.n-1
        s.ary[k] = v
        while k>0:
            k = (k-1)//2
            s.ary[k] = s.oper( \
                        s.ary[2*k+1], s.ary[2*k+2])

    def setary(s,a):
        for i,v in enumerate(a):
            s.ary[i+s.n-1] = v
        for k in range(s.n-2,-1,-1):
            s.ary[k] = s.oper( \
                        s.ary[2*k+1], s.ary[2*k+2])

    def query(s,x,y):
        l = x+s.n-1
        r = y+s.n-1
        res = s.unit
        while l<r:
            if not l%2:
                res = s.oper(res,s.ary[l])
                l += 1
            if not r%2:
                r -= 1
                res = s.oper(res,s.ary[r])
            l >>= 1
            r >>= 1
        return res


# # # # class Segtree end # # # #


n,q = inm()
b = (n-2)**2
minx = x = n-1
miny = y = n-1
sx = Segtree(n,n-1,lambda x,y: min(x,y))
sy = Segtree(n,n-1,lambda x,y: min(x,y))
z = [n-1]*n
sx.setary(z)
sy.setary(z)
#ddprint(sx.ary)
#ddprint(sy.ary)
for i in range(q):
    t,k = inm()
    k -= 1
    if t==1:
        b -= sy.query(k,n)-1
        if k<minx:
            sx.set(miny,k)
            minx = k
    else:
        b -= sx.query(k,n)-1
        if k<miny:
            sy.set(minx,k)
            miny = k
    #ddprint(f"{i=} {b=} {minx=} {miny=}")
    #ddprint(sx.ary)
    #ddprint(sy.ary)
print(b)


Measured memory_bytes: 147928
a,b,c,d = map(int,input().split())
 
while a>0 and c>0:
  if c>0:
    c += -b
    
  if c<=0:
    print("Yes")
    break
    
    
  if a>0:
    a += -d
    
  if a<=0:
    print("No")
    break
    

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

int main() {
  int N, MOD = 1e9+7;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; i++) cin >> A.at(i);
  long ans = 0;
  for (long i = 0, sum = 0; i < N; i++) {
    (ans += sum * A.at(i) % MOD) %= MOD;
    (sum += A.at(i)) %= MOD;
  }
  cout << ans << "\n";
}

Measured memory_bytes: 4032
use std::io::*;
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let n: usize = read();
    let mut a: Vec<i64> = vec![];

    for _ in 0..n {
        a.push(read());
    }
    println!("{}", a.iter().max().unwrap() - a.iter().min().unwrap());
}


Measured memory_bytes: 4352
import std.stdio;
import std.string;
import std.format;
import std.conv;
import std.typecons;
import std.algorithm;
import std.functional;
import std.bigint;
import std.numeric;
import std.array;
import std.math;
import std.range;
import std.container;
import std.concurrency;
import std.traits;
import std.uni;
import core.bitop : popcnt;
alias Generator = std.concurrency.Generator;

enum long INF = long.max/5;
enum long MOD = 10L^^9+7;

void main() {
  long N;
  scanln(N);
  foreach(x; 0..N+1) {
    long y = cast(long)(x*1.08 + 0.000001);
    if (y == N) {
      x.writeln;
      return;
    }
  }
  writeln(":(");
}

// ----------------------------------------------


void times(alias fun)(long n) {
  // n.iota.each!(i => fun());
  foreach(i; 0..n) fun();
}
auto rep(alias fun, T = typeof(fun()))(long n) {
  // return n.iota.map!(i => fun()).array;
  T[] res = new T[n];
  foreach(ref e; res) e = fun();
  return res;
}

T ceil(T)(T x, T y) if (isIntegral!T || is(T == BigInt)) {
  // `(x+y-1)/y` will only work for positive numbers ...
  T t = x / y;
  if (t * y < x) t++;
  return t;
}

T floor(T)(T x, T y) if (isIntegral!T || is(T == BigInt)) {
  T t = x / y;
  if (t * y > x) t--;
  return t;
}

ref T ch(alias fun, T, S...)(ref T lhs, S rhs) {
  return lhs = fun(lhs, rhs);
}
unittest {
  long x = 1000;
  x.ch!min(2000);
  assert(x == 1000);
  x.ch!min(3, 2, 1);
  assert(x == 1);
  x.ch!max(100).ch!min(1000); // clamp
  assert(x == 100);
  x.ch!max(0).ch!min(10); // clamp
  assert(x == 10);
}

mixin template Constructor() {
  import std.traits : FieldNameTuple;
  this(Args...)(Args args) {
    // static foreach(i, v; args) {
    foreach(i, v; args) {
      mixin("this." ~ FieldNameTuple!(typeof(this))[i]) = v;
    }
  }
}

void scanln(Args...)(auto ref Args args) {
  enum sep = " ";
  enum n = Args.length;
  enum fmt = n.rep!(()=>"%s").join(sep) ~ "\n";
  static if (__VERSION__ >= 2071) {
    readf!fmt(args);
  } else {
    enum argsTemp = n.iota.map!(
      i => "&args[%d]".format(i)
    ).join(", ");
    mixin(
      "readf(fmt, " ~ argsTemp ~ ");"
    );
  }
}

// fold was added in D 2.071.0
static if (__VERSION__ < 2071) {
  template fold(fun...) if (fun.length >= 1) {
    auto fold(R, S...)(R r, S seed) {
      static if (S.length < 2) {
        return reduce!fun(seed, r);
      } else {
        return reduce!fun(tuple(seed), r);
      }
    }
  }
}

// popcnt with ulongs was added in D 2.071.0
static if (__VERSION__ < 2071) {
  ulong popcnt(ulong x) {
    x = (x & 0x5555555555555555L) + (x>> 1 & 0x5555555555555555L);
    x = (x & 0x3333333333333333L) + (x>> 2 & 0x3333333333333333L);
    x = (x & 0x0f0f0f0f0f0f0f0fL) + (x>> 4 & 0x0f0f0f0f0f0f0f0fL);
    x = (x & 0x00ff00ff00ff00ffL) + (x>> 8 & 0x00ff00ff00ff00ffL);
    x = (x & 0x0000ffff0000ffffL) + (x>>16 & 0x0000ffff0000ffffL);
    x = (x & 0x00000000ffffffffL) + (x>>32 & 0x00000000ffffffffL);
    return x;
  }
}


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

#define ALL(v) v.begin(), v.end()
#define V vector
#define P pair
using ll = long long;
using ld = long double;
const int MOD = 1e9 + 7;

int main() {
    int a, b;
    cin >> a >> b;
    if (a <= b)
        cout << a << endl;
    else
        cout << a - 1 << endl;

    return 0;
}


Measured memory_bytes: 3444
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
h =list(map(int,input().split()))
c = [1]*n
for i in range(m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  if h[a] >=  h[b]:
    c[b] = 0
  if h[a] <=  h[b]:
    c[a] = 0
print(sum(c))

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

int main() {
  char s;
  cin >> s;
      if(s== 'a'||s=='i'||s=='u'||s=='e'||s=='o')cout<<"vowel"<<endl;

      else  cout <<"consonant"<<endl;
      
  // ここにプログラムを追記
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)
#define RFOR(i,s,e) for(int (i) = (s);(i) >= (e);(i)--)
#define rep(i,n) FOR(i,0,n-1)

signed main() {
    string s;cin>>s;

    rep(i,3)
    {
        if(s[i]=='1') cout << 9;
        else if(s[i]=='9') cout << 1;
        else cout <<s[i];
    }
}


Measured memory_bytes: 256
n = int(input())
p = [int(i) for i in input().split()]
ans = 0
for x,y,z in zip(p,p[1:],p[2:]):
    ls = []
    ls.append(x)
    ls.append(y)
    ls.append(z)
    ls.sort()
    if ls[1] == y:
        ans += 1
print(ans)

Measured memory_bytes: 3064
N=input()
a=input().split()
N=int(N)
for i in range(N):
    a[i]=int(a[i])

point_a=0
point_b=0

#全てのカードがなくなるまで（＝すべての変数値が0になったらカード無）
#一番目に大きい数値をアリスに
#二番目に大きい数値をボブに
while max(a)>0:
    #一番目に大きい数値をアリスに
    point_a+=max(a)
    #この数値をゼロに戻す
    a[a.index(max(a))]=0
    #二番目に大きい数値（この時点で一番大きい数値）をボブに
    point_b+=max(a)
    #この数値をゼロに戻す
    a[a.index(max(a))]=0

#答え
print(point_a-point_b)

Measured memory_bytes: 3064
W,H,N = map(int,input().split())
xya = [list(map(int,input().split())) for _ in range(N)]
p1,p2 = [0,0],[W,H]

for *p,a in xya:
    if a == 1:
        if p1[0] < p[0]:
            p1[0] = p[0]
    elif a == 2:
        if p2[0] > p[0]:
            p2[0] = p[0]
    elif a == 3:
        if p1[1] < p[1]:
            p1[1] = p[1]
    else:
        if p2[1] > p[1]:
            p2[1] = p[1]
if p2[0] - p1[0] < 0 or p2[1] - p1[1] < 0:
    print(0)
else:
    print((p2[0] - p1[0]) * (p2[1] - p1[1]))

Measured memory_bytes: 3064
/* Made by Takauov Yerzhan - 28/01/2020 */
#include <bits/stdc++.h>
#define LL long long
#define Okoshka ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pb push_back
#define F first
#define S second

using namespace std;

const LL MXN = 1e6 + 7;
const LL MOD = 1e9 + 7;
const LL INF = 1e18 + 7;

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

int n, a[MXN], suff[MXN], pref[MXN], ans;

int main()
{
    Okoshka;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    suff[n] = a[n];
    for(int i = n - 1; i > 1; i--){
        suff[i] = __gcd(suff[i + 1], a[i]);
    }
    pref[1] = a[1];
    for(int i = 2; i <= n; i++){
        pref[i] = __gcd(pref[i - 1], a[i]);
    }
    for(int i = 1; i <= n; i++){
        if(i == 1){
            ans = max(ans, suff[i + 1]);
        }
        else if(i == n){
            ans = max(ans, pref[i - 1]);
        }
        else {
            ans = max(ans, __gcd(pref[i - 1], suff[i + 1]));
        }
    }
    cout << ans;
}


Measured memory_bytes: 8960
#include<cstdio>
using namespace std;
  
typedef double D;
  
int n,a[110],r;
D b,v,e,f;
D dp[10100][110];
const D EPS = 1e-8;
  
int main(){
  while(scanf("%d",&n),n){
    a[0] = 0;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    scanf("%lf%d%lf%lf%lf",&b,&r,&v,&e,&f);
  
    for(int i=0;i<=a[n];i++)
      for(int j=0;j<=n;j++)dp[i][j] = 1e15;
    dp[0][0] = 0;
  
    int pos = 1;
    for(int i=0;i<a[n];i++){
      if(i==a[pos]){
    for(int j=0;j<pos;j++){
      if(dp[i][pos] > dp[i][j] + b + EPS){
        dp[i][pos] = dp[i][j] + b;
      }
    }
    pos++;
      }
  
      for(int j=0;j<=n;j++){
      if(dp[i][j] +EPS > 1e15)continue;
    int x = i-a[j];
    D cost = (x<r)?(1.0/(v-f*(r-x))):(1.0/(v-e*(x-r)));
    if(dp[i+1][j] > dp[i][j] + cost + EPS){
      dp[i+1][j] = dp[i][j] + cost;
    }
      }
    }
      
    D res = 1e15;
    for(int i=0;i<=n;i++){
      if(res > dp[a[n]][i] + EPS)res = dp[a[n]][i];
    }
    printf("%.10lf\n",res);
  }
}

Measured memory_bytes: 9688
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, n) for (int i = (int)(n); i >= 0; i--)
#define REP(i, m, n) for (int i = (int)(m); i <= (int)(n); i++)
#define all(v) v.begin(), v.end()
typedef long long ll;

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; }

const long long INF = 1LL << 60;

int main(){
  ll x, k, d;
  cin >> x >> k >> d;
  if(x < 0) x = -x;

  if(d > 10000000000000000/k){
    ll r = x % d;
    ll a = x / d;
    if((k-a) % 2 == 0){
      cout << r << endl;
    }
    else cout << d - r << endl;
    return 0;
  }

  if(k*d > x){
    ll r = x % d;
    ll a = x / d;
    if((k-a) % 2 == 0){
      cout << r << endl;
    }
    else cout << d - r << endl;
  }
  else {
    cout << x - k*d << endl;
  }

  return 0;
}


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

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

    int a, b;
    cin >> a >> b;

    rep(_, max(a, b)) cout << min(a, b);
    cout << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int
#define ul unsigned long long int
#define va vector<long long int> a 
#define vb vector<long long int> b
const ll M = 1e9+7;
const ll inf = 1e18+5;
using namespace std;
void fast(){cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(0);}
ll bs(ll arr[], ll l, ll r, ll x){
	ll mid=0;
    if (r >= l){
		if (arr[mid] == x) return mid; 
        if (arr[mid] > x) return bs(arr, l, mid - 1, x); 
        return bs(arr, mid + 1, r, x); 
    }
    return -1;
}
ll power(ll x,ul y,ll p){
	ll res = 1;
	x = x % p;
	if(x == 0) return 0;
	while (y > 0){
		if (y & 1) res = (res*x) % p;
		y = y>>1;
		x = (x*x) % p;
		}
	return res;
}
void solve(){
	ll n,x,y,z,count=0;
	cin>>n>>x;
	for(ll i=0;i<n;i++){ 
		cin>>y>>z;
		if(sqrt(y*y+z*z)<=x) count++;
	}
	cout<<count<<"\n";
 }
int main(){
	fast();
	solve();
	return 0;
}



Measured memory_bytes: 3696
s = list(input())
a = 0
z = 0
for i in range(len(s)):
    if s[i] == 'A':
        a = i+1
        break
for i in range(1, len(s)):
    if s[-i] == 'Z':
        z = len(s)-i+1
        break
print(z-a+1)

Measured memory_bytes: 4840
import sys
from collections import deque

input = sys.stdin.readline


def calc_group(N, G, group_id, group_cnt):
    g_id = 0
    for i in range(N):
        if group_id[i] != -1:
            continue
        g_id += 1
        group_id[i] = g_id
        group_cnt[g_id] = 1
        stack = deque([i])
        while stack:
            v = stack.pop()
            for u in G[v]:
                if group_id[u] != -1:
                    continue
                group_id[u] = g_id
                group_cnt[g_id] += 1
                stack.append(u)


def main():
    N, M, K = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        A, B = map(int, input().split())
        A -= 1
        B -= 1
        G[A].append(B)
        G[B].append(A)
    B = [[] for _ in range(N)]
    for i in range(K):
        C, D = map(int, input().split())
        C -= 1
        D -= 1
        B[C].append(D)
        B[D].append(C)

    group_id = [-1] * N
    group_cnt = {}
    calc_group(N, G, group_id, group_cnt)

    ans = [0] * N
    for i in range(N):
        n_neighbor = len(G[i])
        n_block = sum(1 for j in B[i] if group_id[i] == group_id[j])
        ans[i] = (group_cnt[group_id[i]] - 1) - n_neighbor - n_block

    print(" ".join(map(str, ans)))


if __name__ == "__main__":
    main()


Measured memory_bytes: 52044
#include <bits/stdc++.h>
using namespace std;
///////////////////////////////////////////
const long long int INF = 1LL<<60;
const long long int Mod = 1000000007;
using ll = long long int; using ci = const int;
using vi = vector<int>;  using Vi = vector<long long int>;
using P = pair<int, int>;  using PLL = pair<ll, ll>;
using matrix = vector<vector<ll>>;
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define rp(i,N) for(ll i = 0; i < (ll)N; i++)
#define repi(i,a,b) for(ll i = ll(a); i < ll(b); ++i)
template<class T>bool chmax(T &former, const T &b) { if (former<b) { former=b; return true; } return false; }
template<class T>bool chmin(T &former, const T &b) { if (b<former) { former=b; return true; } return false; }
template<class T>T sqar(T x){ return x*x; }//sqrt(x)は平方根;
#define Sort(v) std::sort(v.begin(), v.end(), std::greater<decltype(v[0])>()) //降順でVをソート
#define p_queue(v) priority_queue<v, vector<v>, greater<v> >
template<class T> inline void princ(T x){cout<<x<<" ";}; 
template<class T> inline void print(T x){cout<<x<<"\n";};
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
///////////////////////////////////////////////////////////////////////////////////

void solve(){
    int n;
    cin >> n;
    bool u,d;
    if(1<=n%100&&n%100<=12)d=true;
    else d=false;
    if(1<=n/100&&n/100<=12)u=true;
    else u=false;
    if(u&&d) print("AMBIGUOUS");
    else if(d) print("YYMM");
    else if(u) print("MMYY");
    else print("NA");
    return;
}
int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    std::cout<<std::fixed<<std::setprecision(30);
    solve();
    return 0;
}

Measured memory_bytes: 3604
a, b, c = map(int, input().split())

counter = 0
while a%2==b%2==c%2==0:
    a, b, c = (b+c)//2, (a+c)//2, (a+b)//2
    counter += 1
    if counter > 31:
        counter = -1
        break
print(counter)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL,LL> PLL;
const double PI  = acos(-1.0);
const double eps = 1e-8;
const int inf = 0x3f3f3f3f;
const LL INF  = 0x3f3f3f3f3f3f3f3f;
const int N=3e5+10;
const int M=1e6+10;
const int mod=998244353;
inline LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; }
inline LL lcm(LL a, LL b) { return a * b / gcd(a, b); }
inline LL read(){LL x=0,f=1;char c=getchar();while(c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}return x*f;}
inline LL qpow(LL x,LL k=mod-2,LL m=mod){LL res=1;while(k){if(k&1) res=res*x%m;x=x*x%m;k>>=1;}return res;}
/*=================================================================================================================*/
int n,q;
LL ans,a1[N],a0[N]={1};

struct SegTree{
    #define mid (l+r>>1)
    LL sum[N*4],tag[N*4];
    void pushdown(int id,int l,int r){
        int llen=mid-l+1,rlen=r-mid;
        sum[id<<1]=a1[llen]*tag[id]%mod,tag[id<<1]=tag[id];
        sum[id<<1|1]=a1[rlen]*tag[id]%mod,tag[id<<1|1]=tag[id];
        tag[id]=0;
    }
    void upd(int id,int l,int r,int L,int R,int x){
        if(L<=l&&r<=R) {sum[id]=a1[r-l+1]*x%mod;tag[id]=x;return;}
        if(tag[id]) pushdown(id,l,r);
        if(L<=mid) upd(id<<1,l,mid,L,R,x);
        if(R>mid) upd(id<<1|1,mid+1,r,L,R,x);
        sum[id]=(sum[id<<1]*a0[r-mid]%mod+sum[id<<1|1])%mod;
    }
    #undef mid
}tr;

int main(){
    n=read(),q=read();
    for(int i=1;i<=n;i++) 
        a1[i]=(a1[i-1]*10+1)%mod,
        a0[i]=a0[i-1]*10%mod;
    tr.upd(1,1,n,1,n,1);
    while(q--){
        int l=read(),r=read(),x=read();
        tr.upd(1,1,n,l,r,x);
        printf("%lld\n",tr.sum[1]);
    }
    return 0;
}


Measured memory_bytes: 15116
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;

int gi() {
	int x=0,o=1;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if(ch=='-') o=-1,ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x*o;
}

int n,m,fa[N];
vector<pair<int,int>> E[N];
pair<int,int> ans[N];
bool deg[N];

void dfs(int u,int fa) {
	for(auto x:E[u]) {
		int v=x.first,id=x.second;
		if(v==fa) continue;
		dfs(v,u);
		if(deg[v]) deg[v]=0,ans[id]=make_pair(v,u);
		else deg[u]^=1,ans[id]=make_pair(u,v);
	}
}

int getf(int x) {
	return x==fa[x]?x:fa[x]=getf(fa[x]);
}

int main() {
	cin>>n>>m;
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1,u,v;i<=m;i++) {
		u=gi(),v=gi();
		if(getf(u)!=getf(v)) fa[getf(u)]=getf(v),E[u].emplace_back(v,i),E[v].emplace_back(u,i);
		else ans[i]=make_pair(u,v),deg[u]^=1;	
	}
	dfs(1,0);
	if(deg[1]) puts("-1");
	else for(int i=1;i<=m;i++) cout<<ans[i].first<<' '<<ans[i].second<<endl;
	return 0;
}


Measured memory_bytes: 14720
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define int ll
typedef pair<int, int> pii;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)

signed main() {
    ios::sync_with_stdio(false);cin.tie(0);
    REP(_, 20) {
        int n; cin >> n;
        if (n == 0) break;
        vector<int> v;
        REP(i, n) {
            int x; cin >> x;
            v.push_back(x);
        }
        sort(v.begin(), v.end());
        int ans = 0;
        FOR(i, 1, n-1) ans += v[i];
        ans /= n - 2;
        cout << ans << endl;
    }
}


Measured memory_bytes: 3132
#include<bits/stdc++.h>
using namespace std;
const int N=42;
typedef long long ll;

int gi() {
	int x=0,o=1;char ch=getchar();
	while(!isdigit(ch)&&ch!='-') ch=getchar();
	if(ch=='-') o=-1,ch=getchar();
	while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	return x*o;
}

int n;
char s[N][N];
ll f[N][N][N];

ll dp(int l,int r,int m) {
	if(~f[l][r][m]) return f[l][r][m];
	if(l==r) return 1;
	if(l==m||r==m) return 0;
	ll &ret=f[l][r][m];ret=0;
	for(int i=l;i<m;i++)
		for(int j=m+1;j<=r;j++)
			if(s[i][j]=='1')
				for(int u=i;u<m;u++)
					for(int v=m+1;v<=j;v++) ret+=dp(l,u,i)*dp(u+1,v-1,m)*dp(v,r,j);
	return ret;
}

int main() {
	n=gi();
	for(int i=1;i<=n+n;i++) scanf("%s",s[i]+1);
	memset(f,-1,sizeof(f));
	ll ans=0;
	for(int i=2;i<=n+n;i++) if(s[1][i]=='1') ans+=dp(2,n+n,i);
	cout<<ans;
	return 0;
}


Measured memory_bytes: 768
n=int(input())
if n<105:
	print('0')
else:
	if n<135:
		print('1')
	else:
		if n<165:
			print('2')
		else:
			if n<189:
				print('3')
			else:
				if n<195:
					print('4')
				else:
					print('5')	

Measured memory_bytes: 2940
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.NoSuchElementException;
public class Main {
	public static void main(String[] args)throws Exception{
		PrintWriter out = new PrintWriter(System.out);
		int N=nextInt();
		int ans[]=new int[N+1];
		for(int i=1;i*i<N;i++){
			for(int j=1;j*j+i*i+i*j<N;j++){
				for(int k=1;k*k+j*j+i*i+i*j+j*k+i*k<=N;k++){
					ans[k*k+j*j+i*i+i*j+j*k+i*k]++;
				}
			}
		}
		for(int i=0;i<N;i++){
			System.out.println(ans[i+1]);
		}
	}
	static boolean isOK(int index,int key,ArrayList<Integer>a){
		if (a.get(index) >= key) return true;
	    else return false;
	}
	static int binary_search(int key,ArrayList<Integer> a) {
	    int ng = -1; //「index = 0」が条件を満たすこともあるので、初期値は -1
	    int ok = (int)a.size(); // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()
	    while (Math.abs(ok - ng) > 1) {
	        int mid = (ok + ng) / 2;

	        if (isOK(mid,key,a)) ok = mid;
	        else ng = mid;
	    }
	    return ok;
	}
	//FastScanner
	static InputStream in = System.in;
	static  byte[] buffer = new byte[1024];
	static int length = 0, p = 0;
	public static boolean hasNextByte () {
		if (p < length) return true;
		else {
			p = 0;
			try {length = in.read(buffer);}
			catch (Exception e) {e.printStackTrace();}
			if (length == 0) return false;
		}
		return true;
	}
	public static int readByte () {
		if (hasNextByte() == true) return buffer[p++];
		return -1;
	}
	public static boolean isPrintable (int n) {return 33<=n&&n<=126;}
	public static void skip () {
		while (hasNextByte() && !isPrintable(buffer[p])) p++;
	}
	public static boolean hasNext () {skip(); return hasNextByte();}
	public static String next () {
		if (!hasNext()) throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int temp = readByte();
		while (isPrintable(temp)) {
			sb.appendCodePoint(temp);
			temp = readByte();
		}
		return sb.toString();
	}
	public static int nextInt () {return Math.toIntExact(nextLong());}
	public static int[] nextInts (int n) {
		int[] ar = new int[n];
		for (int i=0; i<n; i++) ar[i] = nextInt();
		return ar;
	}
	public static long nextLong () {
		if (!hasNext()) throw new NoSuchElementException();
		boolean minus = false;
		int temp = readByte();
		if (temp == '-') {
			minus = true;
			temp = readByte();
		}
		if (temp<'0' || '9'<temp) throw new NumberFormatException();
		long n = 0;
		while (isPrintable(temp)) {
			if ('0'<=temp && temp<='9') {
				n *= 10;
				n += temp - '0';
			}
			temp = readByte();
		}
		return minus? -n : n;
	}
}



Measured memory_bytes: 35672
#include <iostream>
#include<stdio.h>
using namespace std;

int main() {
    int a,b,c,d,p,A,B,i;
    cin >> a >> b >> c >> d >> p;
    A = a*p;
    B = 0;
    i = 0;
    if(p > c){
        p = p - c;
        while(1){
            p = p - 1;
            i ++;
            if(p < 1){
                break;
            }
        }
        B = b+i*d;
        
    }else{
        B = b;
    }
 
    if(A < B){
        p = A;
    }else if(A > B){
        p = B;
    }else{
        p = A;
    }
    
    cout << p << endl;
    
}

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

int main()
{
	int n,x;
	cin>>n;
	vector<int>v;
	for(int i=0;i<n;i++)
		{  cin>>x;
			v.push_back(x);
		}
			int a[n];
			a[0]=0;
			a[1]=abs(v[1]-v[0]);
			for(int i=2;i<n;i++)
			{
				a[i]=min(a[i-2]+abs(v[i]-v[i-2]),a[i-1]+abs(v[i]-v[i-1]));
			}
     cout<<a[n-1];
	return 0;
}

Measured memory_bytes: 1144
#include <stdio.h>
 
int main(){
    int N,i,j,ball,a,b,flag;
 
    scanf("%d",&N);
 
    for(i = 0;i < N;i++){
        a = b = 0;
        flag = 1;
        for(j = 0;j < 10;j++){
            scanf("%d",&ball);
            if(a < ball){
                a = ball;
            }else if(b < ball){
                b = ball;
            }else{
                flag = 0;
            }
        }
        printf("%s\n",flag ? "YES" : "NO");
    }
 
    return 0;
}

Measured memory_bytes: 580
use proconio::input;

fn main() {
    input! {
        s: usize,
    }
    let modulo = 1_000_000_007;
    let c = Combination::new(s, modulo);
    let mut result = 0;
    for i in 1..=s / 3 {
        let remain = s - 3 * i;
        result = (result + c.combination(i + remain - 1, i - 1)) % modulo;
    }
    println!("{}", result);
}

struct Combination {
    modulo: usize,
    fac: Vec<usize>,
    fac_inv: Vec<usize>,
}
impl Combination {
    /// O(n) # ready to compute combination(n,k) mod p, where p is prime and larger than n
    fn new(max: usize, modulo: usize) -> Self {
        let (mut fac, mut fac_inv, mut inv) =
            (vec![1; max + 1], vec![1; max + 1], vec![1; max + 1]);
        for i in 2..=max {
            fac[i] = fac[i - 1] * i % modulo;
            inv[i] = modulo - inv[modulo % i] * (modulo / i) % modulo;
            fac_inv[i] = fac_inv[i - 1] * inv[i] % modulo;
        }
        Combination {
            modulo,
            fac,
            fac_inv,
        }
    }

    /// O(1) # compute combination(n,k) mod p, where p is prime
    fn combination(&self, n: usize, k: usize) -> usize {
        if n < k {
            0
        } else {
            self.fac[n] * (self.fac_inv[k] * self.fac_inv[n - k] % self.modulo) % self.modulo
        }
    }
}


Measured memory_bytes: 2224
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    map<int,int> mp;
    int a;
    for(int i=0;i<n;i++){
        cin >> a;
        mp[a]++;
    }
    int ans=0;
    for(auto u:mp)if(u.second%2==1)ans++;
    cout << ans;
}

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

#define pb         push_back

typedef long long ll;
const ll INF = 1000000000000000000ll;
const ll MOD = 1000000007ll;
const double EPS = 1e-8;

int main(void) {
	//ios_base::sync_with_stdio(false);
	//cin.tie(0);
	
	ll n, k;
	cin >> n >> k;

	vector<pair<int, int>> p;
	for(int i=0; i<n; i++){
		int a, b;
		cin >> a >> b;
		p.pb(make_pair(a, b));
	}
	sort(p.begin(), p.end());

	ll sum = 0;
	for(int i=0; i<n; i++){
		sum += p[i].second;
		if(sum >= k){
			cout << p[i].first << endl;
			break;
		}
	}
	
	return 0;
}


Measured memory_bytes: 1400