akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            var str = Console.ReadLine().Split();
            var n = UInt64.Parse(str[0]);
            var x = UInt64.Parse(str[1]);
            Console.WriteLine(Solver.Solve(n, x));
        }
    }

    public class Solver
    {
        public static UInt64 Solve(UInt64 n, UInt64 x)
        {
            var ret = x + (n - x);
            ret += dfs(x, n - x);
            return ret;
        }

        public static UInt64 dfs(UInt64 a, UInt64 b)
        {
            if (a == 0 || b == 0) return 0;
            if (b % a == 0)
            {
                return a * 2 * (b / a - 1) + a;
            }

            var ret = (2 * a) * (b / a);
            if (a % (b % a) == 0) return ret + ((b % a) * 2) * (a / (b % a)) - b % a;

            ret += ((b % a) * 2) * (a / (b % a));
            return ret + dfs(a % (b % a), b % a);
        }
    }

}


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

#define MOD 1000000007

using namespace std;

int main() {
	int n, x;
	int pre = 0, cur = 1;
	map<int, int> last;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &x);
		if (x == pre) {
			continue;
		}
		if (last.count(x) != 0) {
			cur = 1LL * (cur + last[x]) % MOD;
		}
		last[x] = cur;
		pre = x;
	}
	cout << cur << endl;
	return 0;
}

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

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

    string s;
    cin >> s;
    int n = s.size() + 1;
    vector<int> ans(n, -1);
    if (s.front() == '<') {
        ans[0] = 0;
    }
    if (s.back() == '>') {
        ans[n - 1] = 0;
    }
    for (int i = 0; i < n - 2; i++) {
        if (s[i] == '>' && s[i + 1] == '<') {
            ans[i + 1] = 0;
        }
    }
    function<void(int, int)> migi = [&](int p, int v) {
        ans[p] = max(ans[p], v);
        if (p + 1 < n && s[p] == '<') {
            migi(p + 1, v + 1);
        }
    };
    function<void(int, int)> hidari = [&](int p, int v) {
        ans[p] = max(ans[p], v);
        if (p - 1 >= 0 && s[p - 1] == '>') {
            hidari(p - 1, v + 1);
        }
    };
    for (int i = 0; i < n; i++) {
        if (ans[i] == 0) {
            migi(i, 0);
            hidari(i, 0);
        }
    }
    // for (int a : ans) {
    //     cout << a << ' ';
    // }
    cout << accumulate(ans.begin(), ans.end(), 0LL) << endl;
}


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

const int maxn = 1e5 + 5;
int mark[maxn];
int par[maxn];
int hig[maxn];
int zir[maxn];
int dp[maxn];
int minDpKids[maxn];
int minHig[maxn];

vector<int> adj[maxn];
vector< pair<int,int> > output;

void dfs (int v) {
    mark[v] = 1;
    zir[v] = 1;

    for (int u : adj[v] ) {
        if ( !mark[u] ) {
            par[u] = v;
            hig[u] = hig[v] + 1;
            dfs(u);
            zir[v] += zir[u];
            dp[v] = min (dp[v] , dp[u]);
        }
        else if ( u != par[v] && hig[u] < hig[v]) {
            dp[v] = min(hig[u] , dp[v]);
        }
    }

    if (dp[v] >= hig[v] && dp[v] + hig[v] != 0){

        pair<int,int> outy (min (par[v] , v) , max (par[v] , v)) ;
        output.push_back(outy);
    }
}

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

    int n , m;
    cin >> n >> m;

    for(int i=1; i<n; i++)
        dp[i] = 100005;

    for (int i = 0; i<m; i++) {
        int u, v;
        cin >> u >> v;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs(0);

    sort (output.begin() , output.end());

    for(int i = 0; i < output.size(); i++)
        cout << output[i].first << ' ' << output[i].second << endl;

    return 0;
}

/*

4 4
0 1
0 2
1 2
2 3
----------
5 4
0 1
1 2
2 3
3 4
----------
6 5
0 1
0 2
0 3
1 4
4 5

*/



Measured memory_bytes: 7116
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int h = sc.nextInt();
		int w = sc.nextInt();
		int c = sc.nextInt();
		if (h==w&&w==c) {
			System.out.println(1);
		} else if (h==w&&w!=c) {
			System.out.println(2);
		} else if (h!=w&&w==c) {
			System.out.println(2);
		} else if (h==c) {
			System.out.println(2);
		} else  {
			System.out.println(3);
		}
	}
}

Measured memory_bytes: 21716
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const ll mod = 1000000007;
const int INF = 1001001001;

int main(){
    ll n; cin >> n;
    ll a = sqrt(n);
    for(int i=a;i>=1;i--){
        if(n%i==0){
            n/=i;
            break;
        }
    }
    cout << (int)((to_string(n)).size()) << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long int ll;

int main(){
	int N, K;
	cin >> N >> K;
	vector<ll> A(N);
	for(int i = 0; i < N; i++) cin >> A[i];
	ll res = 0;
	for(int i = 0; i < N; i++){
		for(int j = i; j <= N; j++){
			if(N - (j - i) > K) continue;
			vector<ll> va;
			for(int k = 0; k < N; k++){
				if(k >= i && k < j) continue;
				va.push_back(A[k]);
			}
			sort(va.begin(), va.end());
			ll sum = 0;
			for(int k = 0; k < va.size(); k++){
				if(va[k] < 0 && k < K - va.size()) continue;
				sum += va[k];
			}
			res = max(res, sum);
		}
	}
	cout << res << endl;
	return 0;
}

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

int main (void)
{
    int n,m,i;
    scanf("%d %d",&n,&m);
    int a[m+1][2],b[n+1];
    for(i=1;i<=n;i++)
    {
        b[i]=0;
    }
    for(i=1;i<=m;i++)
    {
        scanf("%d %d",&a[i][0],&a[i][1]);
        if(a[i][0]==1)
        {
            b[a[i][1]]++;
        }
    }
    for(i=1;i<=m;i++)
    {
        if(a[i][1]==n&&b[a[i][0]]!=0)
        {
            puts("POSSIBLE");
            return 0;
        }
    }
    puts("IMPOSSIBLE");
    return 0;
}

Measured memory_bytes: 3988
#include<stdio.h>
#include<math.h>
#include <limits.h>
#include<stdlib.h>


int main() {
	int n;
	int count = 0;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		count = 0;
		for (int x = 1; x < (int)sqrt(i); x++) {
			for (int y = 1; y <= x; y++) {
				for (int z = 1; z <=y; z++) {
					if ((x * x + y * y + z * z + x * y + x * z + z * y) == i) {
						if (x == y && x==z) {
							count++;
						}
						else if (x == y || y == z || x == z) {
							count += 3;
						}
						else {
							count += 6;
						}
					}
				}
			}
		}
		printf("%d\n", count);
	}
	
	return 0;
}

