akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

int tab[100000 + 5];
int tab1[100000 + 5];
int odp;
int main()
{
    int n;
    cin>>n;

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


    for(int i = 0; i < n; i++)
    {

     if(tab[i] <= 100000)
     {

         tab1[tab[i]]++;

     }
     else
     odp++;

    }
    for(int i = 0; i < 100000 + 1; i++)
    {

        if(tab1[i] > i) odp += (tab1[i]-i);
        if(tab1[i] < i) odp += tab1[i];

    }
    cout<<odp;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define pfc(x) printf("Case %d: ",x)
#define sf1(x) scanf("%lld",&x)
#define sf2(x,y) scanf("%d%d",&x,&y)
#define sf3(x,y,z) scanf("%lld%lld%lld",&x,&y,&z)
#define sf4(x,y,z,m) scanf("%d%d%d%d",&x,&y,&z,&m)
#define pf1(x) printf("%d\n",x)
#define pf2(x,y) printf("%d %d\n",x,y)
#define pf3(x,y,z) printf("%d %d %d\n",x,y,z)
#define pf4(x,y,z,m) printf("%d %d %d %d\n",x,y,z,m)
#define pii pair<long long,long long>
#define pb push_back
int n,flag;
struct lol
{
    char ch;
    long long num;
} a[1000005];
int part(int p,int r)
{
    long long x=a[r].num;
    long long i=p-1;
    for(int j=p; j<r; j++)
    {
        if(a[j].num<=x)
        {
            i++;
            swap(a[i].num,a[j].num);
            char tp;
            tp=a[i].ch;
            a[i].ch=a[j].ch;
            a[j].ch=tp;

        }
    }
    swap(a[i+1].num,a[r].num);
    char tp;
    tp=a[i+1].ch;
    a[i+1].ch=a[r].ch;
    a[r].ch=tp;
    return i+1;
}
void quick(int p,int r)
{
    int q;
    if(p>=r)return ;
    if(p<r)q=part(p,r);
    quick(p,q-1);
    quick(q+1,r);
}
int main()
{
    int n;
    cin>>n;
    flag=0;
    map<long long,vector<char> >mp,rp;
    map<int,int>rr;
    vector<int>v;
    for(int i=0; i<n; i++)
    {
        cin>>a[i].ch>>a[i].num;
        mp[a[i].num].pb(a[i].ch);
        if(rr[a[i].num]==0)v.pb(a[i].num);
        rr[a[i].num]=1;

    }
    quick(0,n-1);
    flag=0;
    for(int i=0; i<n; i++)
    {
        rp[a[i].num].pb(a[i].ch);
    }
    for(int i=0;i<v.size();i++)
    {
        for(int j=0;j<mp[v[i]].size();j++)
        {
            //cout<<mp[v[i]][j]<<' '<<rp[a[i].num][j]<<endl;
            if(mp[v[i]][j]!=rp[v[i]][j])flag=1;
        }
    }

    if(flag==0)printf("Stable\n");
    else
    {
        printf("Not stable\n");
    }
    for(int i=0; i<n; i++)printf("%c %lld\n",a[i].ch,a[i].num);
    return 0;
}

Measured memory_bytes: 11372
#include<iostream>
int box[10];
int ltop = -1, rtop = -1;
bool ball(int i, int left, int right){
	if (i == 10)return true;
	if (left<box[i])return ball(i + 1, box[i], right);
	if (right<box[i])return ball(i + 1, left, box[i]);
	if (left>box[i] && right>box[i])return false;
}
int main(){
	int n;
	std::cin >> n;
	for (int what = 0; what<n; ++what){
		for (int i = 0; i<10; ++i){
			std::cin >> box[i];
		}
		if (ball(0, ltop, rtop))std::cout << "YES\n";
		else std::cout << "NO\n";
		ltop = -1;
		rtop = -1;
	}
}

Measured memory_bytes: 3008
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using Graph = vector<vector<ll>>;
using P = pair<int,int>;
#define MOD 1000000007
#define INF 1000000

int nCr(int n, int r)
{
  int top = 1;
  int bot = 1;
  while (r>0)
  {
    top *= n;
    bot *= r;
    r--,n--;
  }
  return (top/bot);
}

int main()
{
  int N;cin>>N;
  vector<int> x(N+1),y(N+1);
  for (int i=1;i<=N;i++)
  {
    cin>>x[i]>>y[i]; 
  }
  
  //num = N!*(N-1)*nC2
  double num =1;
  int n = N;
  while (n>0)
  {
    num *= n;
    n--;
  }
  num *= N-1;
  //cout<<num<<endl;
  num /= nCr(N,2);
  //cout<<num<<endl;
  
  double sum = 0;
  for (int i=1;i<=N-1;i++)
  {
    for (int j=i+1;j<=N;j++)
    {
      double len = pow(x[i]-x[j],2)+pow(y[i]-y[j],2); 
      len = sqrt(len);
      sum += len * (num);
    }
  }
  double bot = 1;
  while (N>0)
  {
    bot *= N;
    N--;
  }
  sum /= bot;
  cout << fixed <<setprecision(10);
  cout<<sum<<endl;
}

Measured memory_bytes: 256
import java.util.*;
public class Main{
    public static void main(String[] args)throws Exception{
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        if(n < 1000) {
            System.out.println("ABC");

        }else{
            System.out.println("ABD");
        }
    }
}

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

using ll=long long;

int main(){

int N;
cin>>N;

vector<int> A(N),B(N+1),C(N);

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

for(int i=1;i<=N;++i){
cin>>B[i];
}

for(int i=1;i<=N-1;++i){
cin>>C[i];
}

int S=0;

for(int i=0;i<N;++i){
S+=B[A[i]];
if(i<N-1 && A[i]+1==A[i+1]){S+=C[A[i]];}
}

cout<<S<<endl;

}

Measured memory_bytes: 256
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF 0x3f3f3f3f

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

const int maxn = 20;
int n,m,x,c[maxn],a[maxn][maxn],memo[maxn];
signed main() {
  IO;
  cin >> n >> m >> x;
  rep(i,0,n - 1){
    cin >> c[i];
    rep(j,0,m - 1) cin >> a[i][j];
  }
  int ans = INF;
  for(int i = 0 ; i < (1 << n) ; i++){
    mset(memo,0);int res = 0;
    for(int j = 0; j < n ; j++) if((i >> j) & 1){
      res += c[j];
      for(int k = 0 ; k < m ; k++) memo[k] += a[j][k];
    }
    bool v = true;
    for(int j = 0 ; j < m ; j++) if(memo[j] < x) v = false;
    if(v) ans = min(ans,res);
  }
  if(ans == INF) cout << -1 << '\n';
  else cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 3648
#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>;
#define chmax(x,y) x = max(x,y);
#define chmin(x,y) x = min(x,y);
const int di[] = {-1, 0, 1, 0};
const int dj[] = {0, -1, 0, 1};
const int INF = 1001001001;



int main() {
    int h, w;
    cin >> h >> w;
    vector<string> s(h);
    rep(i,h) cin >> s[i];
    int ans = 0;
    rep(si,h)rep(sj,w) {
        if (s[si][sj] == '#') continue;
        vector<vector<int>> dist(h, vector<int>(w, INF));
        queue<P> q;
        auto update = [&](int i, int j, int x) {
            if (dist[i][j] != INF) return;
            dist[i][j] = x;
            q.emplace(i,j);
        };
        update(si,sj,0);
        while (!q.empty()) {
            int i = q.front().first, j = q.front().second;
            q.pop();
            int d = dist[i][j];
            rep(dir,4) {
                int ni = i+di[dir], nj = j+dj[dir];
                if (ni<0||ni>=h||nj<0||nj>=w) continue;
                if (s[ni][nj] == '#') continue;
                update(ni,nj,d+1);
            }
        }
        rep(i,h)rep(j,w) {
            if (dist[i][j] == INF) continue;
            ans = max(ans, dist[i][j]);
        }
    }
    cout << ans << endl;
    return 0;
}

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

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

    int h[N + 1];
    int e[N + 1];
    for(int i = 1; i < N + 1; i++){
        int a; cin >> a;
        h[i] = a;
        e[i] = 1;
    }


    int a, b;
    for(int i = 0; i < M; i++){
        cin >> a >> b;
        if(h[a] > h[b]) e[b] = 0;
        else e[a] = 0;
        if(h[a] == h[b]) e[a] = 0, e[b] = 0;
    }

    int ans = 0;
    for(int i = 1; i < N + 1; i++){
        if(e[i] == 1) ans++;
    }
    cout << ans;
}

Measured memory_bytes: 4396
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3")
#define REP(i,n) for(int i=0;i<n;i++)
#define REPP(i,n) for(int i=1;i<=n;i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define EPS (1e-9)
#define INF (1e17)
#define PI (acos(-1))
//const double PI = acos(-1);
//const double EPS = 1e-15;
//long long INF=(long long)1E17;
#define i_7 (long long)(1e9+7)
//#define i_7 998'244'353
long mod(long a){
    long long c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
long long po(long a, long b){
    if(b==0){
        return 1;
    }
    
    long long z = po(a,b/2);
    z = mod(z*z);
    if(b%2!=0){
        z = mod(a*z);
    }
    return z;
}
 
bool prime_(int n){
  if(n==1){
    return false;
  }else if(n==2){
    return true;
  }else{
    for(int i=2;i<=std::sqrt(n);i++){
      if(n%i==0){
        return false;
      }
    }
    return true;
  }
}
 
long long gcd_(long long a, long long b){
  if(a<b){
    std::swap(a,b);
  }
  if(a%b==0){
    return b;
  }else{
    return gcd_(b,a%b);
  }
}
 
long long lcm_(long long x, long long y){
  return (x/gcd_(x,y))*y;
}
 
//using namespace std;
//using namespace boost::multiprecision;
//using namespace __gnu_pbds;
 
int main(){
  using namespace std;
  int a, b;
  cin>>a>>b;
  REPP(i, 10000){
    if((i * 8) / 100 != a){
      continue;
    }
    if((i * 10) / 100 != b){
      continue;
    }
    cout<<i<<endl;
    return 0;
  }
  cout<<-1<<endl;
  return 0;
}


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

using ll=long long;
using int64=int64_t;
const int inf=100000000;

int in(){
  int a;
  cin >> a;
  return a;
}//int型関数の受け取り

void forin(int* x,int y){
  for (int i=0;i<y;i++){
    cin >> x[i];
  }
}//(x,y) int型配列x[y]の受け取り

int intpow(int x,int y){
  double a=x,b=y;
  return pow(a,b);
}//(x,y) xをy乗

int intfabs(int x){
  double a=x;
  return fabs(a);
}//(x) xの絶対値

int fact(int x){
  if (x == 1) return 1;
  return x*fact(x-1);
}//(x) x!

int fib(int x){
  if (x <= 2) return x;
  int a[x];
  a[0]=1;
  a[1]=2;
  for (int i=2;i<x;i++){
    a[i]=a[i-1]+a[i-2];
  }
  return a[x-1];
}//(x) フィボナッチ数列のx番目

int div1(ll x){
  return x%1000000007;
}

main(){
    int n=in(),h[n],c[n];
    forin(h,n);
    c[0]=0;
    c[1]=intfabs(h[0]-h[1]);
    for(int i=2;i<n;i++){
        c[i]=min(c[i-1]+intfabs(h[i-1]-h[i]),c[i-2]+intfabs(h[i-2]-h[i]));
    }
    cout << c[n-1] << endl;
}

Measured memory_bytes: 1024
import java.util.Scanner;
    
    class Main {
     
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int N = sc.nextInt();
            boolean[] n = new boolean[N+1];
            boolean isEnd = false;
            for(int i = 1; i <=N; i++) {
            	n[i] = false;
            }
            int[] a = new int[N+1];
            for(int i = 1; i <= N; i++) {
            	a[i] = sc.nextInt();
            }
            sc.close();
            
            int count = 0;
            int i = 1;
            
            while(true) {
            	if( n[i] == false ) {
            		n[i] = true;
            		count ++;
            		if( a[i] == 2 ) {
            			break;
            		}
            		i = a[i];
     			}else {
     				count = -1;
     				break;
             	}
            }
	         System.out.println(count);
;        }
    }

Measured memory_bytes: 50420
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 1e9 + 7;
const int inf = (1 << 30) - 1;
const ll infll = (1LL << 61) - 1;
#define fast() ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define digit(N) cout << fixed << setprecision((N))

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

int main()
{
    while (cin >> H >> W)
    {
        if (H == 0 && W == 0)
            return 0;
        vector<string> grid(W);

        pair<int, int> s;
        for (int i = 0; i < W; i++)
        {
            cin >> grid[i];
            for (int j = 0; j < H; j++)
            {
                if (grid[i][j] == '@')
                    s = {i, j};
            }
        }

        queue<pair<int, int>> que;
        que.push(s);

        vector<vector<int>> visited(W, vector<int>(H));

        visited[s.first][s.second] = 1;

        while (!que.empty())
        {
            auto p = que.front();
            que.pop();

            visited[p.first][p.second] = 1;
            for (int i = 0; i < 4; i++)
            {
                int nx = p.first + dx[i], ny = p.second + dy[i];
                if (nx < 0 || nx >= W)
                    continue;
                if (ny < 0 || ny >= H)
                    continue;
                if (visited[nx][ny])
                    continue;
                if (grid[nx][ny] == '.')
                    que.push({nx, ny});
            }
        }

        int ans = 0;

        for (int i = 0; i < W; i++)
        {
            for (int j = 0; j < H; j++)
            {
                ans += visited[i][j];
            }
        }

        cout << ans << endl;
    }
}


Measured memory_bytes: 6076
#include<bits/stdc++.h>
#define reg register
typedef long long ll;
using namespace std;
const int MN=55;
const int MM=15;
int n,m,q,Ans,A[MN],B[MN],C[MN],D[MN],a[MN];
void dfs(int st,int pre){
	if(st==n+1){
		reg int Res=0;
		for(reg int i=1;i<=q;i++)
			if(a[B[i]]-a[A[i]]==C[i])Res+=D[i];
		Ans=max(Ans,Res);return;
	}
	for(reg int i=pre;i<=m;i++)
		a[st]=i,dfs(st+1,i);
}
int main(){
	scanf("%d%d%d",&n,&m,&q);
	for(reg int i=1;i<=q;i++)
		scanf("%d%d%d%d",A+i,B+i,C+i,D+i);
	dfs(1,1);printf("%d\n",Ans);
	return 0;
}

Measured memory_bytes: 3812
#include <stdio.h>
#include <iostream>
#include <iomanip>
#include <limits>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
#include <map>
#include <tuple>

#define INF 100100100100
#define rep(i,n) for(int i=0; i<(n); i++)
typedef long long ll;
using namespace std;

 
int main(){
    int n; cin >> n;
    if(n >= 2500){
        cout << 1 << endl;
        return 0;
    }
    int x2 = n/100;
    
    int x = n%100;
    const int V[5] = {1, 2, 3, 4, 5};
    
    for(int i=4; i>=0; i--){
        if(x2 == 0){
            cout << 0 << endl;
            return 0;
        }
        int t = min(x/V[i], x2);
        x -= t*V[i];
        x2 -= t;
        if(x == 0){
            cout << 1 << endl;
            return 0;
        }
        if(x2 < 0){
            cout << 0 << endl;
            return 0;
        }
        
    }
    
    
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long  
#define pb push_back
#define mk make_pair
#define mod 1000000007
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
#define all(x) x.begin(),x.end()

int main()
{
    ios::sync_with_stdio(0) ;
    cin.tie(0); 
    ll x,y;
    cin>>x>>y;
    if(x<y)
    swap(x,y);
    ll ans=1;
    ll a=x-y;
    y-=(x-y);
    if(y<0||y%3!=0)
    {
        cout<<0<<endl;
    }
    else
    {
        int b=y/3;int yy=mod;yy--;yy--;
        a+=b;
        int n=a+b;
        int bit[31]={0};
        for(int i=0;i<=30;i++)
        {
            if((1<<i)&yy)
            bit[i]=1;

        }
        for(int i=2;i<=n;i++)
        {
            ans*=i;ans%=mod;
        }
        for(int i=1;i<=a;i++)
        {
            ll y=i;
            for(int j=0;j<=30;j++)
            {
               
                if(bit[j]==1)
                {
                    ans*=y;
                    ans%=mod;
                }
                y*=y;y%=mod;
            }
        }
        for(int i=1;i<=b;i++)
        {
            ll y=i;
            for(int j=0;j<=30;j++)
            {
               
                if(bit[j]==1)
                {
                    ans*=y;
                    ans%=mod;
                }
                y*=y;y%=mod;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}
//make all values ll


Measured memory_bytes: 256
n,m  = list(map(int, input().split()))
p, s = [None for _ in range(m)],[None for _ in range(m)]
for i in range(m):
    p[i], s[i] = input().split()
p = list(map(int, p))

correct = [0 for _ in range(n)]
penal = [0 for _ in range(n)]

for i in range(m):
    if s[i] == 'AC':
        correct[p[i]-1] = 1
    else:
        if correct[p[i]-1] != 1:
            penal[p[i]-1] += 1

for i, cor in enumerate(correct):
    if cor == 0:
        penal[i] = 0


c = sum(correct)
pen = sum(penal)
print(c, pen)

Measured memory_bytes: 68352
function Main(input) {
    input = input.split(" ");
    var A = parseInt(input[0],10);
    var B = parseInt(input[1],10);
    var C = parseInt(input[2],10);
    if(B + C - A > 0){
        console.log(B + C - A);
    }else{
        console.log(0);
    }
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 7372
n, q = map(int, input().split())
s = input()
x = [0]*(n+1)

for i in range(n):
    x[i+1] = x[i] + (1 if s[i:i+2] == "AC" else 0)

for i in range(q):
    l, r = map(int, input().split())
    print(x[r-1] - x[l-1])

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

int main() {
	vector<int> vec; int an, tn, fn1, fn2, fn3; int set = 0;
	cin >> an; vec.resize(an);
	for (int i = 0; i < an; i++) cin >> vec[i];
	cin >> tn;
	for (int i = 0; i < tn; i++) {
		cin >> fn1 >> fn2 >> fn3;
		swap_ranges(vec.begin() + fn1, vec.begin() + fn2, vec.begin() + fn3);
	}
	for (int i : vec)cout << (set++ ? " " : "") << i;
	cout << endl;
	return 0;
}


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

int main()
{
  int N;
  cin >> N;
  
  string S;
  bool Y = false;
  
  for(int i = 0; i < N; i++)
  {
    cin >> S;
    if(S == "Y")
    {
      cout << "Four" << endl;
      Y = true;
      break;
    }
  }
  if(!Y){cout << "Three" << endl;}
}

Measured memory_bytes: 256
#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <functional>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <bitset>

using namespace std;
using ll = long long;

const int MOD = 1e9 + 7;
const int N = 1 << 20;
int dp[N][2];
int t[N];

ll binpow(ll a, int p) {
    ll res = 1;
    while (p) {
        if (p & 1) {
            (res *= a) %= MOD;
        }
        (a *= a) %= MOD;
        p >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    int x = 0;
    for (int i = 0; i < N; i++) {
        dp[i][0] = 1;
    }
    int kek = 0;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        x ^= a;
        if (x == 0) {
            kek++;
        } else {
            if (kek > t[x]) {
                dp[x][0] = (dp[x][0] + 1LL * dp[x][1] * (kek - t[x])) % MOD;
                t[x] = kek;
            }
            dp[x][1] = (dp[x][0] + dp[x][1]) % MOD;
        }
    }
    if (x) {
        cout << dp[x][0] << endl;
    } else {
        int ans = 0;
        for (int i = 1; i < N; i++) {
            ans = (ans + dp[i][1]) % MOD;
        }
        cout << (ans + binpow(2, kek - 1)) % MOD << endl;
    }
    return 0;
}

Measured memory_bytes: 12544
#include <iostream>
#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
	return x*f;
}
int main(){
	//freopen("aa.in","r",stdin);
	//freopen("aa.out","w",stdout);
	int A=read(),B=read(),C=read();

	if(A%2==0&&A==B&&B==C){
		printf("-1\n");
		return 0;
	}
	int t=0;
	while(A%2==0&&B%2==0&&C%2==0){
		int a=A>>1,b=B>>1,c=C>>1;
		A=b+c,B=a+c,C=a+b;
		t++;
	}
	printf("%d\n",t);
	fclose(stdin);fclose(stdout);
	return 0;
}


Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main
{
    public static void main(String[] args)
    {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskC solver = new TaskC();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskC
    {
        public void solve(int testNumber, Scanner in, PrintWriter out)
        {
            int T = 1;
            while (T-- > 0)
            {
                solveOne(in, out);
            }
        }

        private void solveOne(Scanner in, PrintWriter out)
        {
            long MOD = 1_000_000_000 + 7;
            long N = in.nextInt();

            if (N == 1 || N == 2)
            {
                out.println(N == 1 ? 0 : 2);
                return;
            }

            long ans = CPUtils.modPower(10L, N, MOD);

            ans -= 2L * CPUtils.modPower(9L, N, MOD);
            ans += CPUtils.modPower(8L, N, MOD);

            ans %= MOD;
            if (ans < 0)
                ans += MOD;

            out.println(ans);
        }

    }

    static class CPUtils
    {
        public static long modPower(long base, long p, long m)
        {
            long ret = 1;
            for (; p > 0; p >>= 1, base = base * base % m)
            {
                if (p % 2 == 1)
                {
                    ret = ret * base % m;
                }
            }
            return ret;
        }

    }
}



Measured memory_bytes: 27116
#pragma region header
#include <bits/stdc++.h>
using namespace std;
#define int long long
#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 rev(i, n) for(int i = (int)(n - 1); i >= 0; i--)
#define rev1(i, n) for(int i = (int)(n); i > 0; i--)
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define resort(v) sort((v).rbegin(), (v).rend())
#define vi vector<int>
#define vvi vector<vector<int>>
#define vc vector<char>
#define vvc vector<vector<char>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
using ll = long long;
using P = pair<int, int>;
/* ----------------よく使う数字や配列----------------- */
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
constexpr ll mod = 1e9+7;
constexpr ll inf = INT32_MAX/2;
constexpr ll INF = LLONG_MAX/2;
constexpr long double eps = DBL_EPSILON;
constexpr long double pi = 3.141592653589793238462643383279;
/* ----------------------end----------------------- */

/* --------------------テンプレート------------------ */
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
/* ----------------------end----------------------- */

/* --------------------ライブラリ-------------------- */
ll fact(int i) {       //階乗
    if (i == 0) return 1;
    return (fact(i - 1)) * i % mod;
}
ll gcd(ll a, ll b) {        //最大公約数
    if(b == 0) return a;
    return gcd(b, a % b); 
}
ll lcm(ll a, ll b) {      //最小公倍数
    return a / gcd(a, b) * b ;
}
int keta(ll n) {        //桁数を求める
    if(n == 0) return 1;
    int count = 0;
    while(n != 0) {
        n /= 10;
        count++;
    }
    return count;
}
ll ketasum(ll n) {    //各桁の和
    ll sum = 0;
    while(n != 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}
bool isprime(int n) { //素数判定
    if(n==1)return false;
    if(n==2)return true;
    for(int i = 2;i<=sqrt(n);i++) {
        if(n%i==0) return false;
    }
    return true;
}
/* ----------------------end----------------------- */
#pragma endregion
struct UnionFind {
    vector<int> par, size;
    UnionFind(int x) {
        par.resize(x);
        size.resize(x, 1);
        for(int i = 0; i < x; i++) {
            par[i] = i;
        }
    }
    int find(int x) {
        if (par[x] == x)
            return x;
        return par[x] = find(par[x]);
    }
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    int consize(int x) {
        return size[find(x)];
    }
    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y)
            return;
        if (size[x] < size[y]) {
            par[x] = y;
            size[y] += size[x];
        }
         else {
            par[y] = x;
            size[x] += size[y];
        }
    }
};
signed main() {
    int n,m;cin >> n >> m;
    UnionFind uf(n);
    rep(i, m) {
        int a,b,c;cin >> a >> b >> c;
        uf.unite(--a,--b);
    }
    set<int> st;
    rep(i, n) st.insert(uf.find(i));
    cout << st.size() << endl;
    return 0;
}

Measured memory_bytes: 9632
import java.util.*;
public class Main {
	
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
         long X = sc.nextLong();
         long A = sc.nextLong();
         long B = sc.nextLong();
         
         if (B - A > X) {
        	 System.out.println("dangerous");
         } else if (0 < B - A &&  B - A <= X ) {
        	 System.out.println("safe");
         } else {
        	 System.out.println("delicious");
         }
    }
}

Measured memory_bytes: 21844
#include <bits/stdc++.h>
#include <math.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rrep(i, n) for(int i = 0; i <= (n); i++)
using namespace std;
typedef long long ll;
const int MOD = 1000000007;
const ll INF = 1LL<<60;
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; }
using Graph = vector<vector<int>>;

typedef pair<int, int> P;


int main(){
    int N, M; cin >> N >> M;
    vector<pair<int,int>> AB;
    vector<vector<int>> jobs(M); 
    rep(i,N){
        int a, b; cin >> a >> b;
        if (M < a) continue;
        jobs[M-a].push_back(b);
    }
    // 実行可能なジョブを格納するキュー
    priority_queue<int> que;
    ll ans = 0;
    for (int i = M-1; i >= 0; i--){
        // i日目で実行可能なジョブを追加
        for (int job : jobs[i]) que.push(job);        
        
        if (!que.empty()){
            ans += que.top(); que.pop();
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 5504
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc =new Scanner(System.in);
    int N =sc.nextInt();
    String M[] =new String[N];
    for(int i=0;i<N;i++){
      M[i]=sc.next();}
    Arrays.sort(M);
    int x =1;
    for(int j=1;j<N;j++){
      if(M[j].equals(M[j-1])){continue;}
      else{x=x+1;}}
    System.out.println(x);
  }
}

Measured memory_bytes: 70172
#include <stdio.h>
int main(void) {
	int a, b;
	scanf("%d%d", &a, &b);
	double c;
	int d,e;
	c = (double)a / (double)b;
	e = a / b;
	d = a % b;
	printf("%d %d %.7f", e, d,c);
	return 0;
}

Measured memory_bytes: 640
#include<iostream>
#include<vector>
#include<algorithm>
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
ll cost[100005][3];
ll dp[100005][3];
ll n,maxc=0;
ll fun(ll i, ll j)
{
    if(i==n)
     return 0;
    if(dp[i][j]!=-1)
       return dp[i][j];
    else
    {
        return dp[i][j]=max(fun(i+1,(j+1)%3),fun(i+1,(j+2)%3) )+ cost[i][j];
    }
    
    
}


int main()
{
    
    memset(dp,-1,sizeof(dp));
    cin>>n;
    
    for(ll i=0;i<n;i++)    
      cin>>cost[i][0]>>cost[i][1]>>cost[i][2];
      
    maxc=max(fun(0,0),fun(0,1));
    
    maxc= max(fun(0,2),maxc); 
    
    cout<<maxc<<"\n"; 
    
    return 0;
}

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

int main(){
  long long int N ,ans = 0 ;
  string S ;
  cin >> N >> S;
  for(long long int i = 0; i < S.size(); i++){
    if(char(S[i] + N) <= 'Z') cout << char(S[i] + N) ;
    else cout << char(S[i] + N - 26);
  }
}


Measured memory_bytes: 3656
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

A, B, C = mi()
N = ii()

cnt = 0

while A >= B:
    B *= 2
    cnt += 1

while B >= C:
    C *= 2
    cnt += 1

if cnt <= N:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 9176
#include <iostream>
#include <ctype.h>
#include <string>
using namespace std;
string toUpper( string s ){
	string t = s;
	for(int i = 0; i<s.size(); i++){
		t[i]=toupper(s[i]);
	}
	return t;
}

int main(){
	string target,source;
	cin>>target;
	target = toUpper(target);
	int count = 0;
	while(1){
		cin >> source;
		if(source == "END_OF_TEXT")break;
		source = toUpper(source);
		if(target == source){
			count++;
		}
	}
	cout << count << endl;
	return 0;
}


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

int main(void){
	int n;
	while(cin>>n,n){
		int t[n];
		for(int i=0;i<n;i++){
			cin>>t[i];
		}
		if(n == 1){
			cout<<0<<endl;
			continue;
		}
		int ans = 0;
		for(int i=0;i<n;i++){
			for(int j=0;j<n-1;j++){
				if(t[j] > t[j+1]){
					ans++;
					swap(t[j],t[j+1]);
				}
			}
		}
		cout<<ans<<endl;
	}

	return 0;
}

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

typedef long long ll;

ll N,X;
ll siz[100];
ll cnt[100];

int main()
{
    scanf("%lld%lld",&N,&X);

    siz[0] = 1;
    for(int i = 1; i <= 50; i++)
    {
        siz[i] = siz[i - 1] * 2 + 3;
    }
    cnt[0] = 1;
    for(int i = 1; i <= 50; i++)
    {
        cnt[i] = cnt[i - 1] * 2 + 1;
    }

    ll ans = 0;
    for(int i = N; i >= 1; i--)
    {
        if(siz[i] == X)X--;
        if(X == 0)continue;
        if((siz[i] - 1) / 2 == X)
        {
            ans += cnt[i - 1];
            X = 0;
        }
        else if((siz[i] - 1) / 2 > X)
        {
            X--;
        }
        else
        {
            ans += cnt[i - 1] + 1;
            X -= siz[i - 1] + 2;
        }
    }
    if(X)ans++;

    printf("%lld\n",ans);
    return 0;
}


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

#define int long long

#define ii pair<int,int>
#define fi first
#define sc second
#define lwb lower_bound
#define upb upper_bound
#define all(x) (x).begin(),(x).end()

#define sqr(x) ((x)*(x))

signed main() {
#ifdef _DEBUG
  // freopen("in", "r", stdin);
#endif
  ios::sync_with_stdio(0); cin.tie(0);
  int n; cin >> n;
  vector<int> a(n);
  int avr = 0;
  for (auto &i : a) cin >> i, avr += i;
  avr /= n;
  int lans = 0, rans = 0;
  for (auto &i : a) {
    lans += sqr(abs(i - avr));
    rans += sqr(abs(i - avr - 1));
  }
  cout << min(lans, rans) << '\n';
}


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

int n1,n2;
int main(){
	cin>>n1;
	n2=n1;
	
	while(n1>=0){
		if(n1%4==0){
			cout<<"Yes"<<endl;
			return 0;
		}
		n1-=7;
	}
	
	while(n2>=0){
		if(n2%7==0){
			cout<<"Yes"<<endl;
			return 0;
		}
		n2-=4;
	}
	cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 256
while True:
    Lists=input().split()
    if Lists[1]=="/":
        print(int(int(Lists[0])/int(Lists[2])))
    elif Lists[1]=="-":
        print(int(int(Lists[0])-int(Lists[2])))
    elif Lists[1]=="+":
        print(int(int(Lists[0])+int(Lists[2])))
    elif Lists[1]=="*":
        print(int(int(Lists[0])*int(Lists[2])))
    elif Lists[1]=="?":
        break
    else:
        break





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

int main() {
    int n, x;
    while(cin >> n >> x){
        int count=0;
        if(n==0 && x==0) break;
        for(int i=1; i<=n-2; i++){
            for(int j=i+1; j<=n-1; j++){
                for(int k=j+1; k<=n; k++){
                    if(x==i+j+k){
                        count++;
                    }
                }
            }
        }
        cout << count << endl;
    }
    return 0;
}

Measured memory_bytes: 1164
# Author: S Mahesh Raju
# Username: maheshraju2020
# Date: 03/08/2020

from sys import stdin, stdout, setrecursionlimit
from math import gcd, ceil, sqrt
from collections import Counter
from bisect import bisect_left, bisect_right
ii1 = lambda: int(stdin.readline().strip())
is1 = lambda: stdin.readline().strip()
iia = lambda: list(map(int, stdin.readline().strip().split()))
isa = lambda: stdin.readline().strip().split()
setrecursionlimit(100000)
mod = 1000000007

k = ii1()
t = 0
for i in range(1, k + 1):
    t = (t % k) * 10 + 7
    if t % k == 0:
        print(i)
        break
else:
    print(-1)

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

using namespace std;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define itn int
typedef long long ll;
typedef pair<ll,ll> p;
ll digitSum(int n)
{
  int tmp = log10(n);
  ll res = 0;
  for (int i = tmp; i > 0; i--)
  {
    res += n / (pow(10, i));
    n -= ((n / int((pow(10, i)))) * pow(10, i));
  }
  res += n;
  return res;
}

int main()
{
  ll a;
  cin >> a;
  ll b = digitSum(a);
  if (a % b == 0)
  {
    cout << "Yes" << endl;
  }
  else
  {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 512
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int w = scan.nextInt();
		int h = scan.nextInt();
		int x = scan.nextInt();
		int y = scan.nextInt();
		int r = scan.nextInt();
		System.out.println(x >= r && x <= w - r && y >= r && y <= h - r ? "Yes" : "No");
		scan.close();
	}

}


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

const double PI = acos(-1.0);

double rad_to_deg(double x){
	return x/PI * 180.0;
}

int a,b,x;

int main(){
	scanf("%d%d%d",&a,&b,&x);
	int total = a*a*b;
	if(2*x >= total){
		int sisa = total - x;
		double tmp = (double)sisa/(double)(a*a) * 2.0;
//		cout << tmp << endl;
		
		printf("%.9lf\n",rad_to_deg(atan(tmp/(double)a)));
	} else {
		double tmp = (double)(x)/(double)(a*b) * 2.0;
//		cout << tmp << endl;
		printf("%.9lf\n",rad_to_deg(atan((double)b/tmp)));
	}
	return 0;
}

Measured memory_bytes: 256
// Package main provides
//
// File:  b.go
// Author: ymiyamoto
//
// Created on Sat Dec  8 18:47:44 2018
//
package main

import "fmt"

func main() {
	var S string
	fmt.Scan(&S)

	if S[0] != 'A' {
		fmt.Println("WA")
		return
	}

	c := 0
	for i := 2; i < len(S)-1; i++ {
		if S[i] == 'C' {
			c = i
		}
	}

	if c == 0 {
		fmt.Println("WA")
		return
	}

	for i := 0; i < len(S); i++ {
		if i != 0 && i != c {
			if !('a' <= S[i] && S[i] <= 'z') {
				fmt.Println("WA")
				return
			}
		}
	}

	fmt.Println("AC")
}


Measured memory_bytes: 512
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <queue>
using namespace std;

#define next '\n'
#define sp " "
#define print(x) cout << (x)
#define println(x) cout << (x) << next
#define stop return(0)
#define rep(i, n) for(int (i) = (0); (i) < (n); (++i))
#define FOR(i, start, end) for(int (i) = (start); (i) < (end); (++i))
#define foreach(e, elem) for(auto& (e) : (elem))
#define FAST ios::sync_with_stdio(false); cin.tie(nullptr)
#define size(s) (s).size()
#define all(vec) (vec).begin(), (vec).end()
#define pb(e) push_back(e);
using ll = long long;
using ull = unsigned long long;

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

    int ak = min(a + k - 1, b),
        bk = max(b - k + 1, a + k);

    for(int i = a; i <= ak; ++i){
        println(i);
    }

    for(int i = bk; i <= b; ++i){
        println(i);
    }
}

Measured memory_bytes: 256
# coding:utf-8

import sys
# from collections import Counter, defaultdict

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


n = II()
d, x = LI()
A = [II() for _ in range(n)]

ans = x + n
for a in A:
    ans += (d - 1) // a
print(ans)


Measured memory_bytes: 3316
#include <stdio.h>

int main()
{

  int i,j,count = 0,N,A[100],minj,swap,flag;

  scanf("%d",&N);
  for(i  = 0 ; i < N ; i++)scanf("%d",&A[i]);
  
  for(i = 0 ; i<N ; i++)
    {
      flag = 0;
      minj = i;
      for(j= i ; j <N ; j++)
	{
	  if( A[j] < A[minj] )
	    {
	      minj = j;
	      flag = 1;
	    }
	}
      if(flag == 1)
	{
	  count++ ;
	  swap = A[i];
	  A[i] = A[minj];
	  A[minj] = swap;
	}
    }

  for(i = 0 ; i < N ; i++)
    {
      if(i == N - 1)
	{
	  printf("%d\n%d\n" , A[i] , count);
	  break;
	}
      printf("%d ",A[i]);
    }

}



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

using namespace std;

int main()
{
	int n, k;
	vector<int> num;
	int tmp;
	int ans = 0;
	
	cin >> n >> k;
	
	for (int i = 0; i < n; i++){
		cin >> tmp;
		num.push_back(tmp);
	}
	
	sort(num.begin(), num.end());
	reverse(num.begin(), num.end());
	
	for (int i = 0; i < k; i++){
		ans += num[i];
	}
	
	cout << ans << "\n";
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<string>
#define rep(i,a,b) for(long long int i=(a);i<(b);i++)
#define se(a) a.begin(),a.end()
#define ll long long int
#define mll map<ll,ll>
#define pll pair<ll, ll>
#define pii pair<int,int>
#define pb push_back
#define mk make_pair
#define F first
#define S second
#define mod 1000000007
#define maxn 100005
#define inf 1e16
#define boost ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
ll solve(string a)
{
	ll x=a.length()-1;
	ll ans=0;
	rep(i,0,a.length())
	if(a[i]=='A')
	{
		ans=ans+(x-i);x--;
	}
	return ans;
}
int main()
{
	string s;
	cin>>s;
	string a;
	for(int i=0;i<s.length();i++)
	{
		if(s[i]=='A')
		a=a+s[i];
		else if(s[i]=='B')
		{
			if(i+1<s.length()&&s[i+1]=='C')
			{
				a=a+'D';
				i++;
			}
			else
			a=a+s[i];
		}
		else
		a=a+s[i];
	}
	ll ans=0;
	for(int i=0;i<a.length();)
	if(a[i]=='A'||a[i]=='D')
	{
		ll j=i+1;
		while(j<a.length()&&(a[j]=='A'||a[j]=='D'))
		j++;
		ans=ans+solve(a.substr(i,j-i));
		i=j;
	}
	else
	i++;
	cout<<ans<<endl;
}

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

int main(){
    int n,x,maximu;
    string text;
    cin >> n;
    cin >> text;

    x = 0;
    maximu = 0;

    for (int i = 0; i < n; i++)
    {
        char s = text[i];
       if (s =='I'){
        x++;
        if (x > maximu)
        {
            maximu = x;
        }
           
       }else {
           x--;
       }   
    }
    cout << maximu << endl;
    

}

Measured memory_bytes: 256
n = int(input())
l_prm = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
l_prm = [i for i in l_prm if i<=n/2]
l_new = []
for i in l_prm:
    a = n
    counter = 0
    b = a
    c=1
    while b!=0:
        b = a//i**c
        counter += b
        c += 1
    l_new.append(counter)
ans=0
def num(j,lst):
    return(len([i for i in lst if i>=j]))
ans += num(4,l_new) * (num(4,l_new)-1)/2 *(num(2,l_new)-2)
ans += num(14,l_new)*(num(4,l_new)-1)
ans += num(24,l_new)*(num(2,l_new)-1)
ans += num(74,l_new)
print(int(ans))

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

int main(void)
{
    string s;

    cin >> s;
    long long int ans = 0;

    for (int bit = 0; bit < (1<<(s.size()-1)); ++bit) 
    {
        long long int tmp = s[0]-'0';
        for(int i = 0; i < (s.size()-1); ++i)
        {
            if (bit & (1 << i)) 
            {
                ans += tmp;
                tmp = 0;
            }
            tmp = tmp*10 + (s[i+1]-'0');
        }
        ans += tmp;        
    }

    cout << ans << endl;


    return 0;
}



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

int main()
{
	int i,N;
	string S;
	int cnt0, cnt1;

	cin >> S;
	N = S.length();
	cnt0 = cnt1 = 0;
	for (i = 0; i < N; i++) {
		if (S[i] == '0') {
			cnt0++;
		}
		else {
			cnt1++;
		}
	}

	cout << min(cnt0, cnt1) * 2 << endl;
	return 0;
}


Measured memory_bytes: 512
import java.util.*;
import java.io.*;
class Main {
    
    static boolean[][] map;
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());
        int sx=Integer.parseInt(st.nextToken())+1000;
        int sy=Integer.parseInt(st.nextToken())+1000;
        int tx=Integer.parseInt(st.nextToken())+1000;
        int ty=Integer.parseInt(st.nextToken())+1000;
        int len1=ty-sy;
        int len2=tx-sx;
        String str="";
        for(int i=0;i<len1;i++){ str+="U"; }
        for(int i=0;i<len2;i++){ str+="R"; }
        for(int i=0;i<len1;i++){ str+="D"; }
        for(int i=0;i<len2;i++){ str+="L"; }
        str+="D";
        len1++;
        len2++;
        for(int i=0;i<len2;i++){ str+="R"; }
        for(int i=0;i<len1;i++){ str+="U"; }
        str+="LU";
        for(int i=0;i<len2;i++){ str+="L"; }
        for(int i=0;i<len1;i++){ str+="D"; }
        str+="R";
        System.out.println(str);
    }
}

Measured memory_bytes: 206024
#include <cstdio>
#include <vector>

using namespace std;

const int NMAX = 2e5;

int n;
int lvl[NMAX + 5];
int mars[NMAX + 5];
int ans[NMAX + 5];

vector<int> graph[NMAX + 5];


vector<int> path_to_root; 
vector<int> max_on_path;
int st[NMAX + 5];
int lin[NMAX + 5];
int fst[NMAX + 5];
int lst[NMAX + 5];
int len;

void predfs(int nod,int tata){
	lin[++len] = nod;
	fst[nod] = len;
	
	for(auto it:graph[nod]){
		if(it == tata){
			continue;
		}
		predfs(it,nod);
	}
	lst[nod] = len;
}

void dfs(int nod,int tata,int father_ancestor){
	path_to_root.push_back(nod);
	max_on_path.push_back(max(tata ? max_on_path.back():0,nod));
	lvl[nod] = 1 + lvl[tata];
	
	int st = 0,dr = path_to_root.size();
	
	while(dr - st > 1){
		int mid = (st + dr) / 2;
		
		if(max_on_path[mid] >= nod){
			dr = mid;
		}
		else{
			st = mid;
		}
	}
	
	int ancestor = path_to_root[min((int)path_to_root.size() - 1,dr + 1)];///the first ancestor from which i can merge and contribute
	ancestor = (lvl[father_ancestor] > lvl[ancestor] ? father_ancestor:ancestor);
		
	mars[fst[ancestor]] += 1;
	mars[lst[ancestor] + 1] -= 1;
	
	for(auto it:graph[nod]){
		if(it == tata){
			continue;
		}
		dfs(it,nod,ancestor);
	}
	
	path_to_root.pop_back();
	max_on_path.pop_back();
}

int main(){
	
	scanf("%d",&n);
	
	for(int i = 1;i < n;i++){
		int x,y;
		scanf("%d %d",&x,&y);
		graph[x].push_back(y);
		graph[y].push_back(x);
	}
	
	predfs(1,0);
	dfs(1,0,1);
	
	for(int i = 1;i <= n;i++){
		mars[i] += mars[i - 1];
		ans[lin[i]] = mars[i];
	}
	
	for(int i = 2;i <= n;i++){
		printf("%d ",ans[i] - 1);
	}
	
	return 0;
}

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

using namespace std;

#define DUMP(x) std::cerr << (#x) << " = " << (x) << "\n"
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define REP(i, k, n) for (int i = (k); i < (int)(n); ++i)
#define ALL(r) r.begin(), r.end()
#define YES puts("YES")
#define Yes puts("Yes")
#define NO puts("NO")
#define No puts("No")
#define IMP puts("IMPOSSIBLE")
#define Imp puts("Impossible")
#define imp puts("impossible")
#define M1 puts("-1")
#define pb push_back

template <typename T>
ostream &operator<<(ostream &os, vector<T> &v)
{
    os << "{";
    rep(i, v.size()) os << v[i] << (i == (int)v.size() - 1 ? "" : ", ");
    os << "}";
    return os;
}
template <typename T>
T dup(T x, T y)
{
    return (x + y - 1) / y;
};
template <typename A, size_t N, typename T>
inline void arrayFill(A (&array)[N], const T &val) { std::fill((T *)array, (T *)(array + N), val); }
struct in
{
    const size_t n = 0;
    in() = default;
    in(size_t n) : n(n){};
    template <typename T>
    operator T()
    {
        T ret;
        cin >> ret;
        return ret;
    }
    template <typename T>
    operator vector<T>()
    {
        assert(n != 0);
        vector<T> ret(n);
        for (auto &x : ret)
            cin >> x;
        return ret;
    }
};

using ll = int64_t;
using vint = vector<int32_t>;
using vvint = vector<vint>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vstr = vector<string>;
using pint = pair<int32_t, int32_t>;
using pll = pair<ll, ll>;
using setint = set<int32_t>;
using setstr = set<string>;
using qint = queue<int32_t>;
using qpint = queue<pint>;

constexpr std::int32_t INF = 1001001001;
constexpr std::int64_t LINF = 1001001001001001001;

vector<pint> rle(vint v)
{
    vector<pint> ret;
    rep(i, v.size())
    {
        if (ret.empty())
        {
            ret.emplace_back(v[i], 1);
        }
        else
        {
            if (ret.back().first == v[i])
                ++ret.back().second;
            else
                ret.emplace_back(v[i], 1);
        }
    }
    return ret;
}

void Main()
{
    int n = in(), k = in();
    vint a = in(n);
    sort(ALL(a));
    auto v = rle(a);
    sort(ALL(v), [](auto lhs, auto rhs) { return lhs.second > rhs.second; });
    int ans = 0;
    rep(i, v.size())
    {
        if (i >= k)
            ans += v[i].second;
    }
    cout << ans << endl;
}

int main()
{
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 3956
#include<iostream>
#include<vector>

int main(){

    size_t k;
    std::cin >> k;

    std::vector<size_t> v = {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};

    std::cout << v[k - 1] << std::endl;

    return 0;
}


Measured memory_bytes: 256
from collections import deque
K = int(input())

Queue = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
for i in range(K):
    x = Queue[0]
    Queue.popleft()
    oneplace = x % 10

    #(1の位の数)-1を付け加えた数を入れる
    if oneplace == 0: #xの1の位が0
        pass
    else:   #xの1の位が0でない
        enqueue = x * 10 + (oneplace - 1)
        Queue.append(enqueue)
    
    #1の位の数を付け加えた数を入れる
    enqueue = x * 10 + oneplace
    Queue.append(enqueue)

    #(1の位の数)+1を付け加えた数を入れる
    if oneplace == 9:   #xの1の位の数が9
        pass
    else:
        enqueue = x * 10 + (oneplace + 1)
        Queue.append(enqueue)

print(x)

Measured memory_bytes: 12404
#include <iostream>
using namespace std;
int main(void){
    int n, i, j, minj, c, A[101], count = 0;
    cin >> n;
    for(i = 0; i < n; i++)
        cin >> A[i];
    for(i = 0; i < n; i++){
        minj = i;
        for(j = i; j <= n-1; j++){
            if(A[j] < A[minj])
                minj = j;
        }
        if(minj != i){
        c = A[i];
        A[i] = A[minj];
        A[minj] = c;
        count++;
        }
    }
    for(i = 0; i < n; i++){
        if(i != n-1) cout << A[i] << ' ';
        else cout << A[i] << endl;
    }
        cout << count << endl;
    return 0;
}


Measured memory_bytes: 3076
#include <iostream>
using namespace std;
int main(void)
{
  int t;
  int n, h[100]={0};
  int max1=0, min1=0;
  int dumy1=0, dumy2=0;

  cin >> t;
  for(int i = 0 ; i < t ; i++) {
    cin >> n;
    
    /* ツ渉可甘コツ可サ */
    for(int a = 0 ; a < 100 ; a++) {
      h[a] = 0;
    }
    max1 = 0; min1 = 0 ; dumy1 = 0 ; dumy2 = 0;
    
    for(int j = 0 ; j < n ; j++) {
      cin >> h[j];
    }
    
    for(int j = 0 ; j < n ; j++) {
      if(h[j] < h[j+1] && h[j+1] != 0) {
	max1 = h[j+1] - h[j];
	if(max1 >= dumy1) {
	  //  max1 = h[j+1] - h[j];
	  dumy1 = max1; 
	}
      }
      else if(h[j] > h[j+1] && h[j+1] != 0) {
	min1 = h[j] - h[j+1];
	if(min1 >= dumy2) {
	  //min1 = h[j] - h[j+1];
	  dumy2 = min1;
	}
      }
    }
    cout << dumy1 << ' ' << dumy2 << endl;
  }
  return 0;
}

Measured memory_bytes: 0