akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
int main()
{
	string s,r;
	cin>>s>>r;
	int l,m;
	l=s.length();
	m=r.length();
	int dp[l+1][m+1];
	memset(dp,0,sizeof(dp));
	for(int i=0;i<l;i++)
	{
		for(int j=0;j<m;j++)
		{
			if(s[i]==r[j])
				dp[i+1][j+1]=dp[i][j]+1;
			else
				dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]);
	//		cout<<dp[i][j]<<" ";
		}
	}
	int len=dp[l][m];
//	cout<<len<<endl;
	string ans="";
	l--;m--;
	while(ans.size()<len && l>=0 && m>=0)
	{
		if(s[l]==r[m])
		{	ans+=s[l];	l--;	m--;	}
		else if(l>0 && m>0)
		{
			if(dp[l+1][m]>dp[l][m+1])
				m--;
			else	
				l--;
		}
		else
		{
			if(l==0)	m--;
			else	l--;
		}
//		cout<<ans<<" ";
	}
	reverse(ans.begin(),ans.end());
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 35456
def Ask(x):
    ans = 0
    while (x):
        ans += x % 10
        x //= 10
    return ans

def Check(x, y):
    return x * Ask(y) > y * Ask(x)


k = int(input())
no = st = 1
while (k):
    k -= 1
    print(no)
    if (Check(no + st, no + st * 10)): st *= 10
    no += st

Measured memory_bytes: 39280
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = (int)1e9+7;
const double PI = 3.14159265359;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int n;
	cin>>n;
	int deg[n+5];
	memset(deg,0,sizeof(deg));
	
	for(int i=2;i<=n;i++){
		int x;
		cin>>x;
		deg[x]++;
		deg[i]++;
	}
	for(int i=1;i<=n;i++){
		if(i==1){
			cout<<deg[i]<<"\n";
		}
		else{
			cout<<deg[i]-1<<"\n";
		}
	}
	
	return 0;
}
































Measured memory_bytes: 4448
import sys

num = int(sys.stdin.readline().strip())

r0 = int(sys.stdin.readline().strip())
r1 = int(sys.stdin.readline().strip())

max_dis = r1 - r0
min_num = min(r0, r1)

for i in range(0, num-2):
    r = int(sys.stdin.readline().strip())
    max_dis = max(max_dis, r - min_num)
    min_num = min(min_num, r)

print max_dis

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

using namespace std;

using ll = long long;

constexpr char newl = '\n';

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

    char c;
    cin >> c;
    cout << ((c >= 'A' && c <= 'Z') ? 'A' : 'a') << newl;

    return 0;
}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define loop(i, x, n) for (int i = (x); i < (n); i++)
#define all(v) (v).begin(), (v).end()
#define int long long
#define INF 1e9
using namespace std;
template<typename T> void cmin(T &a, T b) { a = min(a, b); }
template<typename T> void cmax(T &a, T b) { a = max(a, b); }

signed main() {
  int N, W, H;
  cin >> N >> W >> H;

  int X[200005] = {}, Y[200005] = {};

  rep(i, N) {
    int x, y, w;
    cin >> x >> y >> w;
    X[min(W, x + w)]--;
    X[max(0LL, x - w)]++;
    Y[min(H, y + w)]--;
    Y[max(0LL, y - w)]++;
  }

  rep(i, W + 1) X[i + 1] += X[i];
  rep(i, H + 1) Y[i + 1] += Y[i];

  bool a = true, b = true;
  rep(i, W) if (X[i] <= 0) a = false;
  rep(i, H) if (Y[i] <= 0) b = false;

  cout << ((a || b) ? "Yes" : "No") << endl;

  return 0;
}



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


int main(void) {
	int r, g, b, n;
	int  ans = 0;

	scanf("%d %d %d %d", &r, &g, &b, &n);

	for (int i = 0; i * r <= n; i++) {
		for (int j = 0; j * g <= n; j++) {
			//printf("i=%d  j=%d\n", i, j);
			if ((n - r * i - g * j) % b == 0 && n - r * i - g * j >= 0) {
			ans++;
			
			}
			//printf("n - r * i - g * j = %d\n", n - r * i - g * j);
			//printf("amari = %d\n", (n - r * i - g * j)%b);
		}
	}
	printf("%d", ans);
	return 0;
}


Measured memory_bytes: 128
import math

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    min_ind = a.index(min(a))

    start = [min_ind - x for x in range(k) if min_ind - x >= 0]
    end = [s+k-1 for s in start]

    ans = 10**6
    for s, e in zip(start, end):
        ans = min(ans, math.ceil(s/(k-1)) + math.ceil((n-(e+1))/(k-1)))

    print(ans+1)

main()

Measured memory_bytes: 20436
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REPLL(i, n) for (ll i = 0; i < (ll)(n); i++)
using namespace std;
template<class T>inline bool chmax(T &a, const T &b){if(a < b){a = b; return 1;}return 0;}
template<class T>inline bool chmin(T &a, const T &b){if(a > b){a = b; return 1;}return 0;}
typedef long long ll;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int A, B; cin >> A >> B;
  if(B%A == 0){
    cout << A+B << endl;
  }else{
    cout << B-A << endl;
  }
}


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

struct node
{
    int x,y;
    long long w;
};
vector<node>edge;
long long a[305][305],b[305][305],sum;
bool vis[305][305];
int n,prnt[305];

bool comp(node na,node nb)
{
    return  (na.w<nb.w);
}

void FW1()
{
    for(int k=1; k<=n; k++)
    {
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                b[i][j] = min(b[i][j],(b[i][k]+b[k][j]));
            }
        }
    }
    return;
}

void FW2()
{
    sum = 0;
    for(int k=1; k<=n; k++)
    {
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                long long x = a[i][j];
                long long y = a[i][k]+a[k][j];
                if(k!=i && k!=j && y==x)
                {
                    //cout<<i<<" "<<j<<endl;
                    vis[i][j] = vis[j][i] = true;
                }
                /*if(x!=y)    vis[i][j] = true;
                if(y==b[i][j])
                {
                    if(!vis[i][k])
                    {
                        sum += a[i][k];
                        vis[i][k] = vis[k][i] = true;
                    }
                    if(!vis[k][j])
                    {
                        sum += a[k][j];
                        vis[k][j] = vis[j][k] = true;
                    }
                }
                else if(x==b[i][j])
                {
                    if(!vis[i][j])
                    {
                        sum += a[i][j];
                        vis[i][j] = vis[j][i] = true;
                    }
                }*/
            }
        }
    }
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            if(!vis[i][j])  sum += a[i][j];
        }
    }
    sum /= 2;
    return;
}