Measured memory_bytes: 2112
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <queue>

typedef unsigned long long ULLONG;
typedef long long LLONG;
static const LLONG MOD_NUM = 1000000007;

template<class _T> static void getint(_T& a) {
	std::cin >> a;
}
template<class _T> static void getint(_T& a, _T& b) {
	std::cin >> a >> b;
}
template<class _T> static void getint(_T& a, _T& b, _T& c) {
	std::cin >> a >> b >> c;
}

static void A_task();

int main()
{
	A_task();
	fflush(stdout);
	return 0;
}

static void A_task()
{
	std::string orgs;
	std::cin >> orgs;

	for (int i = 0; i < 3; i++) {
		printf("%c", orgs[i]);
	}
	putchar('\n');
}


Measured memory_bytes: 3628
n = int(input())
a = list(map(int,input().split()))
bi = [0 for i in range(20)]
l = 0
r = 0
ans = 0
while True:
    if r == n:
        break
    rflag = False
    kar = bi[:]
    for i in range(20):
        if a[r] >> i & 1 == 1:
            kar[i] += 1
            if kar[i] == 2:
                rflag = True
    while True:
        if not rflag:
            bi = kar[:]
            break
        ans += r - l
        for i in range(20):
            if a[l] >> i & 1 == 1:
                kar[i] -= 1
        l += 1
        if max(kar) <= 1:
            rflag = False
    r += 1
ans += (r-l)*(r-l-1)//2 + r-l
print(ans)

Measured memory_bytes: 100460
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PI 3.14159265
int main()
{
    long double a, b, c;
    cin >> a >> b >> c;
    //long double aa = sqrt(a);
    //long double = sqrt(b);
    //long double cc = sqrt(c);
    long double ss = 1.0E-14;
    if(sqrt(a)+sqrt(b)+ss <  sqrt(c))
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
#define inf (int)(1e9+7)
#define INF (ll)(1e18)
#define abs(x) (x >= 0 ? x : -(x))
#define ceil(a, b) a / b + !!(a % b)
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    
    int n;
    cin >> n;
    if (n == 0) { cout << 0 << endl; return 0; }
    vector<int> v;
    
    while (n) {
        // cout << n << " " << n % -2 << " " << n / -2 << endl;
        int r = n % -2, s = n / -2;
        if (r == -1) {
            r = 1;
            ++s;
        }
        v.eb(r);
        n = s;
    }
    
    reverse(all(v));
    rep(i, sz(v)) cout << v[i]; cout << endl;
}


Measured memory_bytes: 256
#include<cstdio>
int main(){
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    for(int i=0;i<=n;i++){
        for(int j=0;j<=m;j++){
            if(i*j+(n-i)*(m-j)==k){
                printf("Yes");
                return 0;
            }
        }
    }
    printf("No");
    return 0;
}

Measured memory_bytes: 128
import java.util.*;

public class Main{
  public static void main(String[] args){
    Scanner scan = new Scanner(System.in);
    int n = scan.nextInt();
    long [] a = new long[n+1];
    long [] b = new long[n];
    long [] d = new long[n];
    for (int i=0;i<n+1;i++){
      a[i] = scan.nextLong();
    }
    for (int j=0;j<n;j++){
      b[j] = scan.nextLong();
    }
    long sum = 0;
    for (int k=0;k<n-1;k++){
      if (a[k] > d[k]){
        sum += d[k];
        a[k] -= d[k];
      }
      else{
        sum += a[k];
        d[k+1] = b[k];
        continue;
      }

      long c = b[k] - a[k];
      if (c >= 0){
        sum += a[k];
        d[k+1] += c;
      }
      else{
        sum += b[k];
      }
    }

    if (d[n-1] >= a[n-1]){
      sum += a[n-1];
      a[n-1] = 0;
    }
    else{
      sum += d[n-1];
      a[n-1] -= d[n-1];
    }
    
    if (b[n-1] > a[n-1] + a[n]){
      b[n-1] = a[n-1] + a[n];
    }
    sum += b[n-1];
    System.out.println(sum);

  }
}


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

#include <algorithm>
using namespace std;
struct Fast {
    Fast() {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(20);
    }
} fast;

long long mod = 1000000007;

long long modpow(long long m, long long n) {
    if (n == 0) return 1;
    if (n % 2 == 0) {
        long long t = modpow(m, n / 2);
        return (t * t) % mod;
    } else {
        return (modpow(m, n - 1) * m) % mod;
    }
}
int power(long long x, long long y, long long p) {
    long long res = 1;  // Initialize result

    x = x % p;  // Update x if it is more than or
                // equal to p

    while (y > 0) {
        // If y is odd, multiply x with result
        if (y & 1) res = (res * x) % p;

        // y must be even now
        y = y >> 1;  // y = y/2
        x = (x * x) % p;
    }
    return res;
}

long long modInverse(long long n, long long p) { return power(n, p - 2, p); }

