akhauriyash/Code-Regression huggingface dataset:
// ABC154_F
#include <iostream>
#include <string>
#include <vector>
#include <iterator>
#include <tuple>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <stack>
#include <queue>
#include <algorithm>
#include <functional>  // std::greater<T>()
#include <utility>  // std::swap()
#include <numeric>  // accumulate(ALL(vec), 0)  0 は初期値
#include <bitset>  // static_cast<std::bitset<8>>
#include <sstream>  // std::stringstream
#include <cmath>
#include <cstring>  // std::memset
#include <climits>  // INT_MIN
#include <cctype>  // std::isdigit()
#include <iomanip>
using namespace std;

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> pll;
#define rep(i, n) for (ll i=0; i < n; i++)  // 0 ~ n-1
#define rep1(i, n) for (ll i=1; i <= n; i++)  // 1 ~ n
#define repr(i, n) for (ll i=n-1; i >= 0; i++)  // n-1 ~ 0
#define all(vec) (vec).begin(), (vec).end()
#define sum(vec) accumulate(all(vec), 0LL)  // 0 は初期値
#define min_vec(vec) min_element(all(vec))  // iterator: * を先頭につける
#define max_vec(vec) max_element(all(vec))  // iterator: * を先頭につける
#define idx(vec, element_iter) distance((vec).begin(), element_iter)
const ll INF = 1LL<<60;  // 10^18（const int inf = 1<<29;）
const double PI = acos(-1);

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    
    // input(sunippets: inpv, inpn, inps)
    ll N, n;
    cin >> N;
    set<ll> st;
    rep(i, N) {
        cin >> n;
        st.insert(n);
    }
    
    // calculation
    if ((ll)st.size() == N) cout << "YES" << "\n";
    else cout << "NO" << "\n";
    
    return 0;
}



Measured memory_bytes: 9600
N, M = gets.chomp.split.map(&:to_i)

ans = []

if N.odd?
  1.upto(M) do |i|
    ans.push([i, N-i])
  end
  ans.each do |an|
    puts "#{an[0]} #{an[1]}"
  end
  exit
end

1.upto(M) do |i|
  if N - 2 * i > N/2
    ans.push([i, N-i])
  else
    ans.push([i+1, N-i])
  end
end

ans.each do |an|
  puts "#{an[0]} #{an[1]}"
end


Measured memory_bytes: 19740
#include <stdio.h>

int main()
{
    int i;

    int n;
    scanf("%d", &n);
    int a[n];
    for( i = 0; i < n; ++i ){
        scanf("%d", &a[i]);
    }

    int min = 0, max = 0;
    long int sum = 0;
    for( i = 0; i < n; ++i ){
        min = a[i] < a[min] ? i : min;
        max = a[i] > a[max] ? i : max;
        sum += a[i];
    }

    printf("%d %d %ld\n", a[min], a[max], sum);

    return 0;
}

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

int main() {
  int n;
  vector<int> d;

  cin >> n;
  for (int k = 0; k < n; k++) {
    int t;
    cin >> t;
    d.push_back(t);
  }

  sort(d.begin(), d.end());
  d.erase(unique(d.begin(), d.end()), d.end());
  cout << d.size() << endl;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define REP(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, a, b) for(int i=(a); i<(b); ++i)
#define FORR(i, a, b) for(int i=(b)-1; i>=(a); --i)

#define DEBUG(x) cout<<#x<<": "<<(x)<<'\n'
#define DEBUG_VEC(v) cout<<#v<<":";REP(i, v.size())cout<<' '<<v[i];cout<<'\n'
#define ALL(a) (a).begin(), (a).end()

template<typename T> inline void CHMAX(T& a, const T b) {if(a<b) a=b;}
template<typename T> inline void CHMIN(T& a, const T b) {if(a>b) a=b;}

constexpr ll MOD=1000000007ll;
// constexpr ll MOD=998244353ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

const double EPS=1e-11;
#define EQ0(x) (abs((x))<EPS)
#define EQ(a, b) (abs((a)-(b))<EPS)

template<typename T> struct SegmentTree_min{
	int n;
	vector<T> node;
	T MAX;

	SegmentTree_min(const vector<T> &v, const T &MAX_=INT_MAX){
		init(v, MAX_);
	}

	// n要素で初期化
	void init(const vector<T> &v, const T &MAX_=INT_MAX){
		int n_=v.size();
		n=1;
		while(n<n_){
			n<<=1;
		}
		node.resize(n*2-1);
		MAX=MAX_;
		REP(i, n_){
			node[i+n-1]=v[i];
		}
		FORR(i, 0, n-1){
			node[i]=min(node[i*2+1], node[i*2+2]);
		}
	}

	// k番目(0-indexed)をaに変更
	void update(int k, const T &a){
		k+=n-1;
		node[k]=a;
		while(k>0){
			k=(k-1)/2;
			node[k]=min(node[k*2+1], node[k*2+2]);
		}
	}

	// [a, b)の最小値を求める
	// k: 節点の番号、その節点は[l, r)に対応づく
	T query(int a, int b, int k, int l, int r){
		// [a, b)と[l, r)が交差しなければMAX
		if(r<=a || b<=l){
			return MAX;
		}
		// [a, b)と[l, r)が完全に含んでいればこの節点の値
		if(a<=l && r<=b){
			return node[k];
		}
		// そうでなければ2つの子の最小値
		else{
			T v1=query(a, b, k*2+1, l, (l+r)/2), v2=query(a, b, k*2+2, (l+r)/2, r);
			return min(v1, v2);
		}
	}

	T query(int a, int b){
		return query(a, b, 0, 0, n);
	}
};

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	// cout<<setprecision(10)<<fixed;
	int n;
	vi a(252525);
	cin>>n;
	REP(i, n){
		cin>>a[i];
	}
	SegmentTree_min<int> st(a);
	ll ans=0;
	REP(i, n){
		ll l1=-1, u1=i+1;
		while(u1-l1>1){
			ll mid=(l1+u1)/2;
			if(st.query(mid, i+1)==a[i]){
				u1=mid;
			}
			else{
				l1=mid;
			}
		}
		ll l2=i, u2=n+1;
		while(u2-l2>1){
			ll mid=(l2+u2)/2;
			if(st.query(i, mid+1)==a[i]){
				l2=mid;
			}
			else{
				u2=mid;
			}
		}
		// DEBUG(u1);
		// DEBUG(l2);
		ans+=a[i]*((i-u1+1)*(l2-i+1));
	}
	cout<<ans<<'\n';
	return 0;
}


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

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

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

    int idx = 0;
    int count = 0;
    int fin[N];
    for (int i = 0; i < N; i++) fin[i] = -1;
    while (fin[idx] == -1) {
        fin[idx] = count++;
        idx = A[idx];
    }

    int loopSt = fin[idx];
    int loopEd = count;
    if (K > loopSt) {
        K = (K - loopSt) % (loopEd - loopSt) + loopSt;
    }

    int ans = 0;
    for (int i = 0; i < K; i++) {
        ans = A[ans];
    }
    cout << ans + 1 << endl;
    return 0;
}