/*
int find_p(int x)
{
    if(prnt[x]==x)  return  x;
    else    return  prnt[x] = find_p(prnt[x]);
}

void MST()
{
    int x,y,c=0;
    sort(edge.begin(),edge.end(),comp);
    for(int i=1; i<=n; i++) prnt[i] = i;
    for(int i=0; i<edge.size(); i++)
    {
        x = find_p(edge[i].x);
        y = find_p(edge[i].y);
        if(x!=y)
        {
            prnt[y] = x;
            sum += edge[i].w;
            c++;
            vis[x][y] = true;
        }
        if(c==n-1)  break;
    }
}

void ADD()
{
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            if(vis[i][j])   continue;
            if(a[i][j]<=b[i][j]) sum += a[i][j];
        }
    }
    return;
}
*/
long long check()
{
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            if(b[i][j]!=a[i][j])    return  -1;
            edge.push_back(node({i,j,b[i][j]}));
            //sum += b[i][j];
        }
    }
    FW2();
    //MST();
    //ADD();
    return  sum;
}

int main()
{
    int i,j;
    scanf("%d",&n);
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=n; j++)
        {
            scanf("%lld",&a[i][j]);
            b[i][j] = a[i][j];
        }
    }
    FW1();
    printf("%lld\n",check());
    return  0;
}


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

int main(){
  while(1){
    int m, f, r;
    cin>>m>>f>>r;
    if(m == -1 && f == -1 && r == -1) break;

    string ans;
    if(m == -1 || f == -1) ans = "F";
    else if(m + f >= 80) ans = "A";
    else if(m + f >= 65) ans = "B";
    else if(m + f >= 50) ans = "C";
    else if(m + f >= 30) {
      if(r >= 50) ans = "C";
      else ans = "D";
    }
    else ans = "F";
    cout<<ans<<endl;
  }

  return 0;
}



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

typedef long long ll;
const ll MOD = 998244353L;
const int MAX_N = 300;
const int MAX_R = MAX_N * MAX_N;

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

  return ret;
}

int main() {
  int N, a[MAX_N];

  std::cin >> N;
  int S = 0;
  for(int i = 0; i < N; ++i) {
    std::cin >> a[i];
    S += a[i];
  }

  static ll dp1[MAX_N][MAX_R + 1] = {}, dp2[MAX_N][MAX_R + 1] = {};
  dp1[0][0] = 2;
  dp1[0][a[0]] = 1;
  for(int i = 1; i < N; ++i) {
    for(int R = 0; R <= S; ++R) {
      dp1[i][R] = 2 * dp1[i - 1][R] % MOD;
      if(R - a[i] >= 0) {
        dp1[i][R] += dp1[i - 1][R - a[i]];
        dp1[i][R] %= MOD;
      }
    }
  }

  dp2[0][0] = 1;
  dp2[0][a[0]] = 1;
  if(S % 2 == 0) {
    for(int i = 1; i < N; ++i) {
      for(int R = 0; R <= (S + 1) / 2; ++R) {
        dp2[i][R] = dp2[i - 1][R];
        if(R - a[i] >= 0) {
          dp2[i][R] += dp2[i - 1][R - a[i]];
          dp2[i][R] %= MOD;
        }
      }
    }
  }

  ll ans = modpow(3, N) + (3 * dp2[N - 1][S / 2] % MOD);
  ans %= MOD;
  for(int R = (S + 1) / 2; R <= S; ++R) {
    ans -= 3 * dp1[N - 1][R] % MOD;
    ans %= MOD;
    if(ans < 0) ans += MOD;
  }

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


Measured memory_bytes: 420736
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int a,b,k=0,c=0;
    cin >> a >> b;
    while(k<=a || k<=b)
    {
        if(abs(a-k)==abs(b-k))
        {
            c++;break;
        }
        k++;
    }
    if(c!=0)
        cout << k << endl;
    else
        cout << "IMPOSSIBLE" << endl;
    return 0;
}


Measured memory_bytes: 3632
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        scanner.nextLine();
        int sum = 0;
        for(int x= 0; x<N; x++){
             sum = sum + scanner.nextInt();
        }
        System.out.println(sum-N);


    }

}


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

int n, ans;
int A[MAXN+5], B[MAXN+5], C[MAXN+5];

signed main() {
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> A[i];
  for (int i = 1; i <= n; i++) cin >> B[i];
  for (int i = 2; i <= n; i++) cin >> C[i];
  for (int i = 1; i <= n; i++) {
  	ans += B[A[i]];
  	if (i>1 && A[i] - A[i-1] == 1) ans += C[A[i]];
  }
  cout << ans << endl;
  return 0;
}

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

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

	long double l = 0.0L;
	for (int i = 0; i < n; i++) {
		l += 1.0L / a[i];
	}
	cout << fixed << setprecision(10) << 1.0L / l << endl;
}


Measured memory_bytes: 384
#pragma GCC optimize ("O3")
char buf[1<<20],*p;sz;
main()
{
	read(0,buf,1<<20);
	int N=0;
	for(;;)
	{
		char k=buf[sz++];
		if(k<'0')break;
		N=N*10+k-'0';
	}
	p=buf+sz;
	int s=0,f=0;
	for(int i=0;i<N;i++)
	{
		s+=!(-N&i)*(p[i]-'1');
		f|=p[i]=='2';
	}
	printf("%d\n",s&3>>f);
}

Measured memory_bytes: 1152
#include <iostream>
#include <iomanip>
#include <map>
#include <list>
#include <set>
#include <vector>
#include <utility>
#include <algorithm>
#include <queue>
#include <cstdint>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

constexpr ll inf = INT64_MAX / 4;
constexpr double pi = asin(1) * 2;
constexpr ll mod = 1000000007;

template<class T>
class set2 : public set<T> {
private:
    typename set<T>::iterator back_itr() {
        auto e = this->end();
        e--;
        return e;
    }

public:
    T front() {
        if (this->empty()) throw;
        return *this->begin();
    }

    T back() {
        if (this->empty()) throw;
        return *this->back_itr();
    }

    void erase_front() {
        if (!this->empty()) this->erase(this->begin());
    }

    void erase_back() {
        if (!this->empty()) this->erase(this->back_itr());
    }
};