long long nCrModPFermat(long long n, long long r, long long p) {
    if (r == 0) return 1;
    long long fac[n + 1];
    fac[0] = 1;
    for (long long i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % p;

    return (fac[n] * modInverse(fac[r], p) % p * modInverse(fac[n - r], p) % p) % p;
}

void yes() {
    cout << "Yes" << endl;
    exit(0);
}
void no() {
    cout << "No" << endl;
    exit(0);
}
#define REP(i, n) for (long long i = 0; i < (n); i++)

signed main() {
    long long x;
    cin >> x;
    if (x < 7) {
        cout << 1 << endl;
        return 0;
    } else if (x < 12) {
        cout << 2 << endl;
        return 0;
    }
    if (x % 11 == 0){
        cout << (x / 11) * 2 << endl;
    }else if (x % 11 < 7) {
        cout << (x / 11) * 2 + 1 << endl;
    } else {
        cout << (x / 11) * 2 + 2 << endl;
    }
}

Measured memory_bytes: 256
import java.util.*;

class Main{
public static void main(String[] args){
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	int m = sc.nextInt();
	int[] a = new int[m];
	int[] b = new int[m];
	for(int i=0; i<m; i++) {
		a[i] = sc.nextInt();
		b[i] = sc.nextInt();
	}
	int[] ans = new int[n];
	for(int i=0; i<m; i++) {
		ans[a[i]-1]++;
		ans[b[i]-1]++;
	}
	for(int i=0; i<n; i++) {
	System.out.println(ans[i]);
	}
}
}


Measured memory_bytes: 21716
#include<iostream>
#include<iomanip>
#include<string>
#include<set>
#include<vector>
#include<utility>
#include<algorithm>

using namespace std;

#define LL long long
#define MOD 1000000007

int n, m, losc[5002] = {}, tmp;
bool ansf = false;
vector<int>wl[5002];

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int w, l;
		cin >> w >> l;
		w--; l--;
		wl[w].push_back(l);
		losc[l]++;
	}
	for (tmp = 0; tmp < n; tmp++) {
		if (losc[tmp] == 0) break;
	}
	for (int i = 0; i < n; i++) {
		int top = tmp;
		losc[top] = -1;
		for (int j = 0; j < wl[top].size(); j++) losc[wl[top][j]]--;
		for (int j = 0; j < n; j++) {
			if (losc[j] == 0) {
				if (tmp == top)tmp = j;
				else ansf = true;
			}
		}
		cout << top + 1 << endl;
	}
	cout << (ansf ? 1 : 0) << endl;

	return 0;
}


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

#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x,y) x ## y

using i8  = int8_t;
using u8  = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;

using f32 = float;
using f64 = double;

#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) for(i64 i = 1; i <= n; ++i)
#define RREP(i, n) for(i64 i = n - 1; i >= 0 ; --i)
#define RREPS(i, n) for(i64 i = n; i >= 1; --i)

#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))

#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define pb push_back
#define mp make_pair
#define F first
#define S second

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

template<typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }

template<typename T, size_t N>
i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); }


struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;

    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;

#define MAX_N 100000
string S;
i64 N;
i64 res[MAX_N];

void solve() {
  REP(i, N) res[i] = 0;

  i64 R_cnt = 0;
  i64 L_cnt = 0;
  i64 R_sink = -1;
  REP(i, N) {
    if (S[i] == 'R') R_cnt++;
    if (S[i] == 'L') L_cnt++;

    if (S[i] == 'R' && S[i + 1] == 'L') {
      R_sink = i;
    }

    if ((S[i] == 'L' && S[i + 1] == 'R') || i == N - 1) {
      res[R_sink] = L_cnt / 2 + (R_cnt - R_cnt / 2);
      res[R_sink + 1] = R_cnt / 2 + (L_cnt - L_cnt / 2);

      R_sink = -1;
      R_cnt = 0;
      L_cnt = 0;
    }
  }

  REP(i, N) {
    cout << res[i] << " ";
  }
  cout << endl;
}


int main() {
  cin >> S;
  N = S.length();

  solve();

  return 0;
}

Measured memory_bytes: 1488
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define o(a) cout << a << endl
#define int long long
#define fi first
#define se second
using namespace std;
typedef pair<int, int> P;

const int MAX_N = 200010;
int prime[MAX_N];
bool is_prime[MAX_N + 1];
void sieve(int n){
    int p = 0;
    for(int i = 0; i <= n; i++) is_prime[i] = true;
    is_prime[0] = is_prime[1] = false;
    for(int i = 2; i <= n; i++){
        if(is_prime[i]){
            prime[p++] = i;
            for(int j = 2*i; j <= n; j += i) is_prime[j] = false;
        }
    }
}


signed main(){
    int n, p;
    sieve(200000);
    while(1){
        cin >> n >> p;
        if(n == -1 && p == -1) break;
        int ans = 0;
        vector<int> d;
        set<int> st;
        int id = -1;
        rep(i, 0, 200010){
            if(prime[i] > n){
                id = i;
                break;
            }
        }
        rep(i, 0, 200){
            rep(j, i, 200){
                int sum = prime[id + i] + prime[id + j];
                // if(!st.count(sum)){
                    d.push_back(sum);
                    st.insert(sum);
                // }
            }
        }
        sort(all(d));
        cout << d[p - 1] << endl;
    }
}

Measured memory_bytes: 3756
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
using namespace std;
#define lli long long int
#define all(x) x.begin(),x.end()
#define siz(x) x.size()
#define prs(x,y) x.find(y)!=x.end()
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
const int INF = 1<<29;
typedef long long ll;
inline int two(int n) { return 1 << n; }
inline int test(int n, int b) { return (n>>b)&1; }
inline void set_bit(int & n, int b) { n |= two(b); }
inline void unset_bit(int & n, int b) { n &= ~two(b); }
inline int last_bit(int n) { return n & (-n); }
inline int ones(int n) { int res = 0; while(n && ++res) n-=n&(-n); return res;}
inline int level(int n){int ans=0;while(n%2==0){n/=2;ans++;}return ans;}
int main()
{
	int n;
	cin>>n;
	lli cnt[200005];
	memset(cnt,0,sizeof(cnt));
	for(int i=1;i<n;i++)
	{
		int x;
		cin>>x;
		cnt[x]++;
	}
	for(int i=1;i<=n;i++)
		cout<<cnt[i]<<"\n";

}



