akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <stdio.h>
#include<iostream>
#include<cstdio>
#include<bitset>
#include<algorithm>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<string.h>
#include<cmath>
#include<utility>
#include<functional>
#include<map>
#include<set>
#include<cctype>
#include<fstream>
#include <numeric>
#include <iomanip>
#include <cstring> 
using namespace std;
using ll=long long;

#define FOR(i, a, b) for( int i=(a);i<=(b);i++)
#define RFOR(i, a, b) for( int i=(a);i>=(b);i--)
#define LFOR(i, a, b) for( long long int i=(a);i<=(b);i++)
#define LRFOR(i, a, b) for(long long int i=(a);i>=(b);i--)
#define MOD 1000000007
#define LLONG_MAXs 9223372036854775800

#define ALL(a) (a).begin(),(a).end()

#include <iostream>
#include <cmath>
using namespace std;
 

 
bool isPrimeNum( ll x ){ // 素数である場合 true を返す
  if( x <= 1 ){ // 1以下である場合は素数でないことがすぐにわかる
    return false;
  }
  // sqrt( double型 ) は引数の平方根を double型で返すので、int型でキャスト
  int n = (int)sqrt( (double)x );
  for( int i = 2; i <= n; i++ ){
    if( x % i == 0 ){ // 割り切る整数がある場合、即判定終了
      return false;
    }
  }
  return true; // 割り切る整数がない場合、素数である
}

ll myPow(ll x, ll n, ll m){
  if(n == 0)
    return 1;
  if(n % 2 == 0)
    return myPow(x * x % m, n / 2, m);
  else
    return x * myPow(x, n - 1, m) % m;
}

constexpr ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
constexpr ll lcm(ll a,ll b){return a*b/gcd(a,b);}
constexpr ll abs(ll a,ll b){
if(a>=b)return a-b;
if(a<b)return b-a;
}
constexpr ll min(ll a,ll b){
if(a>=b)return b;
if(a<b)return a;
}

constexpr ll max(ll a,ll b){
if(a>=b)return a;
if(a<b)return b;
}

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

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};