int main() {
    int n, k, p[200000], r = 1;
    set2<int> a;
    list<int> b;
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> p[i];
    }
    
    b.push_front(1);
    for (int i = 0; i < n - 1; i++) {
        if (p[i + 1] > p[i]) (*b.begin())++;
        else b.push_front(1);
    }
    int c = 0;
    for (auto &e:b) if (e >= k) c++;
    if (c > 1) r -= c - 1;

    a.insert(p, p + k);

    for (int i = 0; i < n - k; i++) {
        if (p[i] != a.front() || p[i + k] < a.back()) r++;
        a.erase(p[i]);
        a.insert(p[i + k]);
    }

    cout << r << endl;
}


Measured memory_bytes: 13568
#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <random>
#include <functional>
#include <stack>
#include <iomanip>
#include <cassert>
//#include <boost/multiprecision/cpp_int.hpp>
#include <complex>
#include <cstdio>
#include <list>
#include <bitset>

//< in.txt > out.txt
using namespace std;
//std::ios::sync_with_stdio(false);
//std::cin.tie(0);
const long long MOD = 1e9 + 7;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ll> pdl;
typedef pair<ld, ld> pdd;
typedef vector<ll> VLL;
typedef vector<VLL> VVLL;
//typedef boost::multiprecision::cpp_int bigint;

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	ll A, B, C,D,E;
	cin >> A >> B;
	if (A != 1 && B != 1)cout << 1 << "\n";
	else if (A != 2 && B != 2)cout << 2 << "\n";
	else cout << 3 << "\n";
	return 0;
}

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

int cnt;

void merge(int A[], int l, int m, int r) {
	int n1 = m - l;
	int n2 = r - m;
	int *L = new int[n1];
	int *R= new int[n2];
	
	for (int i = 0; i < n1; ++i) {
		L[i] = A[l + i];
	}
	for (int i = 0; i < n2; ++i) {
		R[i] = A[m + i];
	}
	int i = 0;
	int j = 0;
	int k = l;
	for (; k < r; ++k) {
		if (i >= n1 || j >= n2) break;
		cnt++;
		if (L[i] <= R[j]) {
			A[k] = L[i];
			i++;
		} else { 
			A[k] = R[j];
			j++;
		}
	}
	while (k < r) {
		cnt++;
		if (i < n1) {
			A[k] = L[i];
			i++;
		} else {
			A[k] = R[j];
			j++;
		}
		k++;
	}
	delete[] L;
	delete[] R;
}

void merge_sort(int A[], int l, int r) {
	if (l + 1 < r) {
		int m = (l + r) / 2;
		merge_sort(A, l, m);
		merge_sort(A, m, r);
		merge(A, l, m, r);
	}
}

int main() {
	// your code goes here
	cnt = 0;
	int N;
	cin >> N;
	int* A = new int[N];
	for (int i = 0; i < N; ++i) {
		cin >> A[i];
	}
	merge_sort(A, 0, N);
	
	for (int i = 0; i < N; ++i) {
		cout << A[i];
		if (i < N - 1) {
			cout << " ";
		}
	}
	cout << endl;
	cout << cnt << endl;
	delete[] A;
	return 0;
}


Measured memory_bytes: 6808
from collections import Counter
N = int(input())
V = list(map(int,input().split()))

c1 = Counter(V[::2])
c2 = Counter(V[1::2])
m1 = c1.most_common()
m2 = c2.most_common()
t2 = N//2
t1 = N - t2