Measured memory_bytes: 5196
#include <bits/stdc++.h>
#define nMAX 100
#define MAX 2000
using namespace std;
int n, res=0;
vector<vector<int>> M;
vector<int> now;

int buildT()
{
    int tryn, min, d[nMAX], p[nMAX], pass[nMAX];
    for(int i=0; i<n; i++)
    {
        if(i!=0) d[i] = MAX+1;
        p[i] = -1;
        pass[i] = 0;
    }
    while(1)
    {
        min = MAX + 1;
        tryn = -1;
        for(int i=0; i<n; i++)
        {
            if(min > d[i] && pass[i] !=now[2])
            {
                min = d[i];
                tryn = i;
            }
        }
        if(min == MAX + 1) break;
        pass[tryn] = now[2]; //went
        for(int i=0; i<n; i++)
        {
            if(pass[i] != now[2] && M[tryn][i] !=MAX + 1)
            {
                if(d[i] > M[tryn][i])
                {
                    d[i] = M[tryn][i];
                    p[i] = tryn;
                    pass[i] = now[1];
                }
            }
        }

    }
    for(int i=0; i<n; i++)
    {
        if(p[i] != -1) res+= M[i][p[i]];
    }
    return res;
}

int main()
{
    now.resize(3);
    for(int i=0; i<3; i++) now[i] = i;
    //0 NON 1TRYING 2DEAD
    //input
    cin >> n;
    M.assign(n, vector<int> (n));
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            cin >> M[i][j];
            if(M[i][j] == -1) M[i][j] = MAX + 1;
        }
    }
    printf("%d\n", buildT());
}


Measured memory_bytes: 3320
#include<bits/stdc++.h>
using namespace std;
long long MOD=998244353LL;
long long dp[200100];
pair<int,int> robo[200100];
int n;
stack<pair<int,long long> > stk;//pos,dp val
int main(){
	ios::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>robo[i].first>>robo[i].second;
		robo[i].second+=robo[i].first;
	}
	sort(robo+1,robo+n+1);
	stk.emplace(2e9,1LL);
	dp[n+1]=1LL;
	for(int i=n;i>=1;i--){
		while(stk.size()&&stk.top().first<robo[i].second){//无关的机器人 
			stk.pop();
		}
		if(!stk.empty()){
			dp[i]=stk.top().second;
		}
		dp[i]=(dp[i]+dp[i+1])%MOD;
		stk.emplace(robo[i].first,dp[i]);
	} 
	cout<<dp[1]<<endl;
	return 0;
}


Measured memory_bytes: 4992
# include <bits/stdc++.h>
 
/*
// ordered_set 
# include <ext/pb_ds/assoc_container.hpp>
# include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
# define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
*/
 
using namespace std;
 
typedef long long                                        ll;
typedef long double                                      ld;
typedef pair <int, int>                                  pii;
typedef pair <pii, int>                                  ppi;
typedef pair <int, pii>                                  pip;
typedef pair <pii, pii>                                  ppp;
typedef pair <ll, ll>                                    pll;
 
# define A                                               first
# define B                                               second
# define endl                                            '\n'
# define sep                                             ' '
# define all(x)                                          x.begin(), x.end()
# define kill(x)                                         return cout << x << endl, 0
# define SZ(x)                                           int(x.size())
# define Sort(x)                                         sort(all(x))
# define InTheNameOfGod                                  ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
 
ll power(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * power(a * a % md, b / 2, md) % md : power(a * a % md, b / 2, md) % md));}
 
const int xn = 100 + 10;
const int xm = -20 + 10;
const int SQ = 320;
const int sq = 320 + 10;
const int inf = 1e9 + 10;
const ll INF = 1e18 + 10;
const int MOD = 1e9 + 7;
const int TM = 3;
const int BASE = 257;

string s;
ll n, ans, res;
 
int main(){
    InTheNameOfGod;
    
    cin >> s;
    n = SZ(s);
    for (ll i = 0; i < n; ++ i){
    	res = 0;
    	for (ll j = i; j < n; ++ j){
    		res = res * 10 + (s[j] - '0');
    		ans += res * power(2, max(0LL, i - 1) + max(0LL, n - j - 2), INF);
		}
	}
	cout << ans << endl;
	
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
typedef long long ll;
#include <cmath>
#include <vector>
#include <algorithm>

void dump(int a[],int n)
{
  for (int codeTest = 0; codeTest < n; ++codeTest) {
    if (codeTest!=0)std::cout << " ";
    std::cout << a[codeTest];
  }
  std::cout << '\n';
}

int main() {
  float ans;
  int n;
  std::cin >> n;
  if (n%2){
    ans=(n+1.0)/2.0/n;
  }else{
    ans=1.0/2.0;
  }
  std::cout << ans << '\n';
}


Measured memory_bytes: 888
// Copyright 2020 yaito3014
#include <bits/stdc++.h>

int main() {
  using namespace std;
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  using ll = long long;
  using P = pair<ll, ll>;
  constexpr int MOD = 1000000007;
  auto normalize = [](const P& p){
  	auto [A, B] = p;
  	if (A == 0) B = abs(B);
  	else if (B == 0) A = abs(A);
  	else if (B < 0) A *= -1, B *= -1;
  	return make_pair(A, B);
  };
  auto modpow = [&](ll a, int n) -> int {
  	ll res{1};
  	while (n > 0) {
  		if (n % 2 == 1) res = res * a % MOD;
  		a = a * a % MOD;
  		n /= 2;
  	}
  	return res;
  };
  int N;
  cin >> N;
  vector<P> AB(N);
  for (auto& [A, B] : AB) {
  	cin >> A >> B;
  	ll g = gcd(A, B);
  	if(g == 0) continue;
  	A /= g, B /= g;
  	if (A == 0) B = abs(B);
  	else if (B == 0) A = abs(A);
  	else if (B < 0) A *= -1, B *= -1;
  }
  map<pair<ll, ll>, int> m;
  for (const auto& p : AB) ++m[p];
  ll ans = 1;
  int zeros = m[make_pair(0ll, 0ll)];
  m.erase(make_pair(0ll, 0ll));
  while (!m.empty()) {
  	auto[p, c] = *begin(m);
  	const auto& [A, B] = p;
  	auto iter = m.find(normalize(make_pair(-B, A)));
  	ll op = 
  		iter == m.end() ? modpow(2, c) :
  		(modpow(2, c) + modpow(2, iter->second) - 1) % MOD;
  	ans = ans * op % MOD;
  	if (iter != begin(m) && iter != end(m)) m.erase(iter);
  	m.erase(begin(m));
  }
  ans = (ans + zeros - 1+MOD) % MOD;
  cout << ans << endl;
}


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

const int MAX = 100000;

vector<int> G[MAX];
int N;
bool visited[MAX];
int prenum[MAX],parent[MAX],lowest[MAX],timer;

void dfs(int current,int prev){
prenum[current] = lowest[current] = timer;
timer++;

visited[current] = true;

int next;

for(int i=0;i<G[current].size();i++){
next = G[current][i];
if(!visited[next]){
parent[next] = current;
dfs(next,current);
lowest[current] = min(lowest[current],lowest[next]);
}else if(next!= prev){
lowest[current] = min(lowest[current],prenum[next]);
}
}
}

void art_points(){
for(int i=0;i<N;i++)visited[i] = false;
timer = 1;
dfs(0,-1);

set<int> ap;
int np = 0;
for(int i=1;i<N;i++){
int p = parent[i];
if(p==0)np++;
else if(prenum[p]<=lowest[i])ap.insert(p);
}
if(np>1)ap.insert(0);
for(set<int>::iterator it = ap.begin();it!=ap.end();it++)
cout<<*it<<endl;
}

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

for(int i=0;i<m;i++){
int s,t;
cin>>s>>t;
G[s].push_back(t);
G[t].push_back(s);
}
art_points();

return 0;
}