Measured memory_bytes: 5196
using System;
using System.Collections.Generic;
using System.Linq;

class Procon
{
    public Procon() { }
    static void Main(string[] agrs)
    {
        new Procon().Do();
    }

    Scanner cin;

    int N, Q;

    string S;

    public void Do()
    {
        cin = new Scanner();
        N = cin.nextInt();
        Q = cin.nextInt();
        S = cin.nextString();

        int[] start = new int[N];
        int[] end = new int[N];
        for (int i = 0; i < N; i++)
        {
            if (i + 1 >= N)
            {
                break;
            }
            else if (i - 1 < 0)
            {
                start[i] = 0;
                end[i + 1] = 0;
            }
            else
            {
                start[i] = start[i - 1];
                end[i + 1] = end[i];
            }

            if (S[i] == 'A' && S[i + 1] == 'C')
            {
                start[i]++;
                end[i + 1]++;
            }
        }

        start[N - 1] = start[N - 2];

        for (int i = 0; i < Q; i++)
        {
            int l = cin.nextInt() - 1;
            int r = cin.nextInt() - 1;
            if (l - 1 < 0)
            {
                Console.WriteLine(end[r]);
            }
            else
            {
                Console.WriteLine(end[r] - start[l - 1]);
            }
        }
    }
}

class Scanner
{
    string[] s;
    int i;
    int max_i;

    public Scanner()
    {
        s = new string[0];
        max_i = 0;
        i = 0;
    }

    public string nextString()
    {
        if (i >= s.Length)
        {
            s = Console.ReadLine().Split(' ');
            max_i = s.Length;
            i = 0;
            if (max_i == 0)
            {
                return "";
            }
            return s[i++];
        }
        else
        {
            return s[i++];
        }
    }

    public int nextInt()
    {
        return int.Parse(nextString());
    }

    public long nextLong()
    {
        return long.Parse(nextString());
    }

    public double nextDouble()
    {
        return double.Parse(nextString());
    }

    public string[] arrayString()
    {
        return Console.ReadLine().Split(' ');
    }

    public int[] arrayInt()
    {
        string[] str = Console.ReadLine().Split(' ');
        int[] array = new int[str.Length];
        for (int i = 0; i < str.Length; i++)
        {
            array[i] = int.Parse(str[i]);
        }
        return array;
    }

    public long[] arrayLong()
    {
        string[] str = Console.ReadLine().Split(' ');
        long[] array = new long[str.Length];
        for (int i = 0; i < str.Length; i++)
        {
            array[i] = long.Parse(str[i]);
        }
        return array;
    }

    public double[] arrayDouble()
    {
        string[] str = Console.ReadLine().Split(' ');
        double[] array = new double[str.Length];
        for (int i = 0; i < str.Length; i++)
        {
            array[i] = double.Parse(str[i]);
        }
        return array;
    }
}

Measured memory_bytes: 17100
#include <bits/stdc++.h>
using namespace std;
int main(){
int64_t A,B,K;
  cin>>A>>B>>K;
  if(A+B<=K)
    cout<<0<<" "<<0<<endl;
   else if(K<A+B &&A<=K){
  cout<<0<<" "<<B+A-K<<endl;
  }else
    cout<<A-K<<" "<<B<<endl;
    
  return 0;
}

Measured memory_bytes: 256
a,b,c,d=map(int,input().split())
l=[a,b,c,d]
w=0
x=0
y=0
z=0
for i in range(4):
  if l[i]==1:
    w+=1
  elif l[i]==4:
    x+=1
  elif l[i]==7:
    y+=1
  elif l[i]==9:
    z+=1
if w==x==y==z==1:
  print('YES')
else:
  print('NO')

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

int translate(char c);

int main()
{
    string line;
    while(cin >> line)
    {
        int buffer = 0;
        int number = 0;
        for(int i=0; i<line.size()-1; i++)
        {
            int current_val = translate(line[i]);
            int next_val = translate(line[i+1]);
            buffer += current_val;
            if(current_val > next_val)
            {
                number += buffer;
                buffer = 0;
            }
            else if(current_val < next_val)
            {
                number -= buffer;
                buffer = 0;
            }
            else
            {
                /* Nop */
            }
        }
        number += buffer;
        number += translate(line[line.size()-1]);
        cout << number << endl;
    }
    return 0;
}

int translate(char c)
{
    int ret_val = 0;
    if(c == 'I')
    {
        ret_val = 1;
    }
    else if(c == 'V')
    {
        ret_val = 5;
    }
    else if(c == 'X')
    {
        ret_val = 10;
    }
    else if(c == 'L')
    {
        ret_val = 50;
    }
    else if(c == 'C')
    {
        ret_val = 100;
    }
    else if(c == 'D')
    {
        ret_val = 500;
    }
    else if(c == 'M')
    {
        ret_val = 1000;
    }
    else
    {
       /* Nop */  
    }
    return ret_val;
}

Measured memory_bytes: 3036
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define per(i, a, b) for(int i = (a); i >= (b); --i)
#define debug(x) cerr << #x << ' ' << x << endl;
using namespace std;

typedef long long ll;
const int mod = 1e9+7;
const int MAXN = 2e5 + 7;
const double EPS=1e-8;
inline int sign(double a){return a<-EPS?-1:a>EPS;}
inline int cmp(double a,double b){return sign(a-b);}
//点
struct P{
    double x,y;
    P(){}
    P(double _x,double _y):x(_x),y(_y){}
    P operator + (P p){return P(x+p.x,y+p.y);}
    P operator - (P p){return P(x-p.x,y-p.y);}
    P operator * (double k){return P(x*k,y*k);}
    P operator / (double k){return P(x/k,y/k);}
    double dot(P p){return x*p.x+y*p.y;}
    double det(P p){return x*p.y-y*p.x;}
    double distTo(P p){return (*this-p).abs();}
    double alpha(){return atan2(y,x);}
    void read(){scanf("%lf%lf", &x, &y);}
    void write(){printf("%.10lf %.10lf\n", x, y);}
    double abs(){return sqrt(abs2());}
    double abs2(){return x*x+y*y;}
    P rot90(){return P(-y,x);}
    P unit(){return *this/abs();}
    int quad(){return sign(y)==1||(sign(y)==0&&sign(x)>=0);}
    P rot(double an){return P(x*cos(an)-y*sin(an),x*sin(an)+y*cos(an));}
    bool operator < (P p)const{int c=cmp(x,p.x);if(c)return c==-1;return cmp(y,p.y)==-1;}
    bool operator == (P o)const{return cmp(x,o.x)==0&&cmp(y,o.y)==0;}
}s[105];