if len(m1) == len(m2) == 1:
    print(N//2 if m1[0][0] == m2[0][0] else 0)
elif len(m1) == 1:
    if m1[0][0] != m2[0][0]:
        print(t1 - m2[0][1])
    else:
        print(t1 - m2[1][1])
elif len(m2) == 1:
    if m1[0][0] != m2[0][0]:
        print(t2 - m1[0][1])
    else:
        print(t2 - m1[1][1])
else:
    if m1[0][0] != m2[0][0]:
        print(N - m1[0][1] - m2[0][1])
    else:
        ans = N - m1[1][1] - m2[1][1]
        if m1[0][0] != m2[1][0]:
            ans = min(ans, N - m1[0][1] - m2[1][1])
        if m1[1][0] != m2[0][0]:
            ans = min(ans, N - m1[1][1] - m2[0][1])
        print(ans)

Measured memory_bytes: 21184
#include <stdio.h>

int main(void)
{
    int i, j, t, a[5];
    for(i=0; i<5; i++) scanf("%d", &a[i]);

    for(i=0; i<5; i++) {
        for(j=0; j<4; j++) {
            if(a[j] < a[j+1]) {
                t = a[j];
                a[j] = a[j+1];
                a[j+1] = t;
            }
        }
    }

    printf("%d %d %d %d %d\n",a[0],a[1],a[2],a[3],a[4]);
    return (0);
}

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

int main() {
  int n, k;
  cin >> n >> k;
  int ans = 1;
  int num = k;
  while(n >= num) {
    num *= k;
    ans ++;
  }
  cout << ans << endl;
}


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

using namespace std;
using ll = long long;

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

  int n;
  cin >> n;
  vector<vector<pair<int, int>>> v(n);
  for (int i = 0; i < n; i++) {
    int a;
    cin >> a;
    for (int j = 0; j < a; j++) {
      int x, y;
      cin >> x >> y;
      x--;
      v[i].push_back({x, y});
    }
  }

  int ans = 0;
  for (int b = 0; b < (1 << n); b++) {
    bool f = true;
    for (int i = 0; i < n; i++) {
      if (!(b & (1 << i)))
        continue;
      for (auto [x, y] : v[i]) {
        if (((b & (1 << x)) > 0 && y == 0)) {
          f = false;
        } else if (((b & (1 << x)) == 0 && y == 1)) {
          f = false;
        }
      }
    }
    if (f) {
      ans = max(ans, __builtin_popcount(b));
    }
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3612
#include <iostream>
#include <cstdio>

using namespace std;

int main(){
  char b;
  scanf("%c", &b);
  if (b == 'A'){
    printf("T\n");
  }
  if (b == 'C'){
    printf("G\n");
  }
  if (b == 'G'){
    printf("C\n");
  }
  if (b == 'T'){
    printf("A\n");
  }
  return 0;
}


Measured memory_bytes: 256
#20:03
n,k = map(int,input().split())
s = input()
if s[0] == '1':
  can01 = [0]
  can10 = []
else:
  can01 = [0]
  can10 = [0]
for i in range(1,n):
  if s[i-1] == '0' and s[i] == '1':
    can01.append(i)
  elif s[i-1] == '1' and s[i] == '0':
    can10.append(i)
if s[n-1] == '1':
  can10.append(n)
else:
  can10.append(n)
  can01.append(n)
#print(can01,can10)
can01 = [0] * k + can01
can10 = can10 + [n] * k
#print(can01,can10)
ans = []
for i in range(len(can10)):
  ans.append(can10[i] - can01[i])
print(max(ans))

Measured memory_bytes: 10492
import java.util.*;
import java.io.*;
import java.util.function.*;

public class Main {
	public final int MOD = (int)1e9 + 7;
	int[] weight;
	int[] value;
	public void solve(BufferedReader br) throws IOException {
		int[] nw = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		int N = nw[0];
		int W = nw[1];
		weight = new int[N + 1];
		value = new int[N + 1];
		for (int i = 0; i < N; i++) {
			int[] wv = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
			weight[i + 1] = wv[0];
		   	value[i + 1] = wv[1];
		}
		int sum_of_value = 0;
		for (int i = 1; i <= N; i++) sum_of_value += value[i];
		//System.out.println(sum_of_value);
		System.out.println(findZeroOneKanpsack(N, W, sum_of_value));	
	}	

	public long findZeroOneKanpsack(int n, int w, int size) {
		// dp[i] stores the minimum weight that we can have with size exactly value i
		long[] dp = new long[size + 1];
		Arrays.fill(dp, (long) 1e18 + 7);
		dp[0] = 0;		
		for (int i = 1; i <= n; i++) {
			for (int j = size; j >= value[i]; j--) {
				dp[j] = Math.min(dp[j], weight[i] + dp[j - value[i]]);
			}	
		}
		long ans = 0;
		for (int i = 0; i <= size; i++) {
			if (dp[i] <= w) ans = Math.max(ans, i);
		}
		//for (int i = 0; i <= size; i++) System.out.println(i + " " +dp[i]);
		return ans;
	}
	
	public long mathPow(long base, long exp, long mod) {
		long res = 1;
		base = base % mod;
		while (exp > 0) {
			if ((exp & 1) == 1) res = (res * base ) % mod;
			exp = exp >> 1;
			base = (base * base) % mod;
		}
		return res;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		new Main().solve(br);
	}
}



Measured memory_bytes: 28116
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#define REP(i,n) for(int i=0;i<n;i++)

typedef unsigned long ul;
using namespace std;

string s;

int main() {
    cin >> s;
    for (int i = 0; i < 3; ++i) {
        if (s[i] == '1') s[i] = '9';
        else s[i] = '1';
    }
    cout << s;
    return 0;
}


Measured memory_bytes: 256
N=int(input())
A=list(map(int,input().split()) )
import math

se = A[0]
for i in range(1,N):
    se = math.gcd(se,A[i])
set_wise = se==1

NMAX = 10**6+2
divisors = [i for i in range(NMAX+1)]
p=2
while p*p <=NMAX:
    if divisors[p]==p:
        for r in range(2*p,NMAX+1,p):
            if divisors[r]==r:
                divisors[r]=p
    p+=1
    
from collections import defaultdict
def soinsu_osak(to_devide):
    d = defaultdict(int)
    while to_devide>1:
        d[divisors[to_devide]]+=1
        to_devide //= divisors[to_devide]
    return list(d.keys())

been=[0]*NMAX
pair_wise=True
f=False
for aa in A:
    soinsu = soinsu_osak(aa)
    for s in soinsu:
        if been[s]==0:
            been[s]=1
        else:
            pair_wise=False
            f=True
            break
    if f:
        break

if pair_wise:
    print("pairwise coprime")
elif set_wise:
    print("setwise coprime")
else:
    print("not coprime")

Measured memory_bytes: 220568
#include<bits/stdc++.h>
using namespace std;
int main(){int i,n,m,l,r,c;
cin>>n>>m;
c=m;
l=1;
r=m+2;
for(i=1;i<=m;i++){
    if(i%2){
        cout<<l<<" "<<l+c<<"\n";
        c--;l++;
    }else{cout<<r<<" "<<r+c<<"\n";
        c--;r++;
    }
}
    return 0;
}

Measured memory_bytes: 3604
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>

using namespace std;


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

int dpanel[8][10][10];
int h,w,pmax,lastcol;
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};


int _count(const int panel[10][10], int visit[10][10], int col, int x,int y){
	int sum = 0;
	if(x<0 || y<0 || x>=w || y>=h)return sum;
	
	if(visit[y][x]==1)return sum;
	visit[y][x]=1;
	
	if(panel[y][x]==col){
		sum++;
		rep(i,4){
			sum += _count(panel, visit, col, x+dx[i], y+dy[i]);
		}
	}
	return sum;
}
int count(const int panel[10][10]){
	int visit[10][10];
	rep(i,10)rep(j,10)visit[i][j]=0;
	
	return _count(panel, visit, panel[0][0], 0, 0);
}
void _change(int panel[10][10], int first, int col,int x,int y){
	if(x<0 || y<0 || x>=w || y>=h)return;
	
	if(panel[y][x]==first){
		panel[y][x]=col;
		rep(i,4){
			_change(panel ,first,col,x+dx[i],y+dy[i]);
		}
	}
}
void change(int panel[10][10], int col){
	if(panel[0][0]==col)return;
	_change(panel, panel[0][0], col, 0, 0);
}

void copy(int b1[10][10], int b2[10][10]){
	rep(i,10)rep(j,10)b1[i][j]=b2[i][j];
}

void print(int b[10][10]){
	static int c = 0;
	printf("c=%d\n",c);
	c++;
	
	rep(i,h){
		rep(j,w){
			printf("%d ",b[i][j]);
		}puts("");
	}puts("");
}

int saiki(int depth){
	copy(dpanel[depth] ,dpanel[depth-1]);
	
	if(depth == pmax+1){
		if(dpanel[depth][0][0]!=lastcol)return 0;
		return count(dpanel[depth]);
	}
	
	int maxi = 0;
	reps(col,1,7){
		change(dpanel[depth], col);
		int ret = saiki(depth+1);
		maxi = max(maxi, ret);
		
		copy(dpanel[depth] ,dpanel[depth-1]);
	}
	
	return maxi;
}


int main(){
	while(1){
		pmax = 5;
		cin>>h>>w>>lastcol;
		if(h==0)break;
		
		rep(i,h){
			rep(j,w){
				cin>>dpanel[0][i][j];
			}
		}
		
		int ans = saiki(1);
		printf("%d\n",ans);
	}
}

Measured memory_bytes: 1148
import core.bitop, std.algorithm, std.ascii, std.bigint, std.conv, std.math,
    std.functional, std.numeric, std.range, std.stdio, std.string, std.random,
    std.typecons, std.container, std.format;

// dfmt off
T lread(T = long)(){return readln.chomp.to!T();}
T[] aryread(T = long)(){return readln.split.to!(T[])();}
void scan(TList...)(ref TList Args){auto line = readln.split();
foreach (i, T; TList){T val = line[i].to!(T);Args[i] = val;}}
alias sread = () => readln.chomp();enum MOD = 10 ^^ 9 + 7;
alias PQueue = BinaryHeap!(Array!long, "a<b");
// dfmt on

void main()
{
    long R = lread();
    writeln(R*R);
}


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

int n, k, a, b, arr[1000], ans=0;

int main() {
  cin>>n>>k; 
  for(int i=0; i<k; i++) {
    cin>>a;
    for(int j=0; j<a; j++) {
      cin>>b; arr[b]++;
    }
  }
  for(int i=1; i<=n; i++) {
    if(arr[i]==0) ans++;
  }
  cout<<ans<<"\n";
  return 0;
}


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

int main() {
  string col;
  int N;
  cin >> N;
  
  for (int i = 0; i < N; i++) {
    cin >> col;
  
    if (col == "Y") {
      cout << "Four" << endl;
      return 0;
    }
  }
  cout << "Three" << endl;
}


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

int main() {
    int n;
    cin >> n;
    vector<int>a(n);
    vector<int>b(n);
    vector<int>c(n);
    vector<int>dpa(n);
    vector<int>dpb(n);
    vector<int>dpc(n);
    for (int i=0;i<n;i++){
        cin >> a[i] >> b[i] >> c[i];
        if (i==0) {
            dpa[i] = a[i];
            dpb[i] = b[i];
            dpc[i] = c[i];
        }
        else {
            dpa[i] = a[i] + max(dpb[i-1], dpc[i-1]);
            dpb[i] = b[i] + max(dpa[i-1], dpc[i-1]);
            dpc[i] = c[i] + max(dpb[i-1], dpa[i-1]);
        }
    }

    cout << max( max(dpa[n-1],dpb[n-1]), dpc[n-1]);
}

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

typedef long long ll;
const int MAX = 2e5 + 5;
int N, K, H[MAX];

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

    cin >> N >> K;
    for(int i = 0; i < N; i++) cin >> H[i];
    sort(H, H + N);

    ll ans = 0;
    for(int i = 0; i < N - K; i++) ans += H[i];

    cout << ans << '\n';
    return 0;
}


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