Measured memory_bytes: 6884
#include<bits/stdc++.h>
using namespace std;
long double X[200100];
int N;
long long Count(long double len)
{
  long long Ans=0;
  for(int i=0;i<N;i++)
  {
    Ans+=(long long)(X[i]/len);//解答引っ張ってきた人の条件。なぜか通る
    //Ans+= ceil(X[i]/len)-1;//多少遅くなるがこっちが正解
  }
  return Ans;
}

int main()
	{
	  long long K;
	  cin>>N>>K;
	  for(int i=0;i<N;i++)
	{
		cin>>X[i];
		//X[i]-=0.1;
	}

  long double l=1,r=1e9;
  //while(l<r-0.1)//解答を引っ張ってきた人の条件。なぜかOKだったが、lとｒの整数部が異なる状態でループを出ると問題になるはず
	for(int i=0;i<300;i++)//OK log2(10^9)=30.二分探索だとこのやり方安定する。ただし、浮動小数のせいか34以上でないと通らず。
  //while(!((ceil(r)-ceil(l)) == 0))//NG:左端が初期値0のままだと、右端のceilは0にならず、無限ループ
	//while(!((floor(r)-floor(l)) == 0))//OK:右端がぴったり整数にならなければ成立.(あまりよくない)
  {
    long double mid=(l+r)/2;
    if(Count(mid)<=K) r=mid;
    else	l=mid;
  }
  cout<<(long long)(l+0.999)<<endl;
  return 0;
}


Measured memory_bytes: 6708
#include <iostream>
#include <algorithm>
#include <string>
#include <fstream>
#include <vector>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <list>
#include <bitset>

using namespace std;
typedef long long ll;

// #define DEBUG

class Unionfind
{
    vector<int> p;

public:
    Unionfind(int n);
    int find(int x);
    void unite(int x, int y);
    bool match(int x, int y);
};

Unionfind::Unionfind(int n)
{
    for (int i = 0; i < n; i++)
    {
        p.push_back(i);
    }
}

int Unionfind::find(int x)
{
    while (p[x] != x)
    {
        p[x] = p[p[x]];
        x = p[x];
    }
    return x;
}

bool Unionfind::match(int x, int y)
{
    return (find(x) == find(y)) ? true : false;
}

void Unionfind::unite(int x, int y)
{
    x = Unionfind::find(x);
    y = Unionfind::find(y);
    if (x != y)
    {
        p[x] = y;
    }
}

int main()
{
#ifdef DEBUG
    cout << "DEBUG MODE" << endl;
    ifstream in("input.txt"); //for debug
    cin.rdbuf(in.rdbuf());    //for debug
#endif
    int n, m, x;
    set<int> a, b, c;

    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> x;
        a.insert(x);
    }
    cin >> m;
    for (int i = 0; i < m; i++)
    {
        cin >> x;
        b.insert(x);
    }

    for (auto itr = a.begin(); itr != a.end(); itr++)
    {
        auto itr2 = b.find(*itr);
        if (itr2 != b.end())
            c.insert(*itr);
    }

    for (auto itr = c.begin(); itr != c.end(); itr++)
    {
        cout << *itr << endl;
    }

    return 0;
}

// getline(cin,s);
// a = strtok(s, ",");  ","で分解
// for (int i = 0; i < n; i++)


Measured memory_bytes: 23672
/* 
 * Author: Priyadarshini
 */
 
/*
 * Run in Mac using the following command:
 * g++ -std=c++14 <cpp_filename>
 * A binary will be generated. Then run:
 * ./a.out
 */
 
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <fstream>
#include <cstring>
#include <math.h>
 
using namespace std;
typedef long long int ll;
 
// Macro //
#define X first
#define Y second
#define pii pair<int,int>
#define pll pair<ll,ll>
 