int main(int argc, char const *argv[])
{
    int n;
    scanf("%d", &n);
    rep(i, 0, n-1) s[i].read();
    bool flag = 1;
    rep(i, 0, n-1) if((s[(i+2)%n]-s[(i+1)%n]).det((s[i]-s[(i+1)%n])) < -EPS) flag = 0;
    printf("%d\n", flag);
    return 0;
}



Measured memory_bytes: 3240
#include<cstdio>
#include<cmath>
#include<string>
#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
#include<map>
#include<set>
#include<limits>
#include<bitset>

using namespace std;

//int n;
bool r=true;
string n,m;

int main(){
    cin>>n;
    cin>>m;
    for(int i=0;i<3;i++){
        r=(r and n[i]==m[2-i]);
    }
    cout<<(r ? "YES":"NO")<<endl;
}



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

#ifndef __HEADERS__
#define __HEADERS__

#define up(i,j,k) for (int i = j; i <= k; i++)
#define down(i,j,k) for (int i = j; i >= k; i--)

#define lb long double
#define ll long long
#define ull unsigned long long

#define mp std::make_pair
#define pb push_back

#define all(x) x.begin(), x.end()
#define lowbit(x) ((x) & (-x))
#define mem(a) memset(a, 0, sizeof(a))
#define File(x)                       \
    freopen("" #x ".in", "r", stdin); \
    freopen("" #x ".out", "w", stdout);

#endif

#define int long long

inline int read() {
    int data = 0, w = 1; char ch = 0;
    while (ch != '-' && (ch > '9' || ch < '0')) ch = getchar();
    if (ch == '-') w = -1, ch = getchar();
    while (ch >= '0' && ch <= '9') { data = data * 10 + ch - '0'; ch = getchar(); }
    return data * w;
}

inline void print (ll v) {
    if (v < 0) { putchar('-'); v = -v; }
    if (v > 9) print(v / 10);
    putchar(v % 10 + '0');
}

const int N = 400000;

struct Node {
    int id, key;
    Node (int i = 0, int k = 0) : id(i) , key(k) {}
};

int n, k;
Node v[N];
int x[N], y[N];

bool check(int mid) {
    int use = 0;
    up (i, 1, n) {
        if (v[i].key <= mid) return 1;
        if (v[i].key > mid) {
            int p = v[i].id;
            int num = (x[p] * y[p] - mid + y[p] - 1ll) / y[p];
            if (num > x[p]) return 0;
            use += num;
            if (use > k) return 0;
        }
    }
    return 1;
}

signed main () {
    n = read(); k = read();
    up (i, 1, n) x[i] = read();
    up (i, 1, n) y[i] = read();
    std::sort (x + 1, x + n + 1);
    std::sort (y + 1, y + n + 1, [] (const int &a, const int &b) {return a > b;});
    up (i, 1, n) v[i] = Node(i, x[i] * y[i]);
    std::sort (v + 1, v + n + 1, [] (const Node&a, const Node&b) {return a.key == b.key ? a.id > b.id : a.key > b.key; });
    int l = 0, r = v[1].key, mid, ans = LLONG_MAX;
    while (l <= r) {
        mid = (l + r) / 2;
        if (check(mid)) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    print(ans);
}

Measured memory_bytes: 12288
package main

import "fmt"

func main() {
  var M, D, cnt int
  fmt.Scanf("%d %d", &M, &D)
  for m:=1; m<=M; m++ {
    for d:=22; d<=D; d++ {
      if (d%10)*(d/10)==m && d/10>=2 && d%10>=2 {
        cnt++
      }
    }
  }
  fmt.Println(cnt)
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
int n;
int a[8];
int main() {
	cin>>n;
	for(int i=1; i<=n; i++) {
		string s;
		cin>>s;
		if(s=="AC")
			a[1]++;
		if(s=="WA")
			a[2]++;
		if(s=="TLE")
			a[3]++;
		if(s=="RE")
			a[4]++;
	}
	cout<<"AC x "<<a[1]<<endl;
	cout<<"WA x "<<a[2]<<endl;
	cout<<"TLE x "<<a[3]<<endl;
	cout<<"RE x "<<a[4]<<endl;
	return 0;
}

Measured memory_bytes: 3632
#include <iostream>
using namespace std;
int main() {
    int a, b, i,j;
	cin >> a;
	
	for (i = 1; i <= a; i++) {
		b = i;
		if (b % 3 == 0) cout << ' ' << i;
		else while (1) {
			if (b % 10 == 3) {
			cout << ' ' << i;
			break;
			} 
			if (b<10) break;
			b/=10;
		}
	}
	cout << endl;
	return 0;
}


Measured memory_bytes: 3100
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<iomanip>
#define rep(i,n) for (int i = 0; i < (n); ++i)
typedef long long ll;
using namespace std;

int main(){
    int n;
    cin >> n;
    int ans = n*n;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**5)
#print(sys.getrecursionlimit())
n,m=map(int,input().split())
dp=[-1]*n
E=[ [] for i in range(n) ]

for i in range(m):
  x,y=map(int,input().split())
  x-=1
  y-=1
  E[x].append(y)

def rec(v):
  if dp[v]!=-1:return dp[v]
  res=0
  for nv in E[v]:
    res=max(res,rec(nv)+1)
  dp[v]=res
  return res

res=0
for v in range(n):
  res=max(res,rec(v))
print(res)

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

#define _GLIBCXX_DEBUG
#define all(v) (v).begin(),(v).end()

using namespace std;

using ll=long long;
using ld=long double;
using pii=pair<int, int>;
using vi=vector<int>;
using vii=vector<vector<int>>;

const ll LINF=1LL<<60;
const int INF=1<<29;
const int MOD=1e9+7;

template<typename T> bool chmin(T &a,const T b){if(a>b){a=b; return true;}return false;}
template<typename T> bool chmax(T &a,const T b){if(a<b){a=b; return true;}return false;}


int main(){
    int N; cin >> N;
    vi H(N);
    for(auto &x : H) cin >> x;

    bool ans=true;
    for(int i=1; i<N; i++){
        if(H[i] < H[i-1]){
            ans=false;
            break;
        }
        if(H[i] > H[i-1]) H[i]--;
    }
    cout << (ans?"Yes":"No") << endl;
    return 0;
}

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

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

    int ans = 0;
    vector<int> A(M, 0);
    for(int i = 0; i < N; i++){
        int K; cin >> K;
        for(int k = 0; k < K; k++){
            int a; cin >> a, a--;
            if(++A[a] == N) ans++;
        }
    }

    cout << ans << endl;

}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma comment(linker, "/stack:200000000")

#include <bits/stdc++.h>

using namespace std;

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

#define X first
#define Y second

//#include <boost/unordered_map.hpp>
//using namespace boost;

/*
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rbtree;
rbtree T;
*/

namespace io{
	const int L = (1 << 20) + 1;

	char buf[L], *S , *T, c;

	char getchar() {
		if(__builtin_expect(S == T, 0)) {
			T = (S = buf) + fread(buf, 1, L, stdin);
			return (S == T ? EOF : *S++);
		}
		return *S++;
	}

	int inp() {
		int x = 0, f = 1; char ch;
		for(ch = getchar(); !isdigit(ch); ch = getchar())
			if(ch == '-') f = -1;
		for(; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
		return x * f;
	}

	unsigned inpu()
	{
		unsigned x = 0; char ch;
		for(ch = getchar(); !isdigit(ch); ch = getchar());
		for(; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
		return x;
	}

	ll inp_ll() {
		ll x = 0; int f = 1; char ch;
		for(ch = getchar(); !isdigit(ch); ch = getchar())
			if(ch == '-') f = -1;
		for(; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
		return x * f;
	}

	char B[45], *outs=B+40, *outr=B+40;
	template<class T>
	inline void print(register T a,register char x=0){
		if(x) *--outs = x, x = 0;

		if(!a)*--outs = '0';
		else
			while(a)
				*--outs = (a % 10) + 48, a /= 10;

		if(x)
			*--outs = x;

		fwrite(outs, outr - outs , 1, stdout);
		outs = outr;
	}
};

using io :: print;
using io :: inp;
using io :: inpu;
using io :: inp_ll;

using i32 = int;
using i64 = long long;
using u8 = unsigned char;
using u32 = unsigned;
using u64 = unsigned long long;
using f64 = double;
using f80 = long double;
//using i128 = __int128_t;
//using u128 = __uint128_t;
using i128 = i64;
using u128 = u64;

ll power(ll a, ll b, ll p)
{
	if (!b) return 1;
	ll t = power(a, b/2, p);
	t = t*t%p;
	if (b&1) t = t*a%p;
	return t;
}

ll exgcd(ll a, ll b, ll &x, ll &y)
{
	if (b == 0)
	{
		x = 1;
		y = 0;
		return a;
	}
	ll px, py;
	ll d = exgcd(b, a%b, px, py);
	x = py;
	y = px-a/b*py;
	return d;
}

template<class T>
inline void freshmin(T &a, const T &b)
{
	if (a > b) a = b;
}

template<class T>
inline void freshmax(T &a, const T &b)
{
	if (a < b) a = b;
}

const int MOD = 1000000007;
const int INF = 1000000000;
const int MAXN = 3010;

ll C[MAXN][MAXN];

int main()
{
	
	int n = 2010;
	for (int i = 0; i <= n; ++ i)
		C[i][0] = 1;
	for (int i = 1; i <= n; ++ i)
		for (int j = 1; j <= i; ++ j)
			C[i][j] = (C[i-1][j-1]+C[i-1][j])%MOD;
	
	int N, K;
	cin >> N >> K;
	for (int i = 1; i <= K; ++ i)
	{
		cout << C[K-1][i-1]*C[N-K+1][i]%MOD << endl;
	}
	
	return 0;
}


Measured memory_bytes: 47744
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
	static long[] accum(long A[]){
		long ret[] = new long[A.length + 1];
		ret[0] = 0;
		for(int i = 0 ; i < A.length ; ++i){
			ret[i + 1] = ret[i] + A[i];
		}
		return ret;
	}
	static long[] rev(long A[]){
		long[] ret = new long[A.length];
		for(int i = 0 ; i < ret.length ; ++i){
			ret[i] = A[A.length - 1 - i];
		}
		return ret;
	}
	static long solve(int X , int Y , long P[] , long Q[] , long R[]){
		PriorityQueue<Long> pq = new PriorityQueue<Long>();
		for(int i = 0 ; i < X ; ++i){
			pq.add(P[i]);
		}
		for(int i = 0 ; i < Y ; ++i){
			pq.add(Q[i]);
		}
		for(int i = 0 ; i < R.length ; ++i){
			long c = pq.peek();
			long ri = R[i];
			if(c > ri){
				break;
			}else{
				pq.poll();
				pq.add(ri);
			}
		}
		long S = 0;
		for(long v : pq){
			S += v;
		}
		return S;
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int X = sc.nextInt();
		int Y = sc.nextInt();
		int A = sc.nextInt();
		int B = sc.nextInt();
		int C = sc.nextInt();
		long P[] = new long[A];
		long Q[] = new long[B];
		long R[] = new long[C];
		for(int i = 0 ; i < A ; ++i){
			P[i] = sc.nextLong();
		}
		for(int i = 0 ; i < B ; ++i){
			Q[i] = sc.nextLong();
		}
		for(int i = 0 ; i < C ; ++i){
			R[i] = sc.nextLong();
		}
		Arrays.sort(P);
		Arrays.sort(Q);
		Arrays.sort(R);
		System.out.println(solve(X , Y , rev(P) , rev(Q) , rev(R)));
	}
}


Measured memory_bytes: 98756
#include<iostream>
#include<vector>
#include<map>
using namespace std;
int main()
{
	int N,Y, sum;
	cin >> N >> Y;
	int ans[3];

	int flag = 0;
	for (int i=N;i>=0;i--){
		for(int j=0;j<=N-i;j++){
			sum = i*10000 + j*5000 + (N - i - j)*1000;
			if(sum==Y){
				flag = 1;
				ans[0] = i;
				ans[1] = j;
				ans[2] = (N-i-j);
				break;
			}
		}
		if(flag == 1){
			break;
		}
	}
	if(flag==1){
		cout << ans[0] << " " << ans[1] << " " << ans[2] << endl;
	}else{
		cout << "-1 -1 -1" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
M = (10**9+7)
s = list(input())[::-1]

mo = []
fixed = 0
for i in range(len(s)):
  if s[i]!='?':
    t = int(s[i])
    fixed += (t*pow(10,i,13))
    fixed %= 13
  else:
    t = []
    for j in range(10):
      t.append((j*pow(10,i,13)%13))
    mo.append(tuple(t))

if len(mo)==0:
  if fixed == 5:
    print(1)
  else:
    print(0)
  exit()
  
dp = [[-1]*13 for _ in range(len(mo))]

for m in mo[0]:
  dp[0][m] = 1
for i in range(len(mo)-1):
  for j in range(13):
    if dp[i][j]==-1:
      continue
    dp_i = dp[i+1]
    dp_j = dp[i]
    for m in mo[i+1]:
      p = (j+m)%13
      if dp_i[p] == -1:
        dp_i[p] = 0
      dp_i[p] += dp_j[j]
      dp_i[p]  %= M

ans = dp[-1][(18-fixed)%13] % M 
if dp[-1][(18-fixed)%13] == -1:
  print(0)
  exit()
print(ans)

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

using namespace std;

vector<string> split(const string& s, char c) {
    vector<string> v; stringstream ss(s); string x;
    while (getline(ss, x, c)) v.emplace_back(x); return move(v);
}
template<typename T, typename... Args>
inline string arrStr(T arr, int n) {
    stringstream s; s << "[";
    for(int i = 0; i < n - 1; i++) s << arr[i] << ",";
    s << arr[n - 1] << "]";
    return s.str();
}

#define ANTHRO(args...) {__anthro_begin(__LINE__); __anthro(split(#args, ',').begin(), args);}

inline void __anthro_begin(int line) { cerr << "#" << line << ": "; }
template<typename T> inline void __anthro_out_var(vector<T> val) { cerr << arrStr(val, val.size()); }
template<typename T> inline void __anthro_out_var(T* val) { cerr << arrStr(val,2); } //Change the values in case you want to debug something
template<typename T> inline void __anthro_out_var(T val) { cerr << val; }
inline void __anthro(vector<string>::iterator it) { cerr << endl; }

template<typename T, typename... Args>
inline void __anthro(vector<string>::iterator it, T a, Args... args) {
    cerr << it->substr((*it)[0] == ' ', it->length()) << "=";
    __anthro_out_var(a);
    cerr << "; ";
    __anthro(++it, args...);
}
//Simple Debugger

#define ll long long
#define MOD 1000000007
#define EPS 1e-9
int const INF = (int)1e9 + 1e3;
ll const INFL = (ll)1e18 + 1e6;
/*
    This is F-LCS from Atcoder JP
*/

int main(){
    string s,t; cin>>s>>t;
    ll sl,tl; sl=s.length(),tl=t.length();
    vector<vector<ll>> dp(sl+1,vector<ll> (tl+1,-INF));
    dp[0][0]=0;
    //cout<<"W"<<endl;
    for(ll i=0;i<=sl;i++){
        for(ll j=0;j<=tl;j++){
            if(i==0||j==0){dp[i][j]=0;}
            else if(s.at(i-1)==t.at(j-1)){
                dp[i][j]=dp[i-1][j-1]+1;
            }
            else{
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
    }
    //cout<<"W"<<endl;
    ll in=dp[sl][tl];
    string an; //This is an empty string
    ll i=sl,j=tl;
    while(i>0 && j>0){
        if(s.at(i-1)==t.at(j-1)){
            an+=s.at(i-1);
            i--;j--;
        }
        else if(dp[i-1][j]>dp[i][j-1]){
            i--;
        }
        else{
            j--;
        }
    }
    reverse(an.begin(),an.end());
    cout<<an;
    return 0;
}



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

int main() {
    char a[100] = {};
    a['A'] = 'T';
    a['T'] = 'A';
    a['C'] = 'G';
    a['G'] = 'C';

    char c;
    cin >> c;

    cout << a[c] << endl;

    return 0;
}


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

int main()
{
    string T;
    cin >> T;
    int mx_len = -1;
    int tmp = 0;
    for(int i=0; i<T.length(); i++)
    {
        if(T[i]=='A' || T[i]=='C' || T[i]=='G' || T[i]=='T')
        {
            tmp++;
        }
        if(T[i]!='A' && T[i]!='C' && T[i]!='G' && T[i]!='T')
        {
            mx_len = max(mx_len, tmp);
            tmp = 0;
        }
        mx_len = max(mx_len, tmp);
    }
    cout << max(mx_len, 0) << endl;
    return 0;
}

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

int main(){
    int h, w;
    cin >> h >> w;
    vector<string> v(h);
    rep(i,h) cin >> v.at(i);

    bool f = true;
    rep(y,h){
        rep(x,w){
            if (v[y][x]=='#' && f){
                bool u=true, d=true, l=true, r=true;
                if (y > 0   && v[y-1][x]=='.') u = false;
                if (x > 0   && v[y][x-1]=='.') l = false;
                if (y < h-1 && v[y+1][x]=='.') d = false;
                if (x < w-1 && v[y][x+1]=='.') r = false;
                f = u || d || l || r;
            }
        }
    }
    if (f) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<cctype>
#include<cstdio>
using namespace std;
#define REP(i, a, n) for(int i=0; i<n; i++)

int main()
{
	string A, B;
	cin >> A >> B;
	if (A.size() > B.size()) {
		cout << "GREATER" << endl;
	}
	else if (A.size() < B.size()) {
		cout << "LESS" << endl;
	}
	else {
		int i = 0;
		while(i<A.size()) {
			if (A[i]+0 > B[i]+0) {
				cout << "GREATER" << endl;
				break;
			}
			else if (A[i] + 0 < B[i] + 0) {
				cout << "LESS" << endl;
				break;
			}
			i++;
		}
		if (i == A.size()) cout << "EQUAL" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#define MAX 10000
#define NIL -1

struct Node{
  int parent;
  int left;
  int right;
};

int n, D[MAX], H[MAX];
struct Node T[MAX];

void set_Depth(int, int);
int set_Height(int);
int getSibling(int);
void print(int);

int main(){
  int i, v, l, r, root = 0;
  scanf("%d", &n);

  for(i = 0 ; i < n ; i++)T[i].parent = NIL;

  for(i = 0 ; i < n ; i++){
    scanf("%d %d %d", &v, &l, &r);
    T[v].left = l;
    T[v].right = r;
    if(l != NIL)T[l].parent = v;
    if(r != NIL)T[r].parent = v;
  }

  for(i = 0; i < n ;i++)if(T[i].parent == NIL)root = i;

  set_Depth(root, 0);
  set_Height(root);

  for(i = 0 ; i < n ; i++)print(i);

  return 0;
}

void set_Depth(int u, int d){
  if(u == NIL)return;
  D[u] = d;
  set_Depth(T[u].left, d + 1);
  set_Depth(T[u].right, d + 1);
}

int set_Height(int u){
  int h1 = 0, h2 = 0;
  if(T[u].left != NIL)
    h1 = set_Height(T[u].left) + 1;
  if(T[u].right != NIL)
    h2 = set_Height(T[u].right) + 1;
  return H[u] = (h1 > h2 ? h1 : h2);
}

int getSibling(int u){
  if(T[u].parent == NIL)return NIL;
  if(T[T[u].parent].left != u && T[T[u].parent].left != NIL)
    return T[T[u].parent].left;
  if(T[T[u].parent].right != u && T[T[u].parent].right != NIL)
      return T[T[u].parent].right;
  return NIL;
}

void print(int u){
  printf("node %d: ", u);
  printf("parent = %d, ", T[u].parent);
  printf("sibling = %d, ", getSibling(u));
  int deg = 0;
  if(T[u].left != NIL)deg++;
  if(T[u].right != NIL)deg++;
  printf("degree = %d, ", deg);
  printf("depth = %d, ", D[u]);
  printf("height = %d, ", H[u]);

  if(T[u].parent ==NIL){
    printf("root\n");
  }else if(T[u].left == NIL && T[u].right == NIL){
    printf("leaf\n");
  }else{
    printf("internal node\n");
  }
}



Measured memory_bytes: 2148
#include <stdio.h>
 
int main(void)
{
	int a,b=0,c=0,ans;
	char s[200000];
	scanf("%s",&s);
	for(a=0;a<strlen(s);a++){
		if(s[a]=='A'&&c==0){
			c=1;
		}
		if(c==1){
			b++;
			if(s[a]=='Z'){
				ans=b;
			}
		}
	}
	printf("%d",ans);
	return 0;
}

Measured memory_bytes: 512
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int MAX=105;
const int INF= 1<<30;
int M[MAX][MAX],n,d[MAX],p[MAX],vis[MAX];
void init(){
	for(int i=0;i<n;i++){
		d[i]=INF;
		p[i]=-1;
		vis[i]=0;
	}
	d[0]=0;
}
void dijkstra(){
	init();
	while (true){
		int u=-1;
		int minCost=INF;
		for(int i=0;i<n;i++){
			if(!vis[i] && d[i]<minCost){
				u=i;
				minCost=d[i];
			}
		}
		if(u==-1)break;
		vis[u]=1;
		for(int i=0;i<n;i++){
			if(!vis[i] && M[u][i]!=-1 &&M[u][i]+d[u]<d[i]){
				d[i]=M[u][i]+d[u];
				p[i]=u;
			}
		}
	}
}
int main(){
	cin>>n;
	memset(M,-1,sizeof(M));
	for(int i=0;i<n;i++){
		int u,k,v,c;
		cin>>u>>k;
		for(int j=0;j<k;j++){
			cin>>v>>c;
			M[u][v]=c;
		}
	}
	dijkstra();
	for(int i=0;i<n;i++){
		printf("%d %d\n",i,d[i]);
	}
	return 0;
} 


Measured memory_bytes: 3192
<?php
  list($n, $m, $x) = explode(" ", trim(fgets(STDIN)));
  $a = explode(" ", trim(fgets(STDIN)));


  $g=0;
  $s=0;
  for($i=0;$i<$m;$i++){
    if($x > $a[$i]) $g++;
    else $s++;
  }

  echo min($s, $g).PHP_EOL;

Measured memory_bytes: 16308
#include <iostream>
#include <string>
#include <sstream>
 
using namespace std;
 
int main()
{
    string s = "";
    getline(cin, s);
    string str = s.substr(0, 4);
    str += " " + s.substr(4,11);
    cout << str << endl;
    return 0;
}

Measured memory_bytes: 384
using System;
using System.Collections.Generic;
using System.Linq;

class G
{
	static int[] Read() => Console.ReadLine().Split().Select(int.Parse).ToArray();
	static void Main()
	{
		var h = Read();
		var n = h[0];
		// 多重辺および自己ループを除去。
		var es = new int[h[1]].Select(_ => Read()).Select(e => (v0: e[0], v1: e[1])).Where(e => e.v0 != e.v1).Distinct().ToArray();

		var map = Array.ConvertAll(new int[n], _ => new List<int>());
		var map_r = Array.ConvertAll(new int[n], _ => new List<int>());
		foreach (var (v0, v1) in es)
		{
			map[v0].Add(v1);
			map_r[v1].Add(v0);
		}

		var u = new bool[n];
		var order = new List<int>();
		var gs = new List<List<int>>();
		List<int> lg = null;

		Action<int> Dfs = null;
		Dfs = v =>
		{
			u[v] = true;
			foreach (var nv in map[v]) if (!u[nv]) Dfs(nv);
			order.Add(v);
		};
		for (int v = 0; v < n; v++) if (!u[v]) Dfs(v);

		Action<int> Dfs_r = null;
		Dfs_r = v =>
		{
			u[v] = true;
			foreach (var nv in map_r[v]) if (!u[nv]) Dfs_r(nv);
			lg.Add(v);
		};
		Array.Clear(u, 0, n);
		order.Reverse();
		foreach (var v in order) if (!u[v]) { gs.Add(lg = new List<int>()); Dfs_r(v); }

		Console.WriteLine(gs.Count);
		Console.WriteLine(string.Join("\n", gs.Select(g => string.Join(" ", g.Prepend(g.Count)))));
	}
}


Measured memory_bytes: 177396
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <set>
#include <queue>
#include <map>
#include <numeric>
#include <functional>
#include <math.h>

using namespace std;

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

#define INF ((int)1e9)
#define INFLL ((ll)1e18)
#define MOD (1000000007LL)


int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<int> A(N);
    for (int n = 0; n < N; ++n) cin >> A[n];
    
    int Tmp = 1;
    int Res = 0;
    for (int n = 0; n < N; ++n) {
        if (A[n] == Tmp) {
            ++Tmp;
        } else {
            ++Res;
        }
    }
    if (Tmp == 1) {
        Res = -1;
    }
    cout << Res << endl;

    return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <string>
using namespace std;
int main(){
    string s; cin >> s;
    s = s.substr(0,s.size()-1);
    while(1){
        int n = s.size();
        s = s.substr(0,n-1);
        if(s.size()%2 != 0) continue;
        if(s.substr(0,n/2) == s.substr(n/2)){
            cout << n-1 << endl;
            break;
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main()
{
    int x,y;
    while(1){
        scanf("%d %d", &x, &y);
        if(x==0&&y==0){
            break;
        }
        if(x<y){
            printf("%d %d\n", x, y);
        }
        else{
            printf("%d %d\n", y, x);
        }
    }
    return 0;
}

Measured memory_bytes: 600
import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
S = list(input())[: -1]
qs = [input().split() for _ in range(Q)]

def lcheck(x):
  i = x
  for t, d in qs:
    if S[i] == t:
      if d == "L": i -= 1
      else: i += 1
    if i in range(N): continue
    return i < 0
  return False

def rcheck(x):
  i = x
  for t, d in qs:
    if S[i] == t:
      if d == "L": i -= 1
      else: i += 1
    if i in range(N): continue
    return i >= N
  return False

ok = -1
ng = N
while ng - ok > 1:
  m = (ok + ng) // 2
  if lcheck(m): ok = m
  else: ng = m

res = N - ng

ok = N
ng = -1
while ok - ng > 1:
  m = (ok + ng) // 2
  if rcheck(m): ok = m
  else: ng = m

res -= N - ok
print(res)

Measured memory_bytes: 120584
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#include <functional>
#include <ctime>
#include <cmath>
#include <limits>
#include <numeric>
#include <type_traits>
#include <iomanip>
#include <float.h>
#include <math.h>
using namespace std;
using ll = long long;


unsigned euclidean_gcd(unsigned a, unsigned b) {
    if (a < b) return euclidean_gcd(b, a);
    unsigned r;
    while ((r = a % b)) {
        a = b;
        b = r;
    }
    return b;
}

class UnionFind {
public:
    vector <ll> par;
    vector <ll> siz;
    UnionFind(ll sz_) : par(sz_), siz(sz_, 1LL) {
        for (ll i = 0; i < sz_; ++i) par[i] = i;
    }
    void init(ll sz_) {
        par.resize(sz_);
        siz.assign(sz_, 1LL);
        for (ll i = 0; i < sz_; ++i) par[i] = i;
    }
    ll root(ll x) {
        while (par[x] != x) {
            x = par[x] = par[par[x]];
        }
        return x;
    }
    bool merge(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }

    bool issame(ll x, ll y) {
        return root(x) == root(y);
    }

    ll size(ll x) {
        return siz[root(x)];
    }
};

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

long long modinv(long long a, long long mod) {
    return modpow(a, mod - 2, mod);
}

void dfs(vector<vector<ll>> &p, vector<ll> &oyaa,ll &ans,ll now,ll oyan, vector<ll> &ansoyaa,ll nnow,ll node,ll &nownode) {
    if (nownode <= node)return;
    if (oyaa[now] != -1 && nownode > node) {
        oyaa[now] = oyan;
        ans = now;
        nownode = node;
        for (int i = 0; i < oyaa.size(); i++) {
            ansoyaa[i] = oyaa[i];
        }
        oyaa[now] = -1;
        return;
    }
    oyaa[now] = oyan;
    for (int i = 0; i < p[now].size(); i++) {
        dfs(p, oyaa, ans, p[now][i], now,ansoyaa,nnow,node+1,nownode);
    }
    oyaa[now] = -1;
    return;
}

int main() {
    ll n;
    cin >> n;
    ll ans = 0;
    ll m = 1111;
    for (int i = 0; i < n; i++) {
        ll a;
        cin >> a;
        ans += a;
        if (a % 10 != 0)m = min(m, a);
    }
    if (ans % 10 != 0)cout << ans << endl;
    else if (m == 1111)cout << 0 << endl;
    else cout << ans - m << endl;
}

Measured memory_bytes: 256
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;

public class Main{
	Scanner sc=new Scanner(System.in);

	int INF=1<<28;
	double EPS=1e-12;

	int caze, t, n=5;
	int[][][] a;
	boolean[] birth, survive;

	void run(){
		for(caze=1;; caze++){
			t=sc.nextInt();
			if(t==0){
				break;
			}
			a=new int[n][n][n];
			for(int k=0; k<n; k++){
				for(int j=0; j<n; j++){
					String s=sc.next();
					for(int i=0; i<n; i++){
						a[k][j][i]=s.charAt(i)-'0';
					}
				}
			}
			birth=new boolean[27];
			survive=new boolean[27];
			int m1=sc.nextInt();
			for(int i=0; i<m1; i++){
				birth[sc.nextInt()]=true;
			}
			int m2=sc.nextInt();
			for(int i=0; i<m2; i++){
				survive[sc.nextInt()]=true;
			}
			solve();
		}
	}

	void solve(){
		for(; t>0; t--){
			int[][][] b=new int[n][n][n];
			for(int z=0; z<n; z++){
				for(int y=0; y<n; y++){
					for(int x=0; x<n; x++){
						int live=0;
						for(int k=-1; k<=1; k++){
							for(int j=-1; j<=1; j++){
								for(int i=-1; i<=1; i++){
									if(i==0&&j==0&&k==0){
										continue;
									}
									if(ok(x+i)&&ok(y+j)&&ok(z+k)){
										live+=a[z+k][y+j][x+i];
									}
								}
							}
						}
						if(a[z][y][x]==0&&birth[live]){
							b[z][y][x]=1;
						}
						if(a[z][y][x]==1&&survive[live]){
							b[z][y][x]=1;
						}
					}
				}
			}
			for(int z=0; z<n; z++){
				for(int y=0; y<n; y++){
					for(int x=0; x<n; x++){
						a[z][y][x]=b[z][y][x];
					}
				}
			}
		}
		if(caze>1){
			println("");
		}
		println("Case "+caze+":");
		for(int z=0; z<n; z++){
			for(int y=0; y<n; y++){
				for(int x=0; x<n; x++){
					print(a[z][y][x]+"");
				}
				println("");
			}
			if(z<n-1){
				println("");
			}
		}
	}

	boolean ok(int x){
		return x>=0&&x<n;
	}

	void debug(Object... os){
		System.err.println(Arrays.deepToString(os));
	}

	void print(String s){
		System.out.print(s);
	}

	void println(String s){
		System.out.println(s);
	}

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

Measured memory_bytes: 29160
#include<bits/stdc++.h>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>

#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long int
#define mod 1000000007
#define inf 1e18+42
#define endl "\n"
#define pi 3.1415926535897932384626433832795028841971693993751058
#define maxn 100005

#define out1(a) cout<<#a<<" "<<a<<endl
#define out2(a,b) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<endl
#define out3(a,b,c) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<endl

#define rep(i,a,b) for(int i=a;i<b;i++)
#define repr(i,a,b) for(int i=a;i>=b;i--)
#define fori(it,A) for(auto it=A.begin();it!=A.end();it++)

#define ft first
#define sd second
#define pb push_back
#define mp make_pair
#define pq priority_queue
#define all(x) (x).begin(),(x).end()
#define zero(x) memset(x,0,sizeof(x));
 
using namespace std;

int binpow(int a, int b) {
    int res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

//START OF CODE ->->->->->->->

void solve()
{
    string s;
    cin>>s;

    rep(i,0,s.length())
    {
        if ( s[i] == '?' )
        {
            s[i] = 'D';
        }
    }

    cout<<s<<endl;
}

//END OF CODE ->->->->->->->->

signed main()
{
    fast;
    int t = 1;
    // cin>>t;

    while(t--)
    {
        solve();
    }
    return 0;
}


Measured memory_bytes: 3772
#include<iostream>
#include<string>
#include<algorithm>
#include<stack>
#include<queue>
#include<cmath>
#include<iomanip>
using namespace std;
using ll = long long;
const int mod = 1000000007;

int ex (int a,int b){
  int t=a;
  for (int i=1;i<b;i++){
    t*=a;
  }
  return t;
}

int main(){
  int X;
  cin>>X;
  vector<int> b;
  b.push_back(1);
  for (int i=2;i<X;i++){
    for (int j=2;j<X;j++){
      int t=ex(i,j);
      if (t<=X) b.push_back(t);
      else break;
    }
  }
  sort(b.begin(),b.end(),greater<int>());
  cout<<b[0]<<endl;
  return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<string>
#include<vector>
using namespace std;
#define MOD  1000000007

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
int dp[100001] = { 1 };
bool ok[100001];
int main(){
	int n, m;
	int tmp;
	cin >> n >> m;
	for (int i = 0; i <= n; i++) ok[i] = true;
	for (int i = 0; i < m; i++) {
		cin >> tmp;
		ok[tmp] = false;
	}
	if (ok[1]) {
		dp[1] = 1;
	}
	for (int i = 2; i <=n; i++) {
		dp[i] %= MOD;
		if (ok[i - 1]) dp[i] += (dp[i - 1] % MOD);
		dp[i] %= MOD;
		if (ok[i - 2]) dp[i] += (dp[i - 2] % MOD);
		dp[i] %= MOD;
	}
	dp[n] %= MOD;
	cout << dp[n] << endl;
	return 0;
}


Measured memory_bytes: 768
import java.util.Scanner;

public class Main {
	class Card {
		String card;
		int value;
		Card(String card) {
			this.card = card;
			this.value = card.charAt(1) - '0';
		}
	}

	void run() {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		Card[] bubble = new Card[n];
		Card[] select = new Card[n];
		for (int i = 0; i < n; i++) {
			String card = scan.next();
			bubble[i] = new Card(card);
			select[i] = new Card(card);
		}

		bubbleSort(bubble, n);
		selectionSort(select, n);

		boolean stable = true;
		for (int i = 0; i < n; i++) {
			if (bubble[i].card.compareTo(select[i].card) != 0)
				stable = false;
		}

		for (int i = 0; i < n; i++)
			System.out.print(bubble[i].card + (i != n - 1 ? " ":"\n"));
		System.out.println("Stable");
		for (int i = 0; i < n; i++)
			System.out.print(select[i].card + (i != n - 1 ? " ":"\n"));
		System.out.println(stable ? "Stable" : "Not stable");
	}

	void bubbleSort(Card[] c, int n) {
		for (int i = 0; i < n; i++) {
			for (int j = n - 1; j >= i + 1; j--) {
				if (c[j].value < c[j - 1].value) {
					Card tmp = c[j];
					c[j] = c[j - 1];
					c[j - 1] = tmp;
				}
			}
		}
	}

	void selectionSort(Card[] c, int n) {
		for (int i = 0; i < n; i++) {
			int minj = i;
			for (int j = i; j < n; j++) {
				if (c[j].value < c[minj].value)
					minj = j;
			}
			Card tmp = c[i];
			c[i] = c[minj];
			c[minj] = tmp;
		}
	}

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



Measured memory_bytes: 26332
#include <stdio.h>

int main(void){
	int n,m;
	int i,j;
	int a[100][100] = {0};
	int b[100] = {0};
	int c[100] = {0};
	scanf("%d %d",&n,&m);
	
	for(i=0;i<n;i++){
		for(j=0;j<m;j++){
			scanf("%d",&a[i][j]);
		}
	}
	for(i=0;i<m;i++) scanf("%d",&b[i]);
	
	for(i=0;i<n;i++){
		int sum=0;
		for(j=0;j<m;j++){
			sum += a[i][j] * b[j];
		}
		c[i] = sum;
	}

	for(i = 0;i<n;i++) printf("%d\n",c[i]);

	return 0;
}

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

#define int long long
#define rep(i,l,r) for(int i=(int)(l);i<(int)(r);i++)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)x.size())
template<class T>bool chmax(T &a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a,T b){if(a>b){a=b;return 1;}return 0;}

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;

const int inf = 1LL<<60;
const int mod = 1e9 + 7;
const double eps = 1e-9;

/*{
  }*/

signed main(){
  int h, w;
  cin >> h >> w;

  vector<string> a(h);
  rep(i, 0, h) cin >> a[i];

  vvi dp(h, vi(w));
  dp[0][0] = 1;
  rep(i, 0, h) rep(j, 0, w){
    if(j+1 < w and a[i][j+1] == '.') (dp[i][j+1] += dp[i][j]) %= mod;
    if(i+1 < h and a[i+1][j] == '.') (dp[i+1][j] += dp[i][j]) %= mod;
  }

  cout << dp[h-1][w-1] << endl;

  return 0;
}


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

int main()
{

  ll n, W;
  cin >> n >> W;

  ll w, p;
  vector<ll> dp(100005, 1e18);
  dp[0] = 0;

  for(ll i=1; i<=n; i++)
  {
    cin >> w >> p;
    for(ll j=100000; j>=p; j--)
    {
      dp[j] = min(dp[j], w+dp[j-p]);
    }
  }

  ll ans = 0;
  for(ll i=100000; i>=0; i--)
    if(dp[i] <= W)
      ans = max(ans , i);
  
  cout<<ans;
  return  0;

}


Measured memory_bytes: 1024
import sys, bisect
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N = I()
    A = []
    B = []
    for _ in range(N):
        a, b = LI()
        A.append(a)
        B.append(b)

    A.sort()
    B.sort()

    A_med = 0
    B_med = 0
    if N%2==0:
        A_med_2 = (A[N//2-1] + A[N//2])
        B_med_2 = (B[N//2-1] + B[N//2])
        print((B_med_2-A_med_2)+1)
    else:
        A_med_2 = A[(N+1)//2-1]*2
        B_med_2 = B[(N+1)//2-1]*2
        print((B_med_2-A_med_2)//2+1)

if __name__ == '__main__':
    resolve()


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

int main(void) {
	int K, A, B;
	cin >> K >> A >> B;

	bool ans = false;
	if (B / K > A / K)
		ans = true;
	else if (B % K == 0 || A % K == 0)
		ans = true;

	cout << (ans ? "OK\n" : "NG\n");
	return 0;
}


Measured memory_bytes: 3624
n=int(input())
L=list(map(int, input().split()))

L.sort()
cnt=0

for a in range (0, n-2):
    for b in range(a+1, n-1):
        for c in range(b+1, n):
            if L[a]!=L[b] and L[b]!=L[c] and L[c]!=L[a]:
                if L[a] + L[b] > L[c]:
                    cnt+=1

print(cnt)

Measured memory_bytes: 73496
import math
import sys

def getinputdata():

    # 配列初期化
    array_result = []
    
    data = input()

    
    array_result.append(data.split(" "))

    flg = 1

    try:


        while flg:

            data = input()

            array_temp = []

            if(data != ""):
                
                array_result.append(data.split(" "))

                flg = 1

            else:

                flg = 0
    finally:


        return array_result





arr_data = getinputdata()

n = int(arr_data[0][0])

mysum=0


hash01={}
for i in range(1,1+n):

#    temp=int(arr_data[i][0])
    
    cnt=hash01.get(int(arr_data[i][0]),0)+1
    
    hash01[int(arr_data[i][0])]=cnt
    
#print(hash01)

for k in hash01:
    
    if hash01[k] % 2!=0:
        
        mysum+=1
        
print(mysum)

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

typedef long long ll;

ll a[111];

int main(void)
{
	ll n, i, j, k, ans = 0;

	scanf("%lld", &n);
	for (i = 1; i <= n; i++)
		scanf("%lld", &a[i]);

	for (i = 1; i <= n; i++)
		for (j = i + 1; j <= n; j++)
			for (k = j + 1; k <= n; k++)
				if (a[i] != a[j] && a[j] != a[k] && a[k] != a[i] && 2 * max(a[i], max(a[j], a[k])) < a[i] + a[j] + a[k])
					ans++;

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

Measured memory_bytes: 3824