int main(){
  int a,b,c;
  
  cin >> a >> b >> c;
  
  if(a==b&&b!=c)
    cout << "Yes" << endl;
  else if(a==c&&a!=b)
    cout << "Yes" << endl;
  else if(b==c&&a!=b)
    cout << "Yes" << endl;
  else
    cout << "No" <<endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
#include <iomanip>
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 int mod=1000000007;
const int INF=1001001001;

int main() {
  int N;
  cin>>N;
  vector<int>X(N);
  for(int i=0;i<N;i++){
    cin>>X[i];
  }
  int ans=INF;
  for(int p=1;p<=100;p++){
    int sum=0;
    for(int i=0;i<N;i++){
      sum+=(p-X[i])*(p-X[i]);
    }
    chmin(ans,sum);
  }
  cout<<ans<<endl;
  return 0;  
}

Measured memory_bytes: 3632
n = int(input())
BTC = 380000.0
total = 0

for _ in range(n):
    x, u = list(map(str, input().split(' ')))
    x = float(x)
    if u == 'JPY':
        total += x
    if u == 'BTC':
        total += (x * BTC)

print(total)


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

int main() {
   int A,B,C,D;
    cin >> A >> B >> C >>D;
    if(A+B > C+D){
        cout<<"Left"<<endl;
    
    }
    else if(A+B==C+D){
        cout<<"Balanced"<<endl;
        
    }
    else{
        cout<<"Right"<<endl;
    }
 }


Measured memory_bytes: 256
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		int a=in.nextInt(),b=in.nextInt(),n=in.nextInt();
		boolean j=true;

		for(int i=0;i<n;i++){
			int s=in.nextInt(),f=in.nextInt();
			if(!(s<a && f<=a) && !(s>=b && f>b)) {
				j=false;
			}
		}

		if(j)System.out.println(0);
		else System.out.println(1);
	}
}


Measured memory_bytes: 26632
def main():
  
  n,k=map(int,input().split())
  a=tuple(map(int,input().split()))
  
  count=lambda arr,now:sum(element<now for element in arr)
  
  ans=0
  prime=10**9+7
  
  for i in range(n):
    left=count(a[:i],a[i])
    right=count(a[i+1:],a[i])
    res=(k-1)*k//2*(right+left)+right*k
    ans+=res%prime
    
  print(ans%prime)

if __name__=="__main__":
  main()

Measured memory_bytes: 3188
def answer(x: int) -> int:
    if x < 4 :
        return 1

    result = 1
    for b in range(2, x + 1):
        for p in range(2, x + 1):
            exp = pow(b, p)
            if exp <= x:
                result = max(result, exp)
            else:
                break

    return result


def main():
    x = int(input())
    print(answer(x))


if __name__ == '__main__':
    main()


Measured memory_bytes: 9176
import sys