// Global //
 
 
// Functions //
double calculate_average(int * a, vector <pll >p, int N){
    double dist = 0;
    for(int i = 0;i < N - 1; i++){
        dist += (sqrt(pow(p[a[i + 1]].first - p[a[i]].first, 2) +  
                pow(p[a[i + 1]].second - p[a[i]].second, 2) * 1.0)); 
    }
    return dist;
}
// void display(int a[], int n) 
// { 
//     for (int i = 0; i < n; i++) { 
//         cout << a[i] << "  "; 
//     } 
//     cout << endl; 
// }
// Main //
int main()
{
    int N;
    cin >> N;
    vector<pll> p;
    double c1, c2;
    for(int i = 0;i < N; i++){
        cin >> c1 >>c2;
        p.push_back(make_pair(c1, c2));
    }
    double average = 0;
    ll count = 0;
    int a[N];
    for(int i = 0;i < N; i++)a[i] = i;

    do { 
        average += calculate_average(a, p, N); 
        // display(a, N);
        count++;
    } while (next_permutation(a, a + N));
    if(N != 0) average /= count;
    printf("%.10f", average);
}


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

using namespace std;

char GetSym(char c, int change) {
  if (c == 'A' && change % 2) {
    return 'B';
  }
  if (c == 'B' && change % 2) {
    return 'A';
  }
  return c;
}

void RevSym(char& c) {
  if (c == 'A') {
    c = 'B';
  } else {
    c = 'A';
  }
}

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

  int n, k;
  cin >> n >> k;
  std::string s;
  cin >> s;

  std::vector<char> all;
  all.resize(s.size());
  int ind_cur = 0;

  for (int i = 0; i < s.size(); i++) {
    all[i] = s[i];
  }

  int overall_revs = 0;
  while (k--) {
    if (GetSym(all[ind_cur], overall_revs) == 'A') {
      RevSym(all[ind_cur]);
      continue;
    }
    overall_revs++;
    all[ind_cur] = 'A' + (overall_revs) % 2;
    ind_cur++;
    if (ind_cur >= n) {
      ind_cur = 0;
    }
  }
  for (int i = 0; i < n; i++) {
    cout << GetSym(all[ind_cur], overall_revs);
    ind_cur++;
    if (ind_cur >= n) {
      ind_cur = 0;
    }
  }
  cout << endl;

}

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

const int N = 22;
const int BM = 1<<N;
const int M = 1e9+7;
const int INF = 0x3f3f3f3f;
int n;
int a[N][N];
ll mem[BM][N];
ll dp(int bm, int i) {
  ll & ans = mem[bm][i];
  //cerr << bm << " " << i <<endl;
  if (i==n) return 1;
  if (ans!=-1) return ans;
  ans = 0;
  for(int j=0;j<n;j++) {
    if (bm>>j&1 || a[i][j]==0) continue;
    ans+=dp(bm^(1<<j), i+1);
    ans%=M;
  }
  return ans;
}

int main(){
  cin.tie(0); ios_base::sync_with_stdio(0);
  memset(mem, -1, sizeof mem);
  cin >> n;
  for(int i=0;i<n;i++) {
    for(int j=0;j<n;j++) {
      cin >> a[i][j];
    }
  }
  cout << dp(0, 0) <<endl;
}


Measured memory_bytes: 721280
#include <iostream>
#include <fstream>
#include <typeinfo>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <iomanip>
#include <cctype>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<25;
const double pi=acos(-1);
const double eps=1e-8;
const vi emp;

struct point{
    double x,y;
    point operator+(point p){
        return point{x+p.x,y+p.y};
    }
    point operator-(point p){
        return point{x-p.x,y-p.y};
    }
    point operator*(double p){
    return point{x*p,y*p};
    }
    point operator/(double p){
        if(!p) return point{0,0}; 
        return point{x/p,y/p};
    }
    bool operator==(point p){
        return fabs(x-p.x)<eps&&fabs(y-p.y)<eps;
    }
};
 
typedef pair<point,point> pp;
typedef vector<point> VP;
const point O{0,0};
 
class Geom{
    public:
    double Length(point x,point y){
        point z=y-x;
        return sqrt(z.x*z.x+z.y*z.y);
    }
    double IP(point p,point q){
        return p.x*q.x+p.y*q.y;
    }
    double CP(point p,point q){
        return p.x*q.y-q.x*p.y;
    }
    string Counter_Clockwise(pp a,point x){
        point A=a.second-a.first;
        point X=x-a.first;
        double ip=IP(A,X),cp=CP(A,X),Al=Length(O,A),Xl=Length(O,X);
        if(cp>eps) return "Counter_Clockwise";
        if(cp<-eps) return "Clockwise";
        if(ip<-eps) return "Online_Back";
        if(Xl<Al||fabs(Xl-Al)<eps) return "On_Segment";
        return "Online_Front";
    }
	double Heron(point A,point B,point C){
		double a=Length(B,C),b=Length(C,A),c=Length(A,B),s=(a+b+c)/2;
		return sqrt(s*(s-a)*(s-b)*(s-c));
	}
	double Area(VP p){
		double sum;
		string s;
		p.push_back(p[0]);
		for(VP::iterator i=p.begin()+1;i!=p.end();i++){
			s=Counter_Clockwise(pp(O,*(i-1)),*i);
			if(s[1]=='o') sum+=Heron(O,*(i-1),*i);
			else if(s[1]=='l') sum-=Heron(O,*(i-1),*i);
		}
		return sum;
	}
	string Convex_Concave(VP p){
		p.push_back(p[0]);
		string s;
		for(VP::iterator i=p.begin()+1;i!=p.end()-1;i++){
			s=Counter_Clockwise(pp(*(i-1),*i),*(i+1));
			if(s[1]=='l') return "Concave";
		}
		return "Convex";
	}
    void Point_in(point& p){
        cin>>p.x>>p.y;
    }
};

int N;
VP p;

int main(){
	cout<<syosu(1);
	Geom geo;
	cin>>N;
	p=VP(N);
	for(VP::iterator i=p.begin();i!=p.end();i++) geo.Point_in(*i);
	string s=geo.Convex_Concave(p);
	if(s=="Convex") cout<<1<<endl;
	else cout<<0<<endl;
}

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