int main() {
  ll N,K;
  cin>>N>>K;
  ll ans=0;
  if(K%2!=0){
    ll tmp= N/K;
    ans= tmp*tmp*tmp;
  }else{
    ll tmp1=0;
    ll tmp2=0;
    FOR(i,1,N){
      if(i%K==0)tmp1++;
      if(i%K==(K/2))tmp2++;
    }

    ans= tmp1*tmp1*tmp1;
    ans= ans+tmp2*tmp2*tmp2;
  }



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


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include<algorithm>
#include<string>
#include <map>
#include <queue>
#include <stack>
#include<set>

#define DIV 1000000007
using namespace std;
using ll = long long;
using ldb = long double;

int main() {
	int A, B; cin >> A >> B;
	cout << (A >= 13 ? B : (A <= 5 ? 0 : B / 2)) << endl;
}

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

int main(){
    ll k;
    cin>>k;
    ll ans = 0;
    for(int i=1; i<=k; i++){
        for(int j=1; j<=k; j++){
            for(int l=1; l<=k; l++){
                ans += __gcd(i, __gcd(j, l));
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define rrep(i,a,b) for(int i=(a);i>=(b);--i)
#define PB push_back
#define ar2 array<int,2> 
#define vs vector<string>
typedef long long LL;
const int P = 998244353;
const int N = 305;
mt19937 rng(time(0));

int T, n, K, n0=0, n1;
char s[N];
int a[N], sum[N], dp[N][N][N], sdp[N][N][N];
//i-th, j-same, k-max

void madd(int &x, int y){
	x += y;
	x = (x>=P ? x-P : x);
}

int main() {
	cin>>(s+1)>>K;
	n = strlen(s+1);
	rep(i,1,n) if(s[i]=='0') n0++; else a[n0]++;
	sum[0] = a[0];
	rep(i,1,n0) sum[i] = sum[i-1] + a[i];
	n1 = n - n0;
	
	rep(i,0,n1) rep(j,0,i){
		dp[i][j][0] = sdp[i][j][0] = (min(i, a[0]) == j ? 1 : 0);
		//cout<<i<<" "<<j<<" 0 "<<dp[i][j][0]<<endl;
		rep(k,1,n0){
			if(sum[k]>i) {
				sdp[i][j][k] = sdp[i][j][k-1];
				continue;
			}
			rep(t,sum[k-1],i-1){
				if(j-min(i-t, a[k])<0) continue;
				madd(dp[i][j][k], sdp[t][j-min(i-t, a[k])][k-1]);
			}
			sdp[i][j][k] = sdp[i][j][k-1];
			madd(sdp[i][j][k], dp[i][j][k]);
			//cout<<i<<" "<<j<<" "<<k<<" "<<dp[i][j][k]<<endl;
		}
	}
	
	int ans = 0;
	rep(j, max(0, n1-K), n1) madd(ans, sdp[n1][j][n0]);
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 112132
import java.io.*;
import java.math.*;
import java.util.*;

public class Main {
    private static boolean debug = false;
    private static boolean elapsed = true;

    private static PrintWriter _out = new PrintWriter(System.out);
    private static PrintWriter _err = new PrintWriter(System.err);

    private int N;
    private int K;
    private int[] a;

    private void solve(Scanner sc) {
        N = sc.nextInt();
        K = sc.nextInt();
        a = new int[N];
        long sum = 0;
        for (int i = 0; i < N; ++i) {
            a[i] = sc.nextInt();
            sum += a[i];
        }

        if (sum < K) {
            _out.println(N);
            return;
        }

        Arrays.sort(a);

        long ans = 0;
        int left = 0;
        int right = N;
        while (left < right) {
            int c = (left + right) / 2;
            boolean flg = true;
            if (a[c] < K) {
                boolean[][] dp = new boolean[N][K];
                dp[0][0] = true;
                if (c != 0) {
                    dp[0][a[0]] = true;
                }
                for (int i = 1; i < N; ++i) {
                    dp[i][0] = true;
                    for (int j = 0; j < K; ++j) {
                        if (i != c && a[i] <= j) {
                            dp[i][j] = dp[i - 1][j] || dp[i - 1][j - a[i]];
                        } else {
                            dp[i][j] = dp[i - 1][j];
                        }
                    }
                }
                flg = false;
                for (int i = K - a[c]; i < K; ++i) {
                    if (dp[N - 1][i]) {
                        flg = true;
                        break;
                    }
                }
            }
            if (flg) {
                right = c;
            } else {
                ans = c + 1;
                left = c + 1;
            }
        }

        _out.println(ans);
    }
    private static BigInteger C(long n, long r) {
        BigInteger res = BigInteger.ONE;
        for (long i = n; i > n - r; --i) {
            res = res.multiply(BigInteger.valueOf(i));
        }
        for (long i = r; i > 1; --i) {
            res = res.divide(BigInteger.valueOf(i));
        }
        return res;
    }
    private static BigInteger P(long n, long r) {
        BigInteger res = BigInteger.ONE;
        for (long i = n; i > n - r; --i) {
            res = res.multiply(BigInteger.valueOf(i));
        }
        return res;
    }
    /*
     * 10^10 > Integer.MAX_VALUE = 2147483647 > 10^9
     * 10^19 > Long.MAX_VALUE = 9223372036854775807L > 10^18
     */
    public static void main(String[] args) {
        long S = System.currentTimeMillis();

        Scanner sc = new Scanner(System.in);
        new Main().solve(sc);
        _out.flush();

        long G = System.currentTimeMillis();
        if (elapsed) {
            _err.println((G - S) + "ms");
        }
        _err.flush();
    }
}

Measured memory_bytes: 200700
#include <iostream>
using namespace std;
 
int main(){
    int n,check;
    long a[100005]={};
    int cnt1=0,cnt2=0; 
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>a[i];
        if(a[i]%4==0)
            cnt1++;
        else if(a[i]%2==0)
            cnt2++;
    }
    if(cnt2>=2){
        cnt1+=cnt2/2;
        n-=cnt2/2;
    }
    if(cnt1==0){
        cout<<"No"<<endl;
    }else if((n-cnt1)%2==0){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
typedef long long ll;
typedef long double ld;
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  
using namespace std;
 
const ll inf = 1e17;
const ll N = 1e5+10;
const ll bits = 30;
const ll mod = 998244353;

vector<int>adj[N];
int dist[N],vis[N],indeg[N];

void dfs(int node){
    // cout<<node<<"\n";
    vis[node] = 1;
    for(auto nxt: adj[node]){
        if(!vis[nxt]){
            dfs(nxt);
            
        }

        dist[node] = max(dist[node],1+dist[nxt]);
    }
}


int main(){
    FASTIO;
    int n,m,u,v;
    cin>>n>>m;

    for(int i=0;i<m;i++){
        cin>>u>>v;
        indeg[v]++;
        adj[u].push_back(v);
    }

    // cout<<"\n";

    for(int i=1;i<=n;i++){
        if(!vis[i]){
            dfs(i);
        }
    }

    int ans = 0;

    for(int i=1;i<=n;i++){
        ans = max(ans,dist[i]);
        // cout<<dist[i]<<" ";
    }

    

    cout<<ans<<"\n";


}

Measured memory_bytes: 8960
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define all(obj) (obj).begin(),(obj).end() 
#define dump(x)  cout << #x << " = " << (x) << endl;
typedef long long lint;
using namespace std;
int main(){
	string s;
	cin>>s;
	s.at(3)='8';
	cout<<s<<endl;
}


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

int main(){
    int n; cin >> n;
    string s; cin >> s;
    if(n % 2 == 1){
        cout << "No" << endl;
        return 0;
    }
    for(int i = 0; i < n/2; i++){
        if(s[i] != s[n/2+i]){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}


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

void moji(char c){
    if('a' <= c && c <= 'z'){
        c -= 'a' - 'A';
    }
    else if('A' <= c && c <= 'Z'){
        c += 'a' - 'A';
    }
    cout << c;
}

int main(){
    string str;
    
    getline(cin,str);
    for(int i = 0 ; i < str.size() ; i++) moji(str[i]);
    cout << endl;
    
    return 0;
}

Measured memory_bytes: 1172
#include<stdio.h>
int main(void)
{
  int a,b,c,tmp;
  scanf("%d %d %d",&a,&b,&c);
  if(a>c)
  {
    tmp=a;
    a=c;
    c=tmp;
  }
  if(a>b)
  {
    tmp=a;
    a=b;
    b=tmp;
  }
  if(b>c)
  {
    tmp=b;
    b=c;
    c=tmp;
  }

  printf("%d %d %d\n",a,b,c);
  return 0;
}



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

int main() {
	int k, s;
	cin >> k >> s;
	int ans = 0;
	for (int x = 0; x <= k; x++) {
		for (int y = 0; y <= k; y++) {
			int z = s - x - y;
			if (0 <= z && z <= k)
				ans++;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>


struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL

Node root;

Node treeMinimum(Node x){
  while(x->left!=NIL)
    x=x->left;
  return x;

}
Node treeMaximum(Node x){
  while(x->right!=NIL)
    x=x->right;
  return x;

}


Node treeSearch(Node u, int k){
  while(u!=NIL&&k!=u->key){
    if(k<u->key)u=u->left;
    else u=u->right;
  }
  return u;
}

Node treeSuccessor(Node x){
  Node y;
  if(x->right!=NIL)return treeMinimum(x->right);
  y=x->parent;
   while(y!=NIL&&x==y->right){
    x=y;
    y=y->parent;
  }
  return y;
}

void treeDelete(Node z){
  Node y; // node to be deleted
  Node x; // child of y
  if(z->left==NIL||z->right==NIL)y=z;
  else y=treeSuccessor(z);

  if(y->left!=NIL){
    x=y->left;
  }else{
    x=y->right;
  }

  if(x!=NIL){
    x->parent=y->parent;
  }

  if(y->parent==NIL){
    root=x;
  }else{
    if(y==y->parent->left){
      y->parent->left=x;
    }else{
      y->parent->right=x;
    }
  }

  if(y!=z){
    z->key=y->key;
  }
  free(y);
}

void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

  while(x!=NIL){
    y=x;
    if(z->key < x->key){
      x=x->left;
    }else{
      x=x->right;
    }
  }
  z->parent = y;
  if(y==NIL){
    root=z;
  }else{
    if(z->key < y->key){
      y->left=z;
    }else{
      y->right=z;
    }
  }
}

void inorder(Node u){
  if(u==NIL)return;
  inorder(u->left);
  printf(" %d",u->key);
  inorder(u->right);
}
void preorder(Node u){
  if(u==NIL)return;
  printf(" %d",u->key);
  preorder(u->left);
  preorder(u->right);
}


int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } else if ( com[0] == 'd' ){
      scanf("%d", &x);
      treeDelete(treeSearch(root, x));
    }
  }

  return 0;
}



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

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

  int ans = 1;
  while(true) {
    ans *= 2;
    if(ans > N) {
      ans /= 2;
      break;
    } 

  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#pragma comment(linker, "/STACK:256000000")
#define _USE_MATH_DEFINES
#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<algorithm>
#include<cmath>
#include<set>
#include<queue>
#include<sstream>
#include<utility>
#include<map>
#include<ctime>
#include<cstdio>
#include<cassert>
#include<functional>
#include<unordered_map>




using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<char, char> pcc;
typedef pair<double, double> pdd;

#define show(x) cerr << x
#define debug(x) show(#x << ": " << (x) << endl)

const long double PI = 3.14159265358979323846;
const long double eps = 1e-5;
const int INF = numeric_limits<int>::max();
const ll LINF = numeric_limits<ll>::max();
const ll mod = 1000 * 1000 * 1000 + 7;



void solve() {
    ll n;
    cin >> n;
    ll res = 0;
    for (ll x = 1; x * x < n; ++x) {
        ll y = n / x;
        if ((x * y == n) && (y >= x + 2))
            res += y - 1;
    }
    cout << res << endl;

    
    
}

//#define LOCAL

int main() {
    ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    solve();


#ifdef LOCAL
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif	
    return 0;
}


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

int main() {
  int h, w;
  cin >> h >> w;
  
  string board[50];
  for(int i =0; i < h * w; i++){
    cin >> board[i];
  }
  
  const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
  const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
  
  for(int i = 0; i < h; i++){
    for(int j = 0; j < w; j++){
      if(board[i][j] == '#') continue;
      
      int num = 0;
      for(int d = 0; d < 8; d++){
        const int ni = i + dy[d];
        const int nj = j + dx[d];
        
        if(ni < 0 or h <= ni) continue;
        if(nj < 0 or w <= nj) continue;
        if(board[ni][nj] == '#') num++;
      }
      
      board[i][j] = char(num + '0');
    }
  }
  for(int i = 0; i < h; i++){
    for(int j = 0; j < w; j++){
      cout << board[i][j];
    }
    cout<<endl;
  }
  return 0;
}
          
        
  

         
        

Measured memory_bytes: 256
#include<stdio.h>
main(){
    int i,j,h[10],tmp;
    for(i=0;i<10;i++){
        scanf("%d",&h[i]);
    }
     
    for(i=0;i<=9;i++){
        for(j=9;j>i;j--){
            if(h[j]>h[j-1]){
                tmp=h[j];
                h[j]=h[j-1];
                h[j-1]=tmp;
            }
        }
    }
    for(i=0;i<3;i++){
        printf("%d\n",h[i]);
    }
    return 0;
}



Measured memory_bytes: 1928
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int d = Integer.parseInt(sc.next());
		int n = Integer.parseInt(sc.next());

		if (n == 100) {
			n++;
		}

		long ans = (long) (Math.pow(100, d) * n);

		System.out.println(ans);
	}
}


Measured memory_bytes: 23892
def MAX(a, b):
    return b + (((((a + ms - b) & ms) >> (K - 1)) * tt) & (ms + a - b))

def tolist(n):
    sx = bin(n)[2:] + "_"
    return [int(sx[-(i+1) * K - 1:-i * K - 1], 2) for i in range((len(sx)+K-2) // K)]

K = 52
N, W = map(int, input().split())

ms = int(("1" + "0" * (K - 1)) * (W + 1), 2)
tt = (1 << K - 1) - 1
one = int(("0" * (K - 1) + "1") * (W + 1), 2)

s = 1 << K - 2 + (W * K)
for _ in range(N):
    w, v = map(int, input().split())
    s = MAX(s, (s >> w * K) + one * v)

print(max(tolist(s)) - (1 << K - 2))

Measured memory_bytes: 22700
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <math.h>
#include <cmath>
#include<cctype>
#include<string>
#include<set>
#include<iomanip>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include<bitset>
#include <deque>
#include <climits>
#include <typeinfo>
#include <utility> 
using namespace std;
using ll = long long;
template<typename T>using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const ll inf = 1LL << 60;
#define all(x) (x).begin(),(x).end()
#define puts(x) cout << x << endl
#define rep(i,m,n) for(ll i = m;i < n;++i)
#define pb push_back
#define fore(i,a) for(auto &i:a)
#define rrep(i,m,n) for(ll i = m;i >= n;--i)

vector<vector<ll>>v;
ll N, X;

ll f(ll x, ll b, ll l, ll u) {
	if (x <= b) {
		return l * (x - b);
	}
	else {
		return u * (x - b);
	}
}

int check(ll mid) {
	ll sum = 0;
	ll q = mid / X;
	ll r = mid % X;
	vector<pair<ll,int>>mx;
	for (int i = 0; i < N; i++) {
		ll b = v[i][0];
		ll l = v[i][1];
		ll u = v[i][2];
		mx.pb({l*b + u*(X-b),i});
		sum += -l*b;
	}
	sort(all(mx));
	reverse(all(mx));

	vector<int>ra(N);
	int idx = -1;
	for (int i = 0; i < N; i++) {
		ra[mx[i].second] = i;
		if (i == q)idx = mx[i].second;
	}

	for (int i = 0; i < q; i++)sum += mx[i].first;

	ll res = -inf;
	if (idx == -1) {
		res = sum;
	}
	else {
		for (int i = 0; i < N; i++) {
			ll b = v[i][0];
			ll l = v[i][1];
			ll u = v[i][2];
			if (ra[i] >= q)res = max(res, sum + f(r, b, l, u) + l * b);
			else {
				ll bidx = v[idx][0];
				ll lidx = v[idx][1];
				ll uidx = v[idx][2];
				res = max(res, sum - u * (X - b) + f(r, b, l, u) + uidx * (X - bidx) + lidx * bidx);
			}
		}
	}
	return res >= 0;
}

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

	cin >> N >> X;
	for (int i = 0; i < N; i++) {
		vector<ll>temp(3);
		cin >> temp[0] >> temp[1] >> temp[2];
		v.pb(temp);
	}

	
	ll ng = -1, ok = N * X;
	while (ok - ng > 1) {
		ll mid = (ok + ng) / 2;
		if (check(mid))ok = mid;
		else ng = mid;
	}
	puts(ok);

	return 0;
}

Measured memory_bytes: 12436
import java.io.*;
import java.util.*;
import static java.lang.Math.*;

public class Main {
    public static void main(String[] args) {
        Main main = new Main();main.solve(args);
    }

    public void solve(String[] args) {
        MyScanner scanner = new MyScanner();
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        int c = scanner.nextInt();
        int d = scanner.nextInt();
        if (Math.abs(a - c) <= d ||
            (Math.abs(a - b) <= d &&
             Math.abs(b - c) <= d)) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }

    private class MyScanner {
        String[] s;int i;BufferedReader br;String reg = " ";
        MyScanner () { s = new String[0];i = 0;br = new BufferedReader(new InputStreamReader(System.in)); }
        public String next() {
            try {
                if (i < s.length) return s[i++]; String line = br.readLine();
                while (line.equals("")) {line = br.readLine();}
                s = line.split(reg, 0); i = 0;return s[i++];
            } catch (Exception e) {e.printStackTrace();}
            return null;
        }
        public int nextInt() {
            try {return Integer.parseInt(next());} catch (Exception e) {e.printStackTrace();}
            return -1;
        }
        public double nextDouble() {
            try {return Double.parseDouble(next());} catch (Exception e) {e.printStackTrace();}
            return -1;
        }
        public long nextLong()  {
            try {return Long.parseLong(next());} catch (Exception e) {e.printStackTrace();}
            return -1;
        }
    }
}


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

ll func(ll X){
  int n=X%4;
  if(n==0) return X;
  else if(n==1) return 1;
  else if(n==2) return X+1;
  else return 0;
}

int main(void){
  ll A,B;
  cin>>A>>B;
  ll X=func(A-1) ^ func(B);
  cout << X << endl;
  return 0;
}

Measured memory_bytes: 256
h,w=map(int,input().split())
s=[['.']*(w+2)]
for i in range(h):
    s+=[['.']+list(input())+['.']]
s+=[['.']*(w+2)]

dset=((-1,0),(0,1),(1,0),(0,-1))

for i in range(1,h+1):
    for j in range(1,w+2):
        if s[i][j]=='.':continue
        flag=False
        for y,x in dset:
            if s[i+y][j+x]=='#':
                flag=True
                break
        if not flag:
            print('No')
            exit()
print('Yes')

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

int main(){
    int x,ans=1;
    cin>>x;
    for(int i=2;i<=x;i++){
        for(int j=2;;j++){
            int p=(int)pow(i,j);
            if(p<=x)ans=max(ans,p);
            else break;
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n;
long long m;
map<long long,long long>mp;
long long a[100005];
int main()
{
    scanf("%d%lld",&n,&m);
    long long res=0,ans=0;
    mp[0]=1;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        res=(res+a[i])%m;
        ans+=mp[res];
        mp[res]++;
    }
    cout<<ans<<endl;
}

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

int main()
{
    int N;
    cin >> N;
    
    vector<pair<int, int>> works(N);

    for(int i = 0; i < N; i++){
        cin >> works[i].second >> works[i].first;
    }

    //sort
    std::sort(works.begin(), works.end());

    int time_sum = 0;
    for(int i = 0; i < N; i++){      
        time_sum += works[i].second;
        if(time_sum > works[i].first){
            cout << "No"<< endl;
            return 0;
        }    
    }

    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
struct UnionFind{
    vector<ll> par;
    UnionFind(ll n) : par(n, -1) { }
    void init(ll n) { par.assign(n, -1); }
    
    ll root(ll x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool issame(ll x, ll y) {
        return root(x) == root(y);
    }
    
    bool merge(ll x, ll y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    ll size(ll x) {
        return -par[root(x)];
    }
};

int main(){
  IOS;
  ll n,m;cin>>n>>m;
  vector<ll> p(n),x(m),y(m);
  rep(i,n){
    ll tmp;cin>>tmp;tmp--;
    p[tmp]=i;
  }
  rep(i,m) cin>>x[i]>>y[i],x[i]--,y[i]--;
  UnionFind uf(n);
  rep(i,m) uf.merge(x[i],y[i]);
  ll ans=0;
  rep(i,n) if(uf.issame(i,p[i])) ans++;
  cout<<ans<<endl;
}

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

int main(){
  int N;
  cin >> N;
  
  if(N%1111==0){
    cout << "Yes" << endl;
  }
  else if((N-(N-N%1000))%111==0){
    cout << "Yes" << endl;
  }
  else if((N-N%10)%111==0){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<char> vc;
typedef queue<ll> ql;
typedef deque<ll> dql;
typedef priority_queue<ll/*, vl, greater<ll>*/> pql; //降順(/*昇順*/)
typedef set<ll> sl;
typedef pair<ll, ll> pl;
typedef vector<vl> vvl;
typedef vector<pl> vpl;
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define rep2(i, n) for(ll i = 1; i <= ll(n); i++)
//#define rep(i, k, n) for(ll i = k-1; i < ll(n); i++)
//#define rep2(i, k, n) for(ll i = k; i <= ll(n); i++)
#define all(v) (v).begin(), (v).end()
bool chmin(ll &a, ll b) {if(b < a) {a = b; return 1;} return 0;}
bool chmax(ll &a, ll b) {if(b > a) {a = b; return 1;} return 0;}
const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;
const ll MAX = 1e9;
const char newl = '\n';

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

  ll n;
  cin >> n;
  vl a(n);
  rep(i, n) {
    cin >> a[i];
    if(a[i]==0) {cout << 0 << newl; return 0;}
  }
  
  ll ans=1;
  rep(i, n) {
    if(ans > 1000000000000000000/a[i]) {cout << -1 << newl; return 0;}
    ans *= a[i];
    if(ans > 1000000000000000000) {cout << -1 << newl; return 0;}
  }
  cout << (ans>1000000000000000000 ? -1 : ans) << newl;
  return 0;
}

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

int main() {
  char c;
  cin >> c;

  if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u')
    cout << "vowel" << endl;
  else
    cout << "consonant" << endl;
  return 0;
}

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

#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()

#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define REPS(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)

typedef pair<int, int> pint;

#define mp make_pair
#define mt make_tuple
#define pb push_back
#define pf push_front

#define MOD (1000 * 1000 * 1000 + 7)

double calc(
    vector<double> E,
    vector<double> P,
    vector< vector<int>> &edges,
    vector< vector<int>> &edges_rev,
    int N,
    int loss_s,
    int loss_t) {

        // cout << "---" << endl;
    double total = 0;
    for (int j: edges[loss_s]) {
        if (j == loss_t) continue;

        total += E[j] + 1;
        // cout << E[j] << endl;
    }
    double new_e = total / (SZ(edges[loss_s]) - 1);
    double diff = new_e - E[loss_s];
    // cout << new_e << endl;

    if (diff >= 0) return 100000000.0;

    return E[0] + diff * P[loss_s];
    // E[loss_s] = new_e;

    // RREP(i, loss_s) {
    //     double total = 0;
    //     for (int j: edges[i]) {
    //         total += E[j] + 1;
    //     }

    //     E[i] = total / SZ(edges[i]);
    // }

    // // REP(i, N) {
    // //     cout << i << ":  " << E[i] << endl;
    // // }

    // return E[0];
}

signed main() {
    int N, M;
    cin >> N >> M;

    vector<double> E(N, 0.0);
    vector<double> P(N, 0.0);
    vector< vector<int> > edges(N, vector<int>());
    vector< vector<int> > edges_rev(N, vector<int>());

    REP(i, M) {
        int s, t;
        cin >> s >> t;
        s--; t--;

        edges[s].pb(t);
        edges_rev[t].pb(s);
    }

    RREP(i, N-1) {
        int A = SZ(edges[i]);
        double total = 0;
        for (int j: edges[i]) {
            total += E[j] + 1;
        }

        E[i] = total / A;
    }

    P[0] = 1.0;
    REP(i, N-1) {
        double A = SZ(edges[i]);

        for (int j: edges[i]) {
            P[j] += P[i] / A;
        }
    }

    double ans = E[0];

    REP(i, N) {
        if (SZ(edges[i]) <= 1) continue;

        for (int j: edges[i]) {
            double e = calc(E, P, edges, edges_rev, N, i, j);
            ans = min(ans, e);
            // cout << i << ", " << j << ": " << e << endl;
        }
    }

    cout << setprecision(10) << ans << endl;

    // REP(i, N) {
    //     cout << i << ":  " << E[i] << ":" << P[i] << endl;
    // }

    return 0;
}

Measured memory_bytes: 2560
N, M, C = map(int, input().split())                                                                                                                         
B = list(map(int, input().split()))
 
S = [[0]*M for i in range(N)]
for i in range(N):
    S[i] = list(map(int, input().split()))

b = 0
 
for i in range(N):
    a = 0
    for ii in range(M):
        a += S[i][ii] * B[ii]
    a += C
    if a > 0:
        b += 1
print(str(b))

Measured memory_bytes: 3064
S = input()
T = input()

N = len(S)

RSi = [-1] * 26
RTi = [-1] * 26

a = ord("a")
flg = True
for i in range(N):
    Si = ord(S[i]) - a
    Ti = ord(T[i]) - a
    if RSi[Si] >= 0 and RSi[Si] != Ti:
        flg = False
    elif RSi[Si] < 0:
        RSi[Si] = Ti
    if RTi[Ti] >= 0 and RTi[Ti] != Si:
        flg = False
    elif RTi[Ti] < 0:
        RTi[Ti] = Si
    if not flg:
        break

if flg:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3632
def resolve():
    S = list(input())
    if len(S) == 2:
        if S[0] == S[1]:
            print(1, 2)
        else:
            print(-1, -1)
        return
    for i in range(len(S)-2):
        if S[i] == S[i+1] or S[i+1] == S[i+2] or S[i+2] == S[i]:
            print(i+1, i+3)
            return
    print(-1, -1)


if __name__ == '__main__':
    resolve()

Measured memory_bytes: 9872
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.InputMismatchException;
import java.util.StringTokenizer;

class Main {
	
	static class BinarySearch {
		static Node root = null;
		
		public void binarysearch (InputReader ir) {
			
			int m = ir.nextInt();
			
			for (int i = 0; i < m; i++) {
				String ord = ir.nextString();
				
				if (ord.equals("insert")) Insert (ir.nextInt());
				else if (ord.equals("print")) Print ();
				
			}
			
		}
		
		static void Insert (int k) {
			
			Node x = root;
			Node y = null;
			Node z = new Node ();
			
			z.key = k;
			while (x != null) {
				y = x;
				if (z.key < x.key) {
					x = x.left;
				} else {
					x = x.right;
				}
			}
			
			z.parent = y;
			
			if (y == null) {
				root = z;
			} else if (z.key < y.key) {
				y.left = z;
			} else {
				y.right = z;
			}
			
			
		}
		
		static void Print () {
			
			StringBuilder sb = new StringBuilder();
			
			Inorder (sb, root);
			System.out.println(sb);
			sb.setLength(0);
			Preorder (sb, root);
			System.out.println(sb);
		}
		
		static void Preorder (StringBuilder sb, Node root) {
			if(root == null) return;
	        sb.append(" ").append(root.key);
	        Preorder(sb, root.left);
	        Preorder(sb, root.right);
		}
		
		static void Inorder (StringBuilder sb, Node root) {
			if(root == null) return;
	        Inorder(sb, root.left);
	        sb.append(" ").append(root.key);
	        Inorder(sb, root.right);
		}
	}
	
	static class Node {
		Integer key = null;
		Node parent;
		Node left;
		Node right;
	}
	
	static class InputReader {
		BufferedReader br;
		StringTokenizer st;
		
		public String nextString() {
			
			 while (!st.hasMoreTokens()) {
	                try {
	                    st = new StringTokenizer(br.readLine(), " ");
	                } catch (IOException e) {
	                    throw new InputMismatchException();
	                }
	            }
			return st.nextToken();
		}
		
		public int nextInt() {
			return Integer.parseInt(nextString());
		}
					
		public InputReader (InputStream inputStream) {
			br = new BufferedReader (new InputStreamReader (inputStream));
			st = new StringTokenizer ("");
		}
		
	}
	
	public static void main (String[] args) {
		InputStream inputStream = System.in;
		InputReader in = new InputReader (inputStream);
		BinarySearch obj = new BinarySearch();
		obj.binarysearch(in);
	}
	
	
}



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

const int N = 1010;
const int M = 200005;
const int INF = 1e9;

int n, m;
int fr[M], to[M];
vector<int> g[N];
int low[N], num[N], step, scc;
stack <int> st;
int pos[N];
int vis[N];
bool curvis[N];
bool two[N][N];

void dfs(int u) {
	low[u] = num[u] = ++step;
	st.push(u);

	for (int &v : g[u]) {
		if (num[v]) low[u] = min(low[u], num[v]);
		else {
			dfs(v);
			low[u] = min(low[u], low[v]);
		}
	}

	if (low[u] == num[u]) {
		int v = 0;
		++scc;
		do {
			v = st.top(); st.pop();
			low[v] = num[v] = INF;
			pos[v] = scc;
		} while(v != u);
	}
}

vector<int> current;

void dfs2(int u) {
	vis[u]++;
	current.push_back(u);
	curvis[u] = true;

	for (int &v : g[u]) {
		if (curvis[v]) continue;
		if (vis[v] == 2) continue;
		dfs2(v);
	}
}

void solve(int s) {
	for (int i = 1; i <= n; ++i) vis[i] = 0;
	vis[s] = 2;
	
	for (int &v : g[s]) {
		current.clear();
		if (vis[v] < 2) dfs2(v);
		while(current.size()) {
			curvis[current.back()] = false;
			current.pop_back();
		}
	}

	for (int i = 1; i <= n; ++i) if (vis[i] == 2) two[s][i] = true;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		int u, v; cin >> u >> v;
		g[u].push_back(v);
		fr[i] = u;
		to[i] = v;
	}

	for (int i = 1; i <= n; ++i) if (!num[i]) dfs(i);

	for (int i = 1; i <= n; ++i) {
		solve(i);
	}

	for (int i = 0; i < m; ++i) {
		int u = fr[i], v = to[i];
		bool cur = (pos[u] != pos[v]);
		cur ^= two[u][v];
		
		// cut the i-th edge and check if there exists a directed path from u to v
		if (cur) {
			printf("same\n");
		} else {
			printf("diff\n");
		}
	}
}

Measured memory_bytes: 5376
#include <bits/stdc++.h>
using namespace std;
int main () {
  int N, M;
  cin >> N >> M;
  vector<pair<int,int>> human(N), check(M);
  for(int i = 0; i < N; i++) {
    cin >> human.at(i).first >> human.at(i).second;
  }
  for(int i = 0; i < M; i++) {
    cin >> check.at(i).first >> check.at(i).second;
  }
  long ans, num, sub;
  for(int i = 0; i < N; i++) {
    ans = 10000000000, num = -1;
    for(int j = 0; j < M; j++) {
      sub = abs(human.at(i).first - check.at(j).first) + abs(human.at(i).second - check.at(j).second);
      if(ans > sub) {
        ans = sub;
        num = j + 1;
      }
    }
    cout << num << endl;
  }
  return 0;
}


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

int dl[210][210];
int ds[210][210];
int dp[1010][210];
// 何回目、船の場所

void init(){
    for(int i=0; i<210; i++){
        for(int j=0; j<210; j++){
            if(i == j) dl[i][j] = ds[i][j] = 0;
            else dl[i][j] = ds[i][j] = 1e7;
        }
    }

    for(int i=0; i<1010; i++){
        for(int j=0; j<210; j++){
            dp[i][j] = 1e7;
        }
    }

    return ;
}

int main(){
    while(1){
        init();
        int n, m; cin>>n>>m;
        if(n == 0) return 0;

        for(int i=0; i<m; i++){
            int x, y, t; cin>>x>>y>>t;
            char s; cin>>s;
            x--, y--;

            if(s == 'L'){
                dl[x][y] = min(dl[x][y], t);
                dl[y][x] = min(dl[y][x], t);
            }
            else{
                ds[x][y] = min(ds[x][y], t);
                ds[y][x] = min(ds[y][x], t);
            }
        }

        int r; cin>>r;
        vector<int> z(r);
        for(int i=0; i<r; i++){
            cin>>z[i];
            z[i]--;
        }

        for(int k=0; k<n; k++){
            for(int i=0; i<n; i++){
                for(int j=0; j<n; j++){
                    dl[i][j] = min(dl[i][j], dl[i][k] + dl[k][j]);
                    ds[i][j] = min(ds[i][j], ds[i][k] + ds[k][j]);
                }
            }
        }

        dp[0][z[0]] = 0;

        for(int i=0; i<r-1; i++){
            for(int j=0; j<n; j++){
                int cur = z[i];
                int nxt = z[i+1];

                // cur -> land -> nxt
                dp[i+1][j] = min(dp[i+1][j], dp[i][j] + dl[cur][nxt]);
                    
                // cur -> land -> sea -> land -> nxtS
                for(int k=0; k<n; k++){
                    dp[i+1][k] = min(dp[i+1][k], dp[i][j] + dl[cur][j] + ds[j][k] + dl[k][nxt]);
                }
            }
        }

        int ans = 1e7;
        for(int i=0; i<n; i++){
            ans = min(ans, dp[r-1][i]);
        }

        cout << ans << endl;
    }
}


Measured memory_bytes: 4184
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int K = scanner.nextInt();
        String S = scanner.next();

        if (S.length() <= K) {
            System.out.println(S);
        } else {
            String truncated = S.substring(0, K);
            System.out.println(truncated + "...");
        }
    }
}

Measured memory_bytes: 38572
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<string>
#include<queue>
#include<utility>
#include<cmath>
#include<sstream>
#include<istream>

using namespace std;


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

  int ans = 0;

  for(int i=1; i<=N; i++){
    ans += i;
  }

  cout << ans << endl;

  return 0;
}


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

#define N_MAX 200

int main(){
	int N = 0;
	int L[N_MAX] = {0};
	int sum = 0;

	cin >> N;
	for(int i=0;i<N*2;i++){
		cin >> L[i];
	}

	sort(L,L+N*2);

	for(int i=0;i<N*2; i += 2){
		sum += L[i];
	}

	cout << sum << endl;

	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <array>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#define REP(X, Y, Z) for (ll(X) = (Y); (X) < (Z); (X)++)
#define REV(X, Y, Z) for (ll(X) = (Y); (X) > (Z); (X)--)

using namespace std;
using ll = long long;
using dll = deque<ll>;
using pll = pair<ll, ll>;
using qll = queue<ll>;
using usll = unordered_set<ll>;
using umll = unordered_map<ll, ll>;
using sll = stack<int>;
using vll = vector<ll>;
using vvll = vector<vll>;

constexpr ll kMax = 1e12 + 1;
constexpr ll kMod = 1e9 + 7;

ll gcd(ll a, ll b) {
  if (a < b) {
    return gcd(b, a);
  }
  ll c = a % b;
  while (c != 0) {
    a = b;
    b = c;
    c = a % b;
  }
  return b;
}

ll lcm(ll a, ll b) {
  return a / gcd(a, b) * b;
}

void init() {
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
}

ll fact(ll n) {
  ll ans = 1;
  while (n > 0) {
    ans = (ans * n) % kMod;
    n--;
  }
  return ans;
}

int main() {
  init();

  ll N, M;
  cin >> N >> M;

  ll ans = 1;
  if (abs(N - M) > 1) {
    cout << 0 << endl;
    return 0;
  }
  ans = (ans * fact(N)) % kMod;
  ans = (ans * fact(M)) % kMod;
  if (abs(N - M) == 0) {
    ans = (ans * 2) % kMod;
  } else {
    ans = (ans * 1) % kMod;
  }
  cout << ans << endl;

  return 0;
}


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


using namespace std;
#define rep(i,n) for (int i = 0; i < (int)(n); ++i)
#define reps(i,n) for (int i = 1; i <= (int)(n); ++i)
#define repd(i,n) for (int i = (int)(n - 1); i >= 0; --i)
#define repds(i,n) for(int i = (int)(n); i > 0; --i)
#define all(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
#define rall(f,x,...) ([&](decltype((x)) whole) { return (f)(rbegin(whole), rend(whole), ## __VA_ARGS__); })(x)
#define sz(a) (int)(a).size()
using ll = long long;
using ld = long double;
constexpr ll inf = static_cast<ll>(1e17);
constexpr int iinf = static_cast<int>(1e9);
constexpr ll MOD = static_cast<ll>(1e9 + 7);
ll mod = MOD;

using MatrixChild = std::vector<long long>;
using Matrix = std::vector<MatrixChild>;
Matrix matrixmul(Matrix& a, Matrix& b) {
    Matrix c(a.size(), MatrixChild(b[0].size()));

    for (int i = 0; i < (int)a.size(); ++i)
        for (int k = 0; k < (int)b.size(); ++k)
            for (int j = 0; j < (int)b[0].size(); ++j)
                c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % mod;

    return c;
}
Matrix matrixpow(Matrix a, long long n) {
    Matrix b(a.size(), MatrixChild(a.size()));

    for (int i = 0; i < (int)a.size(); ++i)
        b[i][i] = 1;

    while (n > 0) {
        if (n & 1)
            b = matrixmul(b, a);
        a = matrixmul(a, a);
        n >>= 1;
    }

    return b;
}


ll l, a, b;
void solve() {
    cin >> l >> a >> b >> mod;


    ll ten = 1;
    ll ans = 0;
    rep(i, 19) {
        ten *= 10;

        if (a >= ten)
            continue;

        auto num = min((ten - 1 - a) / b, l - 1) + 1;
        l -= num;

        if (num == 0) {
            if (l == 0)
                break;
            continue;
        }

        Matrix ansMat{
            { ans, a % mod, 1 }
        };

        Matrix mat{
            { ten % mod, 0, 0 },
            {   1, 1, 0 },
            {   0, b, 1 }
        };

        mat = matrixpow(mat, num);
        ansMat = matrixmul(ansMat, mat);
        ans = ansMat[0][0] % mod;
        a += b * num;
    }

    cout << ans % mod << endl;

    return;
}


int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);

    solve();

    return 0;
}


Measured memory_bytes: 256
using System;
using System.Linq;

class C
{
	static int[] Read() => Console.ReadLine().Split().Select(int.Parse).ToArray();
	static void Main()
	{
		n = int.Parse(Console.ReadLine());
		f = new int[n + 1];
		f[0] = 1;
		for (int i = 1; i <= n; i++)
			f[i] = i * f[i - 1];

		var p = GetOrder(Read());
		var q = GetOrder(Read());
		Console.WriteLine(Math.Abs(p - q));
	}

	static int n;
	static int[] f;
	static int GetOrder(int[] p)
	{
		var pi = 0;
		var pl = Enumerable.Range(1, n).ToList();
		for (int i = 0; i < n; i++)
		{
			var li = pl.IndexOf(p[i]);
			pi += li * f[n - 1 - i];
			pl.RemoveAt(li);
		}
		return pi;
	}
}


Measured memory_bytes: 13396
#include<bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define vi vector<int>
#define all(x) (x).begin(),(x).end()
#define INF (1<<30)-1
using ll = long long;
using namespace std;
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(){
  int n; cin >> n;
  vi cnt(n);
  rep(i,n){
    string s; cin >> s;
    if(s == "AC") cnt[0]++;
    if(s == "WA") cnt[1]++;
    if(s == "TLE") cnt[2]++;
    if(s == "RE") cnt[3]++;
  }
  cout << "AC x " << cnt[0] << endl;
  cout << "WA x " << cnt[1] << endl;
  cout << "TLE x " << cnt[2] << endl;
  cout << "RE x " << cnt[3] << endl;
  return 0;
}


Measured memory_bytes: 3780
S = input()
a,b,c,d = int(S[0]),int(S[1]),int(S[2]),int(S[3])
if a+b+c+d==7:print(str(a)+'+'+str(b)+'+'+str(c)+'+'+str(d)+'=7');exit()
if a-b+c+d==7:print(str(a)+'-'+str(b)+'+'+str(c)+'+'+str(d)+'=7');exit()
if a+b-c+d==7:print(str(a)+'+'+str(b)+'-'+str(c)+'+'+str(d)+'=7');exit()
if a+b+c-d==7:print(str(a)+'+'+str(b)+'+'+str(c)+'-'+str(d)+'=7');exit()
if a-b-c+d==7:print(str(a)+'-'+str(b)+'-'+str(c)+'+'+str(d)+'=7');exit()
if a-b+c-d==7:print(str(a)+'-'+str(b)+'+'+str(c)+'-'+str(d)+'=7');exit()
if a-b-c-d==7:print(str(a)+'-'+str(b)+'-'+str(c)+'-'+str(d)+'=7');exit()
if a+b-c-d==7:print(str(a)+'+'+str(b)+'-'+str(c)+'-'+str(d)+'=7');exit()

Measured memory_bytes: 62084
H, W = map(int, input().split())
A = [list(map(str, input())) for i in range(H)]


mod = 10 ** 9 + 7
dp = [[0 for _ in range(W)] for _ in range(H)]

dp[0][0] = 1
if A[0][1] == '.':
    dp[0][1] = 1
if A[1][0] == '.':
    dp[1][0] = 1


for h in range(H):
    for w in range(W):
        if A[h][w] == '.':
            if h * w > 0:
                dp[h][w] = (dp[h-1][w] + dp[h][w-1]) % mod
            elif h == 0 and w == 0:
                pass
            elif h == 0:
                dp[h][w] = dp[h][w-1]
            else:
                dp[h][w] = dp[h-1][w]


print(dp[H-1][W-1])

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

int main() {
  	int N, cnt = 0;
  	string S;
  	cin >> N >> S;
  	rep(i, 1000){
      	int c[3] = { i / 100, (i / 10) % 10, i % 10 };
      	int f = 0;
      	rep(j, N) {
        	if(S[j] == ('0' + c[f])) f++;
          	if (f == 3) break;
        }
      if (f == 3) cnt++;
    }
  	cout << cnt << endl;
    return 0;
}

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

#define REP(i, n) for(int (i) = 0; (i) < (n); ++(i))
#define REPR(i, n) for(int (i) = (n); (i) >= 0; --(i))
#define FOR(i, n, m) for(int (i) = (n); (i) < (m); ++(i))

// constexpr int INF = 1e9;
constexpr ll INF = 1LL<<61;
constexpr ll mod = 1e9+7;
int maxs = 2500;

vector<ll> dijkstra(vector<vector<pair<int, ll>>> g, int s){
  int n = g.size();
  vector<ll> dist(n, INF);
  dist[s] = 0;
  priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
  pq.push({0, s});
  while(!pq.empty()){
    auto[d, v] = pq.top(); pq.pop();
    if(d > dist[v]) continue;
    for(auto e : g[v]){
      auto[nv, c] = e;
      if(dist[nv] > dist[v]+c){
        dist[nv] = dist[v]+c;
        pq.push({dist[nv], nv});
      }
    }
  }
  return dist;
}
int main(){
  int N, M, S;
  cin >> N >> M >> S;
  S = min(S, 2499);
  vector<vector<pair<int, ll>>> g(N*2500);
  REP(i, M){
    int U, V, A, B;
    cin >> U >> V >> A >> B;
    U--, V--;
    FOR(j, A, maxs){
      g[U*maxs+j].push_back({V*maxs+j-A, B});
      g[V*maxs+j].push_back({U*maxs+j-A, B});
    }
  }
  REP(i, N){
    int C, D;
    cin >> C >> D;
    REP(j, maxs-C){
      g[i*maxs+j].push_back({i*maxs+j+C, D});
    }
  }
  vector<ll> dist = dijkstra(g, S);
  vector<ll> ans(N, INF);
  REP(i, N){
    REP(j, 2500){
      ans[i] = min(ans[i], dist[i*maxs+j]);
    }
  }
  FOR(i, 1, N){
    cout << ans[i] << endl;
  }
  return 0;
}


Measured memory_bytes: 37944
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (ll i = 0; i < n; ++i)
ll dx[4] = { 0, 1, 0, -1 };
ll dy[4] = { 1, 0, -1, 0 };
const ll INF = 1e14;
const ll MOD = 1e9 + 7;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll N;
    cin >> N;
    vector<ll> A(N);
    vector<ll> L(N + 1), R(N + 1);
    rep(i, N) { cin >> A[i]; }
    vector<ll> B(A);
    reverse(B.begin(), B.end());
    rep(i, N)
    {
        L[i + 1] = __gcd(L[i], A[i]);
        R[i + 1] = __gcd(R[i], B[i]);
    }
    ll ans = 0;
    rep(i, N) {
        ans = max(ans, __gcd(L[i], R[N - i - 1]));
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3456