def enum_div(n):
    ir=int(n**(0.5))+1
    ret=[]
    for i in range(1,ir):
        if n%i == 0:
            ret.append(i)
            if (i!= 1) & (i*i != n):
                ret.append(n//i)
    return ret

from collections import deque    
#    q = deque(l)
#    q.append(4) # 後ろから4を挿入, l=deque([0,1,2,3,4])
#    q.appendleft(5)#前から5を挿入, l=deque([5,0,1,2,3,4])
#    x = q.pop() #後ろの要素を取り出す, x=4, l=deque([5,0,1,2,3])
#    y = q.popleft() # 前の要素を取り出す, y=5, l = deque([0,1,2,3])

def get_primenumber(number):#エラトステネスの篩
    prime_list = []
    search_list = deque(list(range(2,number+1)))
#    search_list = list(range(2,number+1))
    #search_listの先頭の値が√nの値を超えたら終了
#    while search_list[0] <= math.sqrt(number):
    while search_list[0]**2 <= number:
      #search_listの先頭の値が√nの値を超えたら終了
      #search_listの先頭をprime_listに入れて、先頭をリストに追加して削除
        head_num = search_list.popleft()
#        head_num = search_list.pop(0)
        prime_list.append(head_num)
        #head_numの倍数を除去
        search_list =deque( [num for num in search_list if num % head_num != 0])
    #prime_listにsearch_listを結合
    prime_list.extend(search_list)
    return prime_list

n=int(input())
ap=list(map(int,input().split()))
amin=min(ap)
amax=max(ap)

if amax==1:
    print("pairwise coprime")
    sys.exit()

if amin!=1:
    bp=enum_div(amin)+[amin]
    bp.sort()
    bp=bp[1:]
    for bpi in bp:
        yn=""
        for ai in ap:
            if ai%bpi!=0:
                yn="coprime"
                break
        if yn=="":
            print("not coprime")
            sys.exit()

if n>=78500 :
    print("setwise coprime")
    sys.exit()

aa=[0]*(amax+1)
for ai in ap:
    aa[ai]+=1

p=get_primenumber(amax)

for pp in p:
#for pp in range(2,amax+1):
    psum=sum(aa[pp: :pp])
#    print("pp:",pp,psum)
    if psum>=2:
            print("setwise coprime")
            sys.exit()
## max_13.txt ... max_16.txt : "setwise coprime"
print("pairwise coprime")
   


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

string get_lower(string str, int size){
  for (int j=0;j<size;j++){
    str.at(j) = (char)tolower(str.at(j));
  }
  return str;
}

int main(){
  string W, T;
  cin >> W;
  int cnt = 0;
  while ((cin >> T)&&(T != "END_OF_TEXT")){
    T = get_lower(T, T.size());
//    cout << T << endl;
    if (T == W) cnt += 1;
  }
  cout << cnt << endl;
  return 0;
}


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

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;

#define imx INT_MAX
#define imn INT_MIN
#define llmx LLONG_MAX
#define llmn LLONG_MIN
#define INF         100000000000000000
#define PI          3.1415926535897932384626433832795l



#define fi first
#define se second
#define pb push_back
#define f_s(a) sort(a.begin(), a.end())
#define b_s(a) sort(a.rbegin(), a.rend())
#define p(a) cout<<a<<"\n"


// ll mod = 1000000007;
// #define l(i, )
// #define rl(i, a, b) for(int i = a; i < b; i++)






// struct mycomp {
//     bool operator() (const pair<int,int> &a, const pair<int,int> &b) const{
//         if (a.second-a.first != b.second-b.first)
//         return (a.second-a.first > b.second-b.first);
//         return a.first < b.first;
//     }
// };



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


ll extended_gcd(ll a, ll b, ll& x, ll& y)
{
	if(b==0)
	{
		x=1;
		y=0;
		return a;
	}
	ll x1, y1;
	ll d = extended_gcd(b, a%b, x1, y1);
	x=y1;
	y=x1-y1*(a/b);
	return d;
}

////////////////////SIEVE OF ERATOSTHENES//////////////////////
vector<int> sieveoferatosthenes(int n)
{
	vector<bool> prime(n+1, true);
	for(int i = 2; i <= sqrt(n); i++)
	{
		if(prime[i])
		{
			for(int j = i*i; j<=n; j+=i)
			{
				prime[j]=false;
			}
		}
	}	
	vector<int> all_primes;
	for(int i = 2; i <=n; i++)
	{
		if(prime[i]) all_primes.pb(i);
	}
	return all_primes;
}

////////////////////BINARY EXPONENTIATION///////////////////////
ll bin_exp(ll a, ll b, ll mod)
{
	ll ans = 1;
	while(b)
	{
		if(b%2)
		{
			b--;
			ans = (ans%mod*a%mod)%mod;
		}
		b/=2;
		a = (a%mod*a%mod)%mod;
	}
	return ans;
}


///////////////////////////BFS//////////////////////////////////
void bfs(vector<int>& distance, vector<int> a[], vector<bool>& visited, int u, vector<int>& parent)
{
	visited[u]=true;
	parent[u]=-1;
	distance[u]=0;
	queue<int> q;

	q.push(u); 
    while (!q.empty()) { 
  
        int f = q.front(); 
        q.pop(); 
  		for(int i =0; i < a[f].size(); i++)
  		{
  			if(visited[a[f][i]]==false)
  			{
  				distance[a[f][i]]=distance[f]+1;
  				parent[a[f][i]]=f;
  				visited[a[f][i]]=true;
  				q.push(a[f][i]);
  			}
  		}
    } 

}

void solve()
{

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

	// #ifndef ONLINE_JUDGE
	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);
	// #endif
	ll n, ans=0;
	cin>>n;
	const ll N = 10000000;
	vector<ll> divisors(n+1);

	for (ll i = 2; i <= n; i++) {
  	for (ll j = i; j <= n; j += i) {
    	divisors[j]++;
  		}
	}
	for(int i = 0; i < n; i++)
	{
		ans+=(i+1)*(divisors[i+1]+1);
	}
	p(ans);
	return 0;
}

Measured memory_bytes: 81308
s=int(input())
if s<3:
  print(0)
  exit()
  
dp=[0]*(s+1)
dp[0]=1

for i in range(3,s+1):
  dp[i]=dp[i-1]+dp[i-3]
print((dp[s-1]+dp[s-3]) % (10**9+7))

Measured memory_bytes: 63692
#include <bits/stdc++.h>
#define rep(i,n) for(long long i=0; i<n; i++)
#define Rep(i,n) for(long long i=1; i<n; i++)
#define ll long long
#include <math.h>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <queue>
#include <set>
#include <vector>


using namespace std;
#define PI acos(-1)
using P =pair<int,int>;

ll f(ll x,ll c,ll d){
    ll res =x;
    res -=x/c;
    res -=x/d;
    res+= x/lcm(c,d);
    return res;
}