// 7 x x 6
// 7 2 6

// a,c,c,c,c,c,d,d,d,d,b

// i個目まで増加
// c*i<= sum <= d*i
// n-2-i個で減少
// c*(n-2-i)<= rsum ≤= d*(n-2-i)

// 00000000c0000000d00000
///000c00000000d

// sum-rsum が b-aからc-d以内

int main() {
    ll n,a,b,c,d;
    std::cin >> n>>a>>b>>c>>d;
    
    if(abs(a-b) > (n-1)*d){
        std::cout << "NO" << std::endl;
        return 0;
    }
    
    if(abs(a-b) >= (n-1)*c){
        std::cout << "YES" << std::endl;
        return 0;
    }
    
    for (int i = 0; i <= n-2; i++) {
        // i個目で減少
        ll sc,sd,rc,rd;
        sc = c*i;
        sd = d*i;
        rc = c*(n-2-i);
        rd = d*(n-2-i);
        
        if( (b-d-a <= sd-rc && sc-rd <= b-c-a) || (b+c-a <= sd-rc && sc-rd <= b+d-a) ){
            std::cout << "YES" << std::endl;
            return 0;
        }
    }
    std::cout << "NO" << std::endl;
}


Measured memory_bytes: 256
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author toshibablack
 */

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstring>
#include <fstream>
#include <functional>
#include <iostream>
#include <iomanip>
#include <iterator>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

#define ll long long int
#define FOR(i, a, b) for(int i=(a);i<=(b);++i)
#define REP(i, n) for(int i=0;i<n;++i)
#define FOREACH(x, a) for(auto& (x) : (a))
#define ALL(a) (a).begin(),(a).end()
#define OUT(x) out << (x) << endl;
#define M0(x) memset(x,0,sizeof(x))
#define MINF(x) memset(x,0x3f,sizeof(x))
#define MMINUS(a) memset(a,0xff,sizeof(a))
#define ten(n) ((int)1e##n)

const int INF = 0x3f3f3f3f;
const int MOD = 1e9+7;
const ll LINF = 1e18;
const double EPS = 1.0/LINF;
const char ENDL = '\n'; // for JetBrains IDE only supports yen

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

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

int gcd(int a,int b){return b?gcd(b,a%b):a;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

using namespace std;

class CSwitches {
public:
    vector<int> sw[11];
    int p[11];
    int N, M;

    void solve(std::istream& in, std::ostream& out) {
        in >> N >> M;
        FOR(i, 1, M) {
            int k; in >> k;
            FOR(j, 1, k) {
                int l; in >> l;
                sw[i].push_back(l);
            }
        }
        FOR(i, 1, M) {
            in >> p[i];
        }

        int ans = 0;

        FOR(bit, 0, pow(2, N) - 1) {
            bool ok = true;
            FOR(l, 1, M) {
                int pika = 0;
                FOREACH(s, sw[l]) {
                    if (bit & (1 << (s-1))) pika++;
                }
                if (pika % 2 != p[l]) {
                    ok = false; break;
                }
            }
            if (ok) ans++;
            ok = true;
        }

        OUT(ans);
    }
};


int main() {
    CSwitches solver;
    std::istream& in(std::cin);
    std::ostream& out(std::cout);
    solver.solve(in, out);
    return 0;
}


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

int main(){
  int n; cin >> n;
  int cnt = 0, ans = 0;
  for(int i = 1; i <= n; i += 2){
    cnt = 0;
    for(int j = 1; j <= i; j++){
      if(i % j == 0){
        cnt++;
      }
    }
    if(cnt == 8){
      ans++;
    }
  }
  cout << ans << endl;
}
      
  

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() {
    int n, l;
    cin >> n >> l;
    int answer = n * (n - 1) / 2 + n * l;
    if (l > 0) {
        answer -= l;
    } else if (l + n <= 0) {
        answer -= l + n - 1;
    }
    cout << answer << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define pf push_front

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

#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int main()
{ int A,B,C;
 cin >> A >> B >> C;
 int d;
 d = B/A;
 
 if (d > C) {
   cout << C << endl;
 }else{
   cout << d << endl;
 }
    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<algorithm>
#include<iostream>

using namespace std;

struct Vec{
	int ind;
	int val;
};

bool valDesc( const Vec& left, const Vec& right ) {
    return left.val == right.val  ? left.val> right.val: left.val > right.val;
}

bool valAsc( const Vec& left, const Vec& right ) {
    return left.val == right.val  ? left.val <  right.val: left.val < right.val;
}
int main(void){
	int a,b,c,x,y,z,ans=0;

	
	
	cin >> a >> b >> c;
	x = abs(a - b);
	y = abs(b - c);
	z = abs(c - a);
	if(x > y){
		ans += y;
		if(x > z) ans += z;
		else ans += x;
	}else{
		ans += x;
		if(y > z) ans+= z;
		else ans += y;
	}
	printf("%d\n",ans);
	fflush(stdout);

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
typedef long long int ll;

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	string s; cin >> s;
    int n=s.size();
    for(int i=0;i<n;i++){
        if(s[i]=='?')s[i]='D';
    }
    cout << s << endl;
}

Measured memory_bytes: 3740
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <queue>
#include <list>
#include <cmath>
#include <stack>
#include <deque>
#include <iomanip>

using namespace std;
typedef long long ll;
using Pll = pair<ll,ll>;

const ll INF = 1LL<<60;
const ll MOD = 1000000007;

//cout << fixed << setprecision(10);

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

    vector<vector<ll>> A(N,vector<ll>(N));

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

    vector<ll> idx(N);

    set<ll> finishied;
    set<Pll> se;
    ll ans=0;
    /*
    while(finishied.size()<N){
        bool change=false;
        for(int i=0;i<N;i++){
            if(idx[i]==N-1) {
                finishied.insert(i);
                continue;
            }
            if(se.count(Pll(A[i][idx[i]],i+1))==1){
                change=true;
                se.erase(Pll(A[i][idx[i]],i+1));
                idx[A[i][idx[i]]]++;
                idx[i]++;
            }
            else se.insert(Pll(i+1,A[i][idx[i]]));
        }
        if(change==false){
            cout << finishied.size() << endl;
            if(finishied.size()==N){
               break; 
            }
            else{
                cout << -1 << endl;
                return 0;
            }
        }
        ans++;
    }
    */

    multiset<Pll> multse;
    for(ll i=0;i<N;i++){
        ll first=min(i+1,A[i][0]);
        ll second = max(i+1,A[i][0]);
        se.insert(Pll(first,second));
        multse.insert(Pll(first,second));
    }  

    vector<ll> Ps;

    for(auto e: se){
        ll f = e.first;
        ll s = e.second;
        if(multse.count(Pll(f,s))==2){
            Ps.push_back(f-1);
            Ps.push_back(s-1);
            idx[f-1]++;
            idx[s-1]++;
        }
    }
    if(Ps.size()==0){
        cout << -1 << endl;
        return 0;
    }

    ans=1;

    while(1){
        vector<ll> tp;
        for(auto e : Ps){
            ll first=min(e+1,A[e][idx[e]]);
            ll second = max(e+1,A[e][idx[e]]);

            

            if(se.count(Pll(first,second))==1){
                idx[first-1]++;
                idx[second-1]++;
                
                if(idx[first-1]!=N-1) {
                    tp.push_back(first-1);
                }
                else finishied.insert(first-1);

                if(idx[second-1]!=N-1){
                    tp.push_back(second-1);
                }
                else finishied.insert(second-1);
            }
            else se.insert(Pll(first,second));
        }
        if(tp.size()==0){
            if(finishied.size()!=N){
                cout << -1 << endl;
                return 0;
            }
            else{
                ans++;
                break;
            }
        }
        Ps = tp;
        ans++;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 39552
import sys

def resolve(in_):
    dp0 = [1 << 60] * 1000100
    dp1 = [1 << 60] * 1000100
    zero = ord(b'0')
    dp0[0] = 0
    dp1[0] = 2

    for i, v in enumerate(in_.read().rstrip()):
        v -= zero

        # ちょうど支払う。おつりなし。
        dp0[i + 1] = min(dp0[i] + v, dp1[i] + v)

        # 前の桁の支払い枚数に 1 を加えてお釣りを払うのと、
        # 前の桁で多く払ってあるのでお釣りの払い出しの継続の二通り
        dp1[i + 1] = min(dp0[i] + 1 + 10 - v, dp1[i] + 9 - v)
    else:
        i += 1


    return min(dp0[i], dp1[i])


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()


Measured memory_bytes: 88672
//
//  atcoder.cpp
//
//
///
#include <bits/stdc++.h>
#include <boost/optional.hpp>
#include <boost/range/irange.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/bimap/bimap.hpp>
#include <boost/bimap/multiset_of.hpp>
#include <boost/multi_array.hpp>
#include <boost/math/common_factor.hpp>
#include <boost/algorithm/string.hpp>

#define REP(i, N) for(int i=0; i<(N); i++)
#define REC(f, ...) (void)0; const auto f = [&](const auto f, __VA_ARGS__)
using namespace std;
using namespace boost::math;

using ll = long long;
namespace bst = boost;
template<typename T> class in {
    T value;
public:
    in() { cin >> value; }
    operator const T&() const { return value; }
    operator T&() { return value; }
    in& operator=(T source) { value = source; return *this; }
};
template<> class in<string> : public string {
public:
    in() { cin >> *this; }
};
template<class T> class inseq : public T {
public:
    template<typename... Arg> inseq(Arg... arg) : T(forward<Arg>(arg)...) { for (auto&& i : *this) cin >> i; }
};
template<class T> using invec = inseq<vector<T>>;

auto solve() {
  set<int> A;
  
  REP (i,3) {
    int a;
    cin >> a;
    A.insert(a);
  }

  return (A.size() == 2 ? "Yes" : "No");
}

template<typename T> void plot(const T& func) { cout << func() << endl; }
template<> void plot<void()>(void(&func)()) { func(); }
template<> void plot<double()>(double(&func)()) { cout << setprecision(9) << func() << endl; }

int main() {
  plot(solve);

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
int main(void) {
  std::string s, t;
  std::cin >> s >> t;
  bool f = false;
  for (auto i = s.begin(); i != s.end(); i++) {
    char x = s.back();
    s.pop_back();
    s.insert(s.begin(), x);
    if (s == t) {
      f = true;
      break;
    }
  }
  if (f)
    std::cout << "Yes";
  else
    std::cout << "No";
  std::cout << std::endl;
  return 0;
}


Measured memory_bytes: 760
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include <numeric>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define INF 999999999

using namespace std;


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





ll gcd(ll x, ll y) {
	ll m = max(x, y), n = min(x, y);
	if (m%n == 0)return n;
	else return gcd(m%n, n);
}

int main() {
	ll X, Y;
	cin >> X >> Y;
	ll cnt = 0;
	while (X <= Y) {
		X = X * 2;
		cnt++;
	}
	cout << cnt << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int k = sc.nextInt();
		int n = sc.nextInt();
		int[] a_n = new int[n];

		for (int i = 0; i < n; i++) {
			a_n[i] = sc.nextInt();
		}

		sc.close();

		int maxDistance = 0;
		int tmp = 0;
		for (int i = 0; i < n - 1; i++) {
			tmp = a_n[i + 1] - a_n[i];
			maxDistance = Math.max(tmp, maxDistance);
		}

		maxDistance = Math.max(maxDistance, (k - a_n[n - 1] + a_n[0]));

		System.out.println(k - maxDistance);
	}
}


Measured memory_bytes: 60500
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin>>n;
	int sum=n%10;
	if(sum==3){
		cout<<"bon"<<endl;
	}else if(sum==0||sum==1||sum==6||sum==8){
		cout<<"pon"<<endl;
	}else{
		cout<<"hon"<<endl;
	}
	return 0;
}
//0 1 6 8

Measured memory_bytes: 3592