vector<int> to[100005];
const ll inf =100000000;
int main(){
   ll  n,m;
   cin>>n>>m;
   rep(i,m){
       ll a,b;
       cin>>a>>b;
       a--;b--;
       to[a].push_back(b);
       to[b].push_back(a);
   }
   queue<int>q;
   vector<int> dist(n,inf);
   vector<int> pre(n,-1);
   dist[0]=0;
   q.push(0);
   while(!q.empty()){
       int v=q.front();
       q.pop();
       for(int u:to[v]){
           if(dist[u]!=inf)continue;
           dist[u]=dist[v]+1;
           pre[u]=v;
           q.push(u);
       }
   }
   cout<<"Yes"<<endl;
 
   Rep(i,n){
       cout<<pre[i]+1<<endl;
   }
}


Measured memory_bytes: 10588
#include<stdio.h>
#include<algorithm>
using namespace std;
int min(int x,int y)
{
    return x<y?x:y;
}
int max(int x,int y)
{
    return x>y?x:y;
}
int n,m,a[100010],d[100010],ans;
int main()
{
    scanf("%d %d",&n,&m);
    if(n>=m)
    {
        printf("0");
        return 0;
    }
    for(int i=0;i<m;i++)
    {
        scanf("%d",&a[i]);
    }
    sort(a,a+m);
    for(int i=0;i<m-1;i++)
    {
        d[i]=a[i+1]-a[i];
    }
    sort(d,d+m-1);
    int st=d[m-n-1];
    int e;
    for(int i=0;i<m-1;i++)
    {
        if(d[i]==st&&d[i+1]!=st)
        {
            e=i;
        }
    }
    int k=e-m+n+1;
    int x=a[0];
    int y;
    for(int i=0;i<m;i++)
    {
        if(i==m-1)
        {
            y=a[i];
            ans+=y-x;
        }
        else if(a[i+1]-a[i]>st)
        {
            y=a[i];
            ans+=y-x;
            x=a[i+1];
        }
        else if(a[i+1]-a[i]==st&&k>0)
        {
            y=a[i];
            ans+=y-x;
            x=a[i+1];
            k--;
        }
    }
    printf("%d",ans);
}

Measured memory_bytes: 896
#include<bits/stdc++.h>
#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 fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
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; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/



int v[3];
//---------------------------------------------------------------------------------------------------
void _main() {
    rep(i, 0, 3) cin >> v[i];
    
    int odd = 0, even = 0;
    rep(i, 0, 3) {
        if (v[i] % 2 == 0) even++;
        else odd++;
    }

    int ans = 0;

    // 調整
    if (odd == 2) {
        ans++;
        rep(i, 0, 3) if (v[i] % 2 == 1) v[i]++;
    } else if (even == 2) {
        ans++;
        rep(i, 0, 3) if (v[i] % 2 == 0) v[i]++;
    }

    int ma = max(v[0], max(v[1], v[2]));
    rep(i, 0, 3) ans += (ma - v[i]) / 2;
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <list>
#include <queue>
#include <tuple>
#include <deque>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <utility>
#include <complex>
#include <functional>
using namespace std;
const int MOD = 1000000007;
typedef long long ll;
typedef pair<ll, ll> p;
const int INF = (1 << 28);
const int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
const int Dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, Dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
int n;
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;

    vector<ll> count(2*100000,0);
    ll dp[n+1];
    dp[0]=1;
    int before=-1;
    for (int i = 1; i <= n; i++)
    {
        int temp;
        cin >> temp;
        dp[i]=dp[i-1];
        if(before==temp)continue;
        before=temp;
        //if(count[temp].size()!=0){
            /*
            for(auto iter=count[temp].begin();iter!=count[temp].end();iter++){
                if(i-*iter>1){
                    dp[i]+=dp[*iter-1];
                    dp[i]%=MOD;
                }
            }
            */
        dp[i]+=count[temp];
        dp[i]%=MOD;
        //}
        count[temp]+=dp[i-1];
        count[temp]%=MOD;
    }
    cout << dp[n] << "\n";
}


Measured memory_bytes: 3328
import collections
N, Q = map(int, input().split())
counts = [0] * (N + 1)
T = [[] for _ in range(N + 1)]
for _ in range(N-1):
  a, b = map(int, input().split())
  T[a].append(b)
  T[b].append(a)
for _ in range(Q):
  p, x = map(int, input().split())
  counts[p] += x
visited = [0] * (N + 1)
queue = collections.deque()
queue.append(1)
while queue:
  v = queue.pop()
  visited[v] = 1
  x = counts[v]
  for child in T[v]:
    if visited[child] == 1:
      continue
    counts[child] += x
    queue.append(child)
print(*counts[1:])

Measured memory_bytes: 56060
import java.util.*;
import java.io.*;
 
public class Main{
    public static void main(String[] args){
        Main m = new Main();
        m.input();

    }
 
    int ans,tmp;
    public void input(){
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int k = sc.nextInt();
        ArrayList<Integer> ansList = new ArrayList<Integer>();
        for(int i = 0; i < k; i++){
            ansList.add(a + i);
            if(a + i == b){
                break;
            }
        }
        for(int i = 0; i < k; i++){
            if(ansList.contains(b - i)){
                break;
            }
            ansList.add(b - i);
        }
        Collections.sort(ansList);
        for(int i = 0; i < ansList.size(); i++){
            System.out.println(ansList.get(i));
        }
        sc.close();
    }

}

Measured memory_bytes: 22356
#include<stdio.h>

void print();

int n,i,j;
int Adj[100][100];

int main() {

  int u,k,v;

  scanf("%d",&n);

  for( i=0 ; i<n ; i++)
    for( j=0 ; j<n ; j++)
      Adj[i][j] = 0;

  for( i=0 ; i<n ; i++){
    scanf("%d%d", &u, &k);
    for( j=0 ; j<k ; j++) {
      scanf("%d", &v);
            Adj[i][v-1] = 1;
    }
  }
  print();
  
  return 0;
}

void print() {
  for( i=0 ; i<n ; i++ ){
    for( j=0 ; j<n ; j++ ) {
      printf("%d", Adj[i][j]);
      if(j != n-1) printf(" ");
    }
    printf("\n");
  }
}

Measured memory_bytes: 636
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
int main()
{
    long long int x,i;
    scanf("%lld",&x);
    long long int ans;
    long long int principle=100;
    long long int compounded;
    for(i=1;;i++)
    {
        compounded=(principle+(principle/100));
        principle=compounded;
        ans=compounded;
        if(ans>=x)
        break;
    }
    printf("%lld",i);
}

Measured memory_bytes: 1732
import java.io.*;
import java.util.Arrays;
import java.util.Scanner;
import java.util.HashMap;
import java.util.Map;
public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int x=scan.nextInt();
        int y=scan.nextInt();
        while(x>0&&y>0){
            for(int i=0;i<x;i++){
                for(int j=0;j<y;j++){
                    System.out.print('#');
                }
                System.out.println();
            }
            x=scan.nextInt();
            y=scan.nextInt();
            System.out.println();
        }
    }
}


Measured memory_bytes: 39492
#include<bits/stdc++.h>
using namespace std;
stack<int> st;

int main(){
	int n,a,b,x,y,all;
	cin >> n >> a >> b;
	x = n - a;
	y = b - 1;
	if(x <= 0 || y <= 0){
		if(x == 0 && y == 0) for(int i = 1;i <= n;i++) cout << i << ' ';
		else cout << "-1" << endl;
	}
	else if((x % y == 0 && x / y > a) || (x % y != 0 && x / y + 1 > a) || y > x) cout << "-1" << endl;
	else{
		int cnt = a + 1;
		while(--cnt) st.push(cnt);
		all = n - a;
		cnt = n - (b - 2);
		while(true){
			while(cnt <= a) cnt++;
			int ans = cnt;
			for(int i =  1;i <= b - 1 && all >= 1;i++) st.push(ans++),all--;
			if(all <= 0) break;
			cnt -= (b - 1);
			while(cnt <= a) cnt++;
		}
		while(!st.empty()){
			cout << st.top() << ' ';
			st.pop();
		}
	}
}

Measured memory_bytes: 3276
parseInt(x) = parse(Int, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)

function main()
	n,m = readline() |> split |> parseMap
	a = Array{Int}(2,m)
	for i in 1:m
		a[:,i] = readline() |> split |> parseMap
	end
	a = sortcols(a, by=x->x[1],rev=true)
	count = 0
	mcut = n
	for i in 1:m
		if a[2,i] <= mcut
			count += 1
			mcut = a[1,i]
		end
	end
	println(count)
end

main()


Measured memory_bytes: 180740
/*
 * @Author: AsilenceBTF
 * @Buff: ︿(￣︶￣)︿  芜湖塔台 起飞
 * @Date: 2019-06-20 09:22:24
 * @LastEditTime: 2020-09-16 10:14:55
 */

#include <bits/stdc++.h>
using namespace std;
#define sz(x) int(x.size())
#define ALL(x) x.begin(), x.end()
#define INF 0x3f3f3f3f
#define debug(x) cout << "##### " << x << endl; 
typedef long long ll;

// #define cin in
// #define cout out
// ifstream in("in.txt");
// ofstream out("out.txt");

const int N = 2e5 + 105;
int main(){
    int x; cin >> x;
    cout << 1 - x << endl;
}

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

// types
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
typedef vector<ll> vll;

// macros
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define FI first
#define SE second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define REP1(i,n) for(int i=1;i<((int)n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define PB push_back
#define EB emplace_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL

// constants
const int inf = 1e9;
const ll linf = 1LL << 50;
const double eps = 1e-10;
const int MOD = 1e9 + 7;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};


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

  ll a,b;
  cin >> a >> b;

  if(1 <= a && a <= 9 && 1<=b && b<=9)
    cout << a*b << endl;
  else
    cout << -1 << endl;
}


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

int main() {
  vector<int> a = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
  int k;
  cin >> k;
  cout << a[k - 1] << "\n";
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int s;
  cin >> s;
  int a = (s / 100);
  int b = (s - a*100) / 10;
  int c = (s - a*100 - b*10);
    cout << a+b+c << endl;
}


Measured memory_bytes: 256
#!/usr/bin/env python3

a = []

N = input()
N = int(N)
v = list(map(int, input().split()))
c = list(map(int, input().split()))

sum = 0
for i in range(N):
    if(v[i] - c[i] > 0):
        sum += v[i] - c[i]

print(sum)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
//#include <mylib.h>
using namespace std;
//cin.sync_with_stdio(false);

#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define FOR_EQ(i,a,b) for(int i = (a); i <= (b); ++i)
#define FOR_RE(i,a,b) for(int i = (a); i > (b); --i)
#define rep(i,n) FOR(i,0,n)
#define rep_eq(i,n) FOR_EQ(i,0,n)
#define rep_re(i,n) FOR_RE(i,n,0)

#define DEBUG_VARIABLE(variable) cout << #variable << ":" << variable << endl

#define WHITE 1//（未訪問）
#define GRAY 2//（訪問）未だに訪問していない頂点への辺を持っている。スタックに退避。
#define BLACK 3//（訪問完了）未訪問への頂点への辺を持たない
#define N 100
#define INFTY (1 << 21) //10^21
#define INF (1 << 9)
int M[N][N];//隣接行列
int color[N];

//1個上から時計周り
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
//上右下左
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {-1, 0, 1, 0};
static const int NIL = -1;

typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> Vector;
typedef vector<Vector>	DVector;
ll n;

void printArray(int *array, int);
void printVector(Vector &v);
void printDimention(DVector &dv);

int main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int k;
    cin >> n >> k;
    
    ll res = 0;
    if(k == 0){
        res = n * n;
        cout << res << endl;
        return 0;
    }
    
    ll div;
    ll rem, loop;
    FOR_EQ(i, 1, n){    //b
        div = n / i;
        //if(div % i) div++;
        loop = i - k;
        if(loop > 0){
            rem = n % i - k + 1;
            if(rem < 0) rem = 0;
            res += loop * div + rem;
            //cout << "bが " << i << "の時，" << loop * div + rem << endl;
        }
    }
    cout << res << endl;
}

//配列の表示
void printArray(int array[], int n){
    rep(i, n){
        if(i)   cout << " ";
        cout << array[i];
    }
    cout << endl;
}

//Vectorの表示
void printVector(Vector &v){
    rep(i, (int)v.size()){
        if(i)   cout << " ";
        cout << v[i];
    }
    cout << endl;
}

//二次元配列の表示
void printDimention(DVector &dv){
    rep(i, (int)dv.size()){
        rep(j, (int)dv[i].size()){
            if(j)   cout << " ";
            cout << dv[i][j];
        }
        cout << endl;
    }
}

//numの中に何個2がかかってるか
int factor2(int num){
    int cnt = 0;
    while(num % 2 == 0){
        num /= 2;
        cnt++;
    }
    return cnt;
}

Measured memory_bytes: 256