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

#define all(x) (x).begin(), (x).end()
#define sz(x) static_cast<int>((x).size())

using LL = long long;
template<class T, size_t D>
struct vec : vector<vec<T, D - 1>> {
  template<class... Args>
  vec(size_t n = 0, Args... args)
    : vector<vec<T, D - 1>>(n, vec<T, D - 1>(args...)) {}
};
template<class T>
struct vec<T, 1> : vector<T> {
  template<class... Args>
  vec(Args... args)
    : vector<T>(args...) {}
};

template<class T>
inline bool asMn(T& a, const T& b) { return a > b ? a = b, true : false; }
template<class T>
inline bool asMx(T& a, const T& b) { return a < b ? a = b, true : false; }
inline int nex(int i, int n) { return i == n - 1 ? 0 : i + 1; }
inline int pre(int i, int n) { return !i ? n - 1 : i - 1; }

mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());

template<class T>
bool updBasis(vec<T, 1>& basis, T a) {
  for (auto &i : basis) if (a >> __lg(i) & 1) a ^= i;
  if (!a) return false;
  for (auto &i : basis) if (i >> __lg(a) & 1) i ^= a;
  basis.emplace_back(a);
  return true;
}
template<class T>
bool check(const vec<T, 1>& basis, T a) {
  for (auto &i : basis) if (a >> __lg(i) & 1) a ^= i;
  return !a;
}

void main2() {
  int n; cin >> n;
  vec<LL, 1> a(n);
  for (auto& i : a) {
    cin >> i;
  }
  string s; cin >> s;

  vec<LL, 1> basis;
  for (int i = n - 1; ~i; --i) {
    if (s[i] == '0') {
      updBasis(basis, a[i]);
    } else {
      if (!check(basis, a[i])) {
        cout << "1\n";
        return ;
      }
    }
  }

  cout << "0\n";
}

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

  int nTest; cin >> nTest;
  while (nTest--) {
    main2();
  }

  return 0;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll ; 
typedef long double ld ;
typedef pair<ll , ll> pll ;

const ll N = 2e5 + 30 , Mod = 1e9 + 7 ;
const ll SQ = 330 ;

ll cnt[N] ;
int main () {
    ios::sync_with_stdio(0), cin.tie(0) ;
    ll n ;
    cin >> n ;
    vector<ll> v ;
    for (int i = 0 ; i < n ;i  ++) {
    	ll x ;
    	cin >> x ;
    	v.pb(x) ;
    	cnt[x] ++ ;
	}
	sort(all(v)) ;
	if (v.back() - v[0] > 1) return cout << "No" , 0 ;
	if (v.back() == v[0]) {
		if (v[0] == n - 1 || 2 * v[0] <= n) cout << "Yes" ;
		else cout << "No" ;
		exit(0) ;
	}
	ll x = cnt[v[0]] , y = cnt[v.back()] ;
    if (v.back() >= x + 1 && v.back() <= x + (y / 2) ) cout << "Yes" ;
    else cout << "No" ;
    return (0) ;
}

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

#define rep(i, n) for(int i = 0; i<(n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
using ll = long long;

const int mod = 1000000007;

int main() {
    ll N, D;
    cin >> N >> D;
    int ans = 0;
    ll X, Y;
    rep(_, N) {
        cin >> X >> Y;
        if (X * X + Y * Y <= D * D) ans++;
    }

    cout << ans << endl;
}


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

using namespace std;

long long niz[2100];

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

    long long n,A,B;
    cin>>n>>A>>B;
    for(int i=1;i<=n;i++)
        cin>>niz[i];
    if(n>1)cout<<max(abs(B-niz[n]),abs(niz[n]-niz[n-1]));
    else cout<<abs(B-niz[n]);

    return 0;
}



Measured memory_bytes: 256
import java.util.*;
public class Main{
public static void main(String[]args){
Scanner sc=new Scanner(System.in);
  int n=sc.nextInt();
  int m=sc.nextInt();
  int a=1;
  for(int i=0;i<n;i++){
  a=(a<m)?a*2:a+m;
  }
  System.out.println(a);
}
}

Measured memory_bytes: 22736
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i < (n); ++i)
using namespace std;
typedef long long ll;
const ll INF = 1LL << 60;


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

    ll n;
    cin >> n;
    vector<ll> a(n);
    vector<ll> bucket(n+2, 0);
    rep(i, n) {
        ll num;
        cin >> num;
        a[i] = num;
        ++bucket[num];
    }
 
    ll sum = 0;
    rep(i, n+2){
        if(bucket[i]<2) continue;
        else sum += bucket[i] * (bucket[i] - 1) / 2;
    }


    rep(i, n){
        if(bucket[a[i]] < 2) cout << sum << endl;
        else {
            ll tmp = bucket[a[i]];
            ll res = sum - (tmp*(tmp-1LL)/2LL);
            --tmp;
            cout << res + tmp*(tmp-1LL)/2LL << endl;
        }
    }

    return 0;
}

Measured memory_bytes: 5760
t=int(input())
import heapq
for _ in range(t):
    n=int(input())
    L=[];R=[]
    ans=0
    for _ in range(n):
        ki,li,ri = map(int, input().split())
        dif=li-ri
        if dif>=0:
            L.append((ki-1,dif))
            ans+=ri
        else:
            R.append((n-ki-1,-dif))
            ans+=li
    L.sort();R.sort()
    hL=[]
    hR=[]
    for i in range(len(L)):
        if L[i][0]>=len(hL):
            heapq.heappush(hL,L[i][1])
        elif L[i][0]==len(hL)-1:
            heapq.heappushpop(hL,L[i][1])
    for i in range(len(R)):
        if R[i][0]>=len(hR):
            heapq.heappush(hR,R[i][1])
        elif R[i][0]==len(hR)-1:
            heapq.heappushpop(hR,R[i][1])
    print(ans+sum(hL)+sum(hR))        
    
    

Measured memory_bytes: 36076
#include <assert.h>
#include <limits.h>
#include <cmath>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <complex>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using ll = long long;
using P = std::pair<ll, ll>;

#define rep(i, a, b) for (ll(i) = (a); i < (b); i++)
#define all(i) i.begin(), i.end()
#define debug(i) std::cout << i << "\n"

//const ll MOD = 998244353;
const ll MOD = 1e9+7;

//非再帰累乗(mod付き)
ll pow_mod(ll a, ll b, ll mod) {
  if (a % mod == 0) {
    return 0;
  }

  ll x = 1;

  while (b > 0) {
    if (b & 1) {
      x = (x * a) % mod;
    }
    a = (a * a) % mod;
    b >>= 1;
  }
  return x;
}
 
int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);
  //問題文中の添え字が0-indexか1-indexか確認!

  ll n,m;
  std::cin>>n>>m;

  std::vector<ll> facto(n+35);
  facto[0]=1;
  rep(i,1,n+35)facto[i]=(facto[i-1]*i)%MOD;
  ll ans=1,fh=m;
  for(ll i=2;i*i<=m;i++){
    if(m%i==0){
      ll temp=0;
      while(fh%i==0){
        temp++;
        fh/=i;
      }
      ans=(ans*facto[n-1+temp])%MOD;
      ans=(ans*pow_mod(facto[n-1],MOD-2,MOD))%MOD;
      ans=(ans*pow_mod(facto[temp],MOD-2,MOD))%MOD;
    }
  }

  if(fh!=1)ans=(ans*n)%MOD;

  std::cout<<ans;
  return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>
#define mod 1000000007

int main(void){
  int N,M;
  scanf("%d%d",&N,&M);

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

  long long dp[N+1];
  for (int i = 0; i < N+1; i++) {
    dp[i] = 0;
  }
  dp[0] = 1;

  for (int i = 0; i <= N; i++) {
    if(i < N && flag[i+1] == 0) dp[i+1] += dp[i] , dp[i+1] %= mod;
    if(i < N-1 && flag[i+2] == 0) dp[i+2] += dp[i] , dp[i+2] %= mod;
  }

  /* printf("\n"); */
  /* for (int i = 0; i < N+1; i++) { */
  /*   printf("%lld\n",dp[i]); */
  /* } */

  printf("%lld\n",dp[N]);

  return 0;
}

Measured memory_bytes: 1280
"use strict";
    
const main = arg => {
    const H = arg.split("\n")[0].split(" ")[0];
    const W = arg.split("\n")[0].split(" ")[1];
    const h = arg.split("\n")[1].split(" ")[0];
    const w = arg.split("\n")[1].split(" ")[1];
    
    console.log((H*W) - (h*W) - ((w*H)-(h*w)));
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 21064
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <deque>
#include <map>
#include <set>
#include <complex>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <chrono>

#define ft first
#define sc second
#define pb push_back
#define len(v) (int)v.size()
#define int ll

using namespace std;
typedef long long ll;
typedef long double ld;


signed main() {
	#ifdef PC
		freopen("in.txt", "r", stdin);
		freopen("out.txt", "w", stdout);
	#endif	


	int n;
	cin >> n;
	vector<int> p(n);
	for (int i = 0; i < n; i++) {
		cin >> p[i];
		p[i]--;
	}
	vector<int> a(n);
	a[0] = 30000;
	for (int i = 1; i < n; i++) {
		a[i] = a[i - 1] + 30000;
	}	
	auto b = a;
	reverse(b.begin(), b.end());

	for (int i = 0; i < n; i++) {
		a[p[i]] += i;
	}
	for (auto x : a)
		cout << x << " ";
	cout << endl;
	for (auto x : b) 
		cout << x << " ";
	cout << endl;
	return 0;
}

Measured memory_bytes: 1152
class Dice:
    def __init__(self, nums):
        self.top    = nums[0]
        self.front  = nums[1]
        self.right  = nums[2]
        self.left   = nums[3]
        self.back   = nums[4]
        self.bottom = nums[5]

    def toN(self):
        tmp = self.top
        self.top = self.front
        self.front = self.bottom
        self.bottom = self.back
        self.back = tmp

    def toS(self):
        tmp = self.top
        self.top = self.back
        self.back = self.bottom
        self.bottom = self.front
        self.front = tmp

    def toE(self):
        tmp = self.top
        self.top = self.left
        self.left = self.bottom
        self.bottom = self.right
        self.right = tmp

    def toW(self):
        tmp = self.top
        self.top = self.right
        self.right = self.bottom
        self.bottom = self.left
        self.left = tmp

    def moveTo(self, ds):
        for d in ds:
            if   d == 'N':
                self.toN()
            if d == 'S':
                self.toS()
            if d == 'E':
                self.toE()
            if d == 'W':
                self.toW()

    def getTop(self):
        return self.top

    def getBottom(self):
        return self.bottom

    def getFront(self):
        return self.front

    def getBack(self):
        return self.back

    def getLeft(self):
        return self.left

    def getRight(self):
        return self.right

    def __eq__(self, other):
        if self.top != other.top:
            return False
        if self.bottom != other.bottom:
            return False
        if self.front != other.front:
            return False
        if self.back != other.back:
            return False
        if self.left != other.left:
            return False
        if self.right != other.right:
            return False

        return True

def moveTo(dice, top, front):
    if dice.getFront() != front:
        if   dice.getTop()    == front:
            dice.moveTo("S")
        elif dice.getBottom() == front:
            dice.moveTo("N")
        elif dice.getBack()   == front:
            dice.moveTo("NN")
        elif dice.getLeft()   == front:
            dice.moveTo("ES")
        elif dice.getRight()  == front:
            dice.moveTo("WS")

    if dice.getTop() != top:
        if   dice.getBottom() == top:
            dice.moveTo("EE")
        elif dice.getLeft()   == top:
            dice.moveTo("E")
        elif dice.getRight()  == top:
            dice.moveTo("W")

    return dice

def equalDice(dice1, dice2):
    dice2 = moveTo(dice2, dice1.getTop(), dice1.getFront())
    return dice1 == dice2

def main():
    n = int(input())
    dice1 = Dice(input().split())

    ans = "Yes"
    for _ in range(n-1):
        dice2 = Dice(input().split())

        if equalDice(dice1, dice2):
            ans = "No"
            break

    print(ans)

if __name__ == '__main__':
    main()



Measured memory_bytes: 5620
#include "bits/stdc++.h"
using namespace std;
#define REP(i, n) for(ll i = 0;i < n;i++)
#define ll long long
#define MOD 1000000007
using vi = vector<ll>; // intの1次元の型に vi という別名をつける
using vvi = vector<vi>; // intの2次元の型に vvi という別名をつける

ll n,k,x,y;

//Bitと転倒数
class Bit
{
  public:
  ll size;
  vector<ll> data;
  Bit(ll num)
  {
    data.resize(num+1);
    REP(i,num+1)
      data[i]=0;
    size=num;
  }
  //(1-i)までの合計を返す
  ll Sum(ll i){
    ll s = 0;
    while (i > 0){
        s += data[i];
        i -= i & (-i);
    }
    return s;
  }
  //Add
  void Add(ll i,ll x){
    while (i <= size){
      data[i] += x;
      i += i & (-i);
    }
  }
};




int main(){
  ll ans=0;
  cin >> n;

  vi a(n);
  Bit bit(262144);

  REP(i,n){
    cin>>a[i];
    bit.Add(a[i],1);
    if (bit.Sum(a[i])==1) ans++;
  }




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

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

using namespace std;

int main()
{
    map<string, int> mp;

    mp["SUN"] = 7;
    mp["MON"] = 6;
    mp["TUE"] = 5;
    mp["WED"] = 4;
    mp["THU"] = 3;
    mp["FRI"] = 2;
    mp["SAT"] = 1;

    string S;
    cin >> S;

    cout << mp[S] << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
using Graph = vector<vector<int>>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const long long INF = 1LL << 60;
//入力
int n;
long long h[100010];

//DPテーブル
long long dp[100010];

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

  for(int j=0;j<100010;j++){
    dp[j]=INF;
  }
  dp[0]=0;

  for (int i=1; i<n;i++){
    chmin(dp[i],dp[i-1]+abs(h[i]-h[i-1]));
    if (i>1){
      chmin(dp[i],dp[i-2]+abs(h[i]-h[i-2]));
    }
  }

  cout << dp[n-1] << endl;
  
}


Measured memory_bytes: 1792
from bisect import bisect_left
n = int(input())
a = list(map(int, input().split()))
a.sort()
b = [abs(i) for i in a]
b.sort()

i = bisect_left(a, 0)
if i % 2==0:
    print(sum(b))
else:
    print(sum(b) - 2*b[0])


Measured memory_bytes: 15140
#include<iostream>
#include<algorithm>
#include<vector>
using lint=int64_t;
using namespace std;

void z_algo(vector<int>& ret,const string& str)
{
	const int size=(int)str.size();
	ret.resize(size,0);
	
	int L=0;
	for(int i=1;i<size;i++)
	{
		int diff=i-L;
		if(i+ret[diff]<L+ret[L])
			ret[i]=ret[diff];
		else
		{
			int k=max(0,ret[L]-diff);
			while(i+k<size && str[k]==str[i+k])k++;
			ret[i]=k;
			L=i;
		}
	}
	return;
}

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

	int ans=0;
	for(int i=0;i<N;i++)
	{
		vector<int> lcp;
		z_algo(lcp,S.substr(i));

		int tans=0;
		for(int i=0;i<lcp.size();i++)
			tans=max(tans,min(i,lcp[i]));
		ans=max(ans,tans);
	}

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


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    int64_t k;
    cin >> n >> k;
    vector<int> a(n);
    for(int i=0; i<n; i++){
        int p;
        cin >> p;
        a.at(i) = p-1;
    }
    int town=0;
    set<int> visited;
    visited.insert(0);
    while(1){
        town = a.at(town);
        if(visited.count(town)){
            break;
        }
        visited.insert(town);
    }
    int roop_step=0;
    int roop_start = town;
    while(1){
        town = a.at(town);
        roop_step++;
        if(town == roop_start) break;
    }
    
    int to_start=0;
    town = 0;
    while(1){
        town=a.at(town);
        to_start++;
        if(town == roop_start) break;
    }

    int same_step;
    if(to_start > k){
        same_step = k;
    }
    else{
        same_step = (k-to_start)%roop_step + to_start;
    }

    int goal=0;
    for(int i=0; i<same_step; i++){
        goal = a.at(goal);
    }

    cout << goal+1 << endl;
}


Measured memory_bytes: 13180
fn main() {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    let v = s
        .split_whitespace()
        .map(|w| w.parse().unwrap())
        .collect::<Vec<f64>>();
    let (a, b, x) = (v[0], v[1], v[2]);
    let square = x / a;
    if square < a * b / 2f64 {
        let deg1 = (b * b / 2f64 / square).atan() / std::f64::consts::PI * 180f64;
        println!("{}", deg1);
    } else {
        let deg2 = (2f64 / a / a * (a * b - square)).atan() / std::f64::consts::PI * 180f64;
        println!("{}", deg2);
    }
}


Measured memory_bytes: 4604
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <utility>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const int INF = 1<<30; 
const int MOD = 1e9 + 7;
const int dy[] = {1, 0, -1, 0};
const int dx[] = {0, 1, 0, -1};
int a, b, x;
int dfs(int sum)
{
    int res;
    if(sum >= x) res = 0;
    else
    {
        res = min(dfs(sum + 1000) + a, dfs(sum + 500) + b);
    }
    return res;
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> a >> b >> x;
    cout << dfs(0) << endl;
    return 0;
}




Measured memory_bytes: 3192
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] p = new int[N];
		for(int i=0; i<N; i++)
			p[i] = sc.nextInt();
		
		int cnt = 0;
		for(int i=0; i<N; i++) {
			if(p[i]!=i+1) {
				cnt++;
			}
		}
		System.out.println(cnt==0 || cnt==2 ? "YES" : "NO");
		sc.close();
	}
}


Measured memory_bytes: 21844
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 2e5 + 4;
const int mod = 2019;
const int REV = 202;// pow(10,-1) % 2019
int cnt[mod];
int bf[MAXN];
char s[MAXN];
int w33ha(){
    int t=1,l;
    scanf("%s",s+1);
    l = strlen(s+1);
    memset(bf,0,sizeof(bf));
    for(int i=l;i>=1;i--){
        bf[i] = (bf[i+1] + (t * (s[i] - '0')))%mod;
        cnt[bf[i]] ++;
        t = (t*10)%mod;
    }
    t = REV;
    ll ans=cnt[0];
    //for(int i=1;i<=l;i++) cout << bf[i] <<" ";cout << endl;
    for(int i=l;i>=1;i--){
        cnt[bf[i]] --;
        ans += cnt[bf[i]];
    }
    printf("%lld\n",ans);
    return 0;
}

int main(){
    w33ha();
    return 0;
}


Measured memory_bytes: 4812
a=1
b=0
c=-1
A,B,C,K=input().split()
A=int(A)
B=int(B)
C=int(C)
K=int(K)
test=0
if K>=A:
    a=a*A
    test=test+a
    K=K-A
elif K<=A:
    a=a*K
    test=test+a
    c=0
if K>=B:
    b=b*B
    test=test+b
    K=K-B
elif K<=B: 
    b=b*K
    test=test+b
    c=0
    
if K>=C:
    c=c*C
    test=test+c
    K=K-C
elif K<=C:
    c=c*K
    test=test+c
    
    
print(test)

Measured memory_bytes: 9132
////////////////////////////////////////////////////////////////////////
//ファイル名：ITP_1_6_B_Finding Missing Cards.c
//内容；入力されたカードから、不足しているカードを発見して出力する
//入力：持っているカードの枚数 n  
//出力：不足しているカードを出力
//制約：n ≤ 52
////////////////////////////////////////////////////////////////////////

#include <stdio.h>

#define MAX_SIZE 52


//メイン関数
int main(void)
{
    int n = 0;                          //カードの所持枚数
    int i, j;                           //for文用
    int value = 0;
    char design;
    char mark[4] = {'S','H','C','D'};  //S:スペード H:ハート C:クローバー D:ダイヤ
    static int card [4][13];

    //所持カード枚数の決定
    scanf("%d", &n);

    //制約の範囲外ならエラーメッセージを出力
    if(n > MAX_SIZE)
    {
        printf("Invalid Input\n");
        return 0;
    }

    //所持カードの入力
    for(i=0; i<n; i++)
    {
        scanf("%c", &design);
        scanf("%c %d", &design, &value);

        for(j=0; j<4; j++)
        {
            //所持カードを記憶
            if(mark[j] == design)
            {
                card[j][value-1] = 1; 
            }
        }
    }

    //不足カードを出力
    for(i=0; i<4; i++)
    {
        for(j=0; j<13; j++)
        {
            if(card[i][j] == 0)
            {
                printf("%c %d\n",mark[i],j+1);
            }
        }
    }

    return 0;
}


Measured memory_bytes: 2116
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int a,b,k,pos=0;
	cin>>a>>b>>k;
	for (int j=min(a,b);j>=1;j--)
	{
		if (a%j==0&&b%j==0)	 pos++;
		if (pos==k)
		{
			cout<<j<<endl;
			return 0;
		} 
	}
}

Measured memory_bytes: 384
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<iomanip>
#include<set>
#include<numeric>
#include<sstream>
#include<random>
#include<cassert>
#include<complex>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rrep(i, st, n) for (int i = st; i < n; ++i)
using pii = pair<int, int>;
const int inf = 1e9 + 7;
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int dx[] = {1, -1, 0, 0, -1, 1, 1, -1};
#define ceil(a, b) a / b + !!(a % b)
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)

int main() {
    int n, k; cin >> n >> k;
    string s; cin >> s;
    s[k - 1] = tolower(s[k - 1]);
    cout << s << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <bitset>
#include <string>
#include <map>
#include <queue>
#include <functional>
#include <assert.h>
using namespace std;
inline int pack(int p, int ps, int n) {
  return (p << n) | ps;
}
int main(int argc, char *argv[])
{
  for(;;) {
    int n;
    cin >> n;
    if(n==0) break;
    string sa, sb;
    getline(cin, sa);
    getline(cin, sa);
    getline(cin, sb);
    auto conv = [n](string &s) {
      int r = 0;
      for(int i = 0; i < n; i++) {
        r = (r<<1) + (s[i] == 'W' ? 1 : 0); 
      }
      return r;
    };
    const int a = conv(sa);
    const int b = conv(sb);
    //cout << "a = " << static_cast<std::bitset<8> >(a) << endl;
    //cout << "b = " << static_cast<std::bitset<8> >(b) << endl;
    // better DP: state = (head-pos, difference)
    vector<int> ds(n<<n, -1);
    function<int(int)> rec = [&rec,&b,&n,&ds](const int v){
      if(ds[v] >= 0) return ds[v];
      const int p = v >> n;
      const int s = v & ((1<<n) - 1);
      if(s == 0) return 0;
      int e = 10000000;
      for(int i = 0; i < n; i++) {
        if((s & (1<<i)) == 0) continue;
        for(int j = 0; j < n; j++) {
          if(i == j) continue;
          if((s & (1<<j)) == 0) continue;
          if((((b>>i) ^ (b>>j))&1) == 0) continue;
          const int c = abs(i - p) + abs(j - i);
          const int u = pack(j, s ^ (1<<i) ^ (1<<j), n); // swap
          e = min(e, c + rec(u));
        }
      }
      ds[v] = e;
      return e;
    };
    int e = 10000000;
    for(int i = 0; i < n; i++) {
      e = min(e, rec(pack(i, a^b, n)));
    }
    cout << e << endl;
/*  // naive Dijkstra search: state = (head-pos, panels)
    vector<int> ds(n<<n, 100000000);
    priority_queue<pair<int,int>> que;
    for(int i = 0; i < n; i++) {
      int v = pack(i, a, n);
      ds[v] = 0;
      que.push(make_pair(-ds[v], v));
      
    }
    vector<bool> done(n, false);
    int rest = n;
    while(que.size() > 0) {
      auto dv = que.top(); que.pop();
      const int v = dv.second;
      const int d = -dv.first;
      const int p = v >> n;
      const int s = v & ((1<<n) - 1);
      //cout << "popped: " << static_cast<std::bitset<8> >(s) << " at " << p << " with cost " << d << endl;
      if(s == b) {
        if(!done[p]) {
          done[p] = true;
          rest--;
        }
        if(rest == 0) {
          int e = d;
          for(int i = 0; i < n; i++) {
            e = min(e, ds[pack(i, b, n)]);
          }
          cout << e << endl;
          break;
        }
      }
      // generate all possible transitions: marking i, and then j.
      for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
          if(i == j) continue;
          if((((s>>i) ^ (s>>j))&1) == 0) continue;
          const int c = abs(i - p) + abs(j - i);
          const int u = pack(j, s ^ (1<<i) ^ (1<<j), n); // swap
          if(ds[u] > d + c) {
            ds[u] = d + c;
            que.push(make_pair(-ds[u], u));
            //cout << " to " << i << " and " << j << " cost " << ds[u] << " for " << static_cast<std::bitset<8> >(u) << endl;
          }
        }
      }
    }
*/
  }
  return 0;
}

Measured memory_bytes: 7088
#include<iostream>
#include<vector>
using namespace std;
int a, b, c; vector<int>p, q;
int main() {
	while (true) {
		cin >> a >> b >> c; p.clear(); q.clear(); if (a == 0)break;
		if (c == 0) {
			if (b < 0 && a == 1)cout << a << " " << "0" << " " << "1" << " " << b << endl;
			else { cout << a << ' ' << b << ' ' << "1" << ' ' << "0" << endl; }
			goto E;
		}
		for (int i = -10000; i <= 10000; i++) {
			if (i == 0)continue;
			if (a%i == 0)p.push_back(i);
			if (c%i == 0)q.push_back(i);
		}
		for (int i = 0; i < p.size(); i++) {
			for (int j = 0; j < q.size(); j++) {
				int sum = p[i] * (c / q[j]) + (a / p[i])*q[j];
				if (p[i] < a / p[i] || p[i] < 0 || a / p[i] < 0)continue;
				if (p[i] == a / p[i] && q[j] < c / q[j])continue;
				if (sum == b) { cout << p[i] << ' ' << q[j] << ' ' << a / p[i] << ' ' << c / q[j] << endl; goto E; }
			}
		}
		cout << "Impossible" << endl; E:;
	}
	return 0;
}

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

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define start_routine() int begtime = clock();
#define end_routine() int endtime = clock(); cerr << endl << "Time elapsed: " << (endtime - begtime)*1000/CLOCKS_PER_SEC << " ms"; return 0
#define speed() cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(false)
// #define exit(a, b) return cout << a, b;

#define loop(i,a,b) for(ll i=a;i<b;i++)
#define all(v) v.begin(), v.end() 

#define print(stuff) cout << stuff << endl
#define len length
#define ret0 return 0
#define ret return 

#define ll long long
#define ld long double
#define fi first
#define endl '\n'
#define se second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound

#define vl vector<ll> 
#define sl set<ll>
#define pll pair<ll, ll>
#define mll map<ll, ll> 
#define pq priority_queue<ll>

// typedef tree<ll,null_type,less<ll>,rb_tree_tag,
// tree_order_statistics_node_update> indexed_set;

#define inf (long long int) 1e18
#define eps 0.000001
#define mod 1000000007
#define mod1 998244353
#define MAXN 10000

ll modexp(ll a, ll b, ll m){
    if (b==0)
        return 1;
    ll temp = modexp(a,b/2,m);
    temp = (temp*temp)%m;
    if (b&1)
        return (temp*(a%m))%m; // if b is odd a^b = a^(b/2)*a^(b/2)*a
    return temp;
}


string k;
ll d;
ll dp[10004][2][103];

ll f(ll i, ll b, ll rem){ // b=0 means that it has not yet become smaller.
    if(i>=MAXN){
        if(rem==0) return 1;
        else if(rem!=0) ret 0;
    }
    else if(dp[i][b][rem]!=-1){
        ret dp[i][b][rem];
    }
    else {
        ll ans = 0;
        if(b==0){
            ll dig_k = k[i]-'0';
            loop(j,0,dig_k){
                ll new_rem = (rem + (j)%d)%d;
                ans = (ans%mod + f(i+1, 1, new_rem)%mod)%mod;
            }
            ll neww_rem = (rem + (dig_k)%d)%d;
            ans = (ans%mod + f(i+1, 0, neww_rem)%mod)%mod;
        }
        else if(b==1){
            loop(j,0,10){
                ll new_rem = (rem + (j)%d)%d;
                ans = (ans%mod + f(i+1, 1, new_rem)%mod)%mod;
            }
        }
        ret dp[i][b][rem] = ans%mod;
    }
}

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

    cin>>k;
    cin>>d;
    string temp;
    loop(i,0,MAXN-k.len()){
        temp.pb('0');
    }
    loop(i,0,k.len()) temp.pb(k[i]);
    k=temp;
    loop(i,0,10004){
        loop(j,0,2){
            loop(k,0,103){
                dp[i][j][k]=-1;
            }
        }
    }
    ll op = (f(0, 0, 0)%mod - 1 + mod)%mod;
    print(op);

        
    
}



Measured memory_bytes: 19072
using System;
using System.Linq;//リストの使用
using System.Collections.Generic;
using System.Text;//テキストの高速出力に必要
class Program
{
	static void Main()
	{
		string s = Console.ReadLine();
    
		if(s[0] == 'S') Console.WriteLine("Cloudy");
    else if(s[0] == 'C') Console.WriteLine("Rainy");
    else Console.WriteLine("Sunny");
	}
}

Measured memory_bytes: 11092
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <iomanip>
int main()
{
    long N;
    std::vector<std::string> S;
    std::cin >> N;
    for(long i=0; i<N; i++){
        std::string Si;
        std::cin >> Si;
        S.push_back(Si);
    }
    long m=0,a=0,r=0,c=0,h=0;
    for(long i=0; i<N; i++){
        if(S[i][0]=='M'){
            m++;
        }
        if(S[i][0]=='A'){
            a++;
        }
        if(S[i][0]=='R'){
            r++;
        }
        if(S[i][0]=='C'){
            c++;
        }
        if(S[i][0]=='H'){
            h++;
        }
    }
    long march[5];
    march[0]=m;
    march[1]=a;
    march[2]=r;
    march[3]=c;
    march[4]=h;
    long count=0;
    for(long i=0; i<3;i++){
        for(long j=i+1; j<4; j++){
            for(long k=j+1; k<5; k++){
                count+=march[i]*march[j]*march[k];
            }
        }
    }
    std::cout << count << std::endl;
    return 0;
}

Measured memory_bytes: 6132
from sys import stdin
from itertools import accumulate
input = stdin.readline

MOD = 10**9+7
N, K = map(int,input().split())
*a, = map(int,input().split())

p = list(accumulate(a))

dp = [0] * (K+1)
dp[0] = 1
prefix = [0]+[1]*(K+1)
for i in range(N):
    new_dp = [0]*(K+1)
    for j in range(min(p[i],K)+1):
        new_dp[j] = prefix[j+1] - prefix[max(0,j-a[i])]
    dp = new_dp[:]
    prefix = [i % MOD for i in [0]+list(accumulate(dp))]

print(dp[K]%MOD)


Measured memory_bytes: 135880
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i = 0;i<((ll)(n));i++)
#define reg(i,a,b) for(ll i = ((ll)(a));i<=((ll)(b));i++)
#define irep(i,n) for(ll i = ((ll)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(ll i = ((ll)(b));i>=((ll)(a));i--)
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;

/*
奇数番と偶数番に分ける
奇数番の最頻出 != 偶数番の最頻出
	やる
奇数番の最頻出 == 偶数番の最頻出
	(1,2) or (2,1)
*/

ll n,ans=1e9;
map<ll,ll> m[2];
V<pair<ll,ll>> v[2];

int main(void){
	cin>>n;
	rep(i,n){
		ll b;
		cin>>b;
		m[i%2][b]++;
	}
	rep(i,2){
		for(auto itr=m[i].begin();itr!=m[i].end();++itr){
			v[i].push_back({-itr->second,itr->first});
		}
		sort(v[i].begin(),v[i].end());
	}
	if(v[0][0].second!=v[1][0].second){
		ans=n+v[0][0].first+v[1][0].first;
	}else{
		ans=min(ans,n+v[0][0].first);
		ans=min(ans,n+v[1][0].first);
		if(v[0].size()>1)ans=min(ans,n+v[0][1].first+v[1][0].first);
		if(v[1].size()>1)ans=min(ans,n+v[0][0].first+v[1][1].first);
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 8824
import math

def cal_ans(x):
  return math.floor(A*x/B) - A*math.floor(x/B)

A,B,N = map(int,input().split())

ans = 0

if A == 1 or B ==1:
  ans = 0
else:
  ans = cal_ans(min(N,B-1))

print(ans)

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

using namespace std;
int main(){
    // Your code here!
    int n;
    cin >> n;
    vector<int> cards(n);
    
    for (int i = 0; i < n; i++) {
        cin >> cards.at(i);
    }
    
    sort(cards.begin(), cards.end());
    reverse(cards.begin(), cards.end());
    int A = 0;
    int B = 0;
    
    for (int i = 0; i < n; i+=2) {
        A += cards.at(i);
    }
    
    for (int i = 1; i < n; i+=2) {
        B += cards.at(i);
    }
    
    if (B <= A) {
        cout << A - B << endl;
    }else {
        cout << B - A << endl;
    }
}

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;

pair<int,int> r[105],b[105];
bool used[105];

int main(){
  int n;
	cin >> n;
	rep(i,n){
		int x,y;
		cin >> x >> y;
		r[i] = make_pair(x,y);
	}
	rep(i,n){
		int x,y;
		cin >> x >> y;
		b[i] = make_pair(x,y);
	}
	sort(r,r+n); sort(b,b+n);
	int ans = 0;
	rep(i,n){
    int alternative=-1;
    int value=-1;
    rep(j,n){
      if(used[j])continue;
      if(r[j].first<b[i].first&&r[j].second<b[i].second){
        if(value<=r[j].second){
          alternative=j;
          value = r[j].second;
        }
      }
    }
    if(alternative==-1)continue;
    used[alternative]=1;
    ans++;
  }
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
N=int(input())
E=[[] for _ in range(N)]
for _ in range(N-1):
    a,b=map(lambda x:int(x)-1, input().split())
    E[a].append(b)
    E[b].append(a)
C=list(map(int, input().split()))

C.sort(reverse=True)

ans=[0]*(N)
stack=[0]
ans[0]=C[0]
k=1
while stack:
    n=stack.pop()
    for to in E[n]:
        if ans[to]!=0: continue
        ans[to]=C[k]
        k+=1
        stack.append(to)

print(sum(C[1:]))
print(' '.join(map(str,ans)))

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

// Type alias
using ll=long long;
using ld=double;

using pi=pair<int,int>;
using pll=pair<ll,ll>;
using pld=pair<ld,ld>;
using ti3=tuple<int, int, int>;

using vi=vector<int>;
using vll=vector<ll>;
using vld=vector<ld>;
using vpi=vector<pi>;
using vpll=vector<ll>;
using vpld=vector<ld>;
using vti3=vector<ti3>;

// Constants
const double EPS = 1e-9;
const int inf = numeric_limits<int>::max();

// Macro
#define rep(i,n) for(int i=0;i<int(n);++i)
#define rrep(i,n) for(int i=int(n-1);i>=0;--i)
#define REP(i,a,b) for(int i=int(a);i<int(b);++i)
#define RREP(i,a,b) for(int i=int(b-1);i>=int(a);--i)
#define SHOW(a) cout << #a << " = " << a << endl
#define ARR(a,n) for(int i=0;i<int(n);++i) cout << #a << "[" << i << "]" << " = " << a[i] << endl

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

// Funtcions
ll pow(ll base, ll i, ll mod){
  ll a = 1;
  while(i){
    if (i & 1) {
      a *= base;
      a %= mod;
    }
    base *= base;
    base %= mod;
    i >>= 1;
  }
  return a;
}
ll gcd(ll a, ll b){
  while(b){
    ll c = a % b;
    a = b;
    b = c;
  }
  return a;
}
ll lcm(ll a, ll b){
  return a / gcd(a, b) * b;
}


void solve(){
  int N;
  string S;
  cin >> N >> S;

  ll r = 0, g = 0, b = 0;
  rep(i, N){
    if(S[i] == 'R')
      r++;
    else if(S[i] == 'G')
      g++;
    else if(S[i] == 'B')
      b++;
  }

  ll ex = 0;
  REP(i, 0, N-2){
    REP(j, i+1, N-1){
      if(2*j-i < N && S[i] != S[j] && S[j] != S[2*j-i] && S[2*j-i] != S[i])
        ex++;
    }
  }

  cout << r * g * b - ex << endl;
}

int main(){
  // FastIO
  //ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  solve();
  return 0;
}

Measured memory_bytes: 3596
#include<iostream>
#include<cmath>
#define ll long long

using namespace std;

int n,k;
double num[200010];
double eps = 1e-6;

int can(double len)
{
	ll rul = 0;
	for(int i=0; i<n; i++)
	{
		ll t = num[i] / len;
		if(fabs(num[i] - t * len) > eps) t++;
		rul+=t-1;
		if(rul > k) return 0;
	}	
	return 1;
}

int main()
{
	cin>>n>>k;
	for(int i=0; i<n; i++) cin>>num[i];
	
	double l = 1e-9, r = 1e9, mid;
	
	while(l < r - eps)
	{
		mid = (l + r) / 2;
		if(can(mid)) r = mid;
		else l = mid;
	}
	printf("%lld",(ll)ceil(r));
	return 0;
}

Measured memory_bytes: 4788
import math, sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import lru_cache
from heapq import heapify, heappop, heappush
from itertools import accumulate, combinations, permutations
input = sys.stdin.readline
mod = 10**9 + 7
ns = lambda: input().strip()
ni = lambda: int(input().strip())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort(reverse=True)
    return divisors

n, m = nm()

for divisor in make_divisors(m):
    if divisor <= m / n:
        print(divisor)
        exit()


Measured memory_bytes: 3788
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  int n; cin >> n;
  V<long double> x(n), y(n);
  V<char> d(n);
  for (int i = 0; i < n; ++i) cin >> x[i] >> y[i] >> d[i];
  auto fn = [&](long double t) -> long double {
    long double x_min = 1e12, x_max = -1e12;
    long double y_min = 1e12, y_max = -1e12;
    for (int i = 0; i < n; ++i) {
      if (d[i] == 'R') {
        x_min = min(x_min, x[i] + t);
        x_max = max(x_max, x[i] + t);
      } else if (d[i] == 'L') {
        x_min = min(x_min, x[i] - t);
        x_max = max(x_max, x[i] - t);
      } else {
        x_min = min(x_min, x[i]);
        x_max = max(x_max, x[i]);
      }
      if (d[i] == 'U') {
        y_min = min(y_min, y[i] + t);
        y_max = max(y_max, y[i] + t);
      } else if (d[i] == 'D') {
        y_min = min(y_min, y[i] - t);
        y_max = max(y_max, y[i] - t);
      } else {
        y_min = min(y_min, y[i]);
        y_max = max(y_max, y[i]);
      }
    }
    return (x_max - x_min) * (y_max - y_min);
  };
  long double l = 0, r = 1e10;
  for (int _ = 0; _ < 200; ++_) {
    long double ml = (2 * l + r) / 3, mr = (l + 2 * r) / 3;
    if (fn(ml) < fn(mr)) r = mr;
    else l = ml;
  }
  cout << fixed << setprecision(15) << fn((l + r) / 2) << '\n';
}

Measured memory_bytes: 3456
#include<bits/stdc++.h>
#include<string.h>
using namespace std;
using ll = long long;
int main(){
	int ans, i;
	char chr;
	string n;
	cin >> n;
	ans = 0;
	for(i = 0; i < n.length(); i++){
		chr = n[i];
		ans += (int)chr - 48;
	}
	if (ans%9 == 0){
		cout << "Yes" << endl;
	}else{
		cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 3720
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repi(i, s, n) for (int i = (s); i < (n); i++)
#ifdef LOCAL
#define INPUT_FILE                              \
  ifstream in("atcoder-problems/abc125_d.txt"); \
  cin.rdbuf(in.rdbuf());
#define print_vec(v)                        \
  rep(l, v.size()) { cout << v[l] << " "; } \
  cout << endl;
#else
#define INPUT_FILE
#define print_vec(v)
#endif
#define CIN_OPTIMIZE \
  cin.tie(0);        \
  ios::sync_with_stdio(false);
typedef pair<int, int> P;
typedef long long ll;
typedef pair<ll, ll> pl;
const int INF = 100100100;
const ll LINF = 1e18 + 100;
const int MOD = 1e9 + 7;

int main() {
  INPUT_FILE CIN_OPTIMIZE;

  int N;
  cin >> N;

  vector<ll> c(N);
  int minus = 0;
  ll mi = LINF;
  ll ans = 0;
  rep(i, N) {
    cin >> c[i];
    minus += c[i] < 0;
    mi = min(mi, abs(c[i]));
    ans += abs(c[i]);
  }
  if (minus % 2 == 1) ans -= 2 * mi;

  cout << ans << endl;
}

Measured memory_bytes: 1024
import java.util.*;

public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

		while(true){
			int n = sc.nextInt();
			if(n == 0) break;

			ArrayList<Integer> t = new ArrayList<Integer>();
			for(int i=0;i<n;i++) t.add(sc.nextInt());

			int ans = Integer.MAX_VALUE;
			for(int i=1;i<t.size();i++){
				int top = 1;
				int bottom = i<t.size()-1 ? 1 : 0;

				for(int j=i-2;j>=0 && t.get(j) == t.get(j+1);j--,top++);
				for(int j=i+2;j<t.size() && t.get(j) == t.get(j-1);j++,bottom++);

				if(top == 3){
					ans = Math.min(ans,solve(n,t,i,t.get(i-1)));
				}
				if(i+1 < t.size() &&
					 (bottom == 3 && t.get(i-1) != t.get(i+1) ||
						top + bottom >= 3 && t.get(i-1) == t.get(i+1))){
					ans = Math.min(ans,solve(n,t,i,t.get(i+1)));
				}
			}

			System.out.println(ans == Integer.MAX_VALUE ? n : ans);
		}
	}

	private static int solve(int n,ArrayList<Integer> tt,int pos,int col){
		int res = n;
		ArrayList<Integer> t = new ArrayList<Integer>(tt);
		t.set(pos,col);

		while(pos < t.size() && t.get(pos) == col){
			t.remove(pos);
			res--;
		}
		while(--pos >= 0 && t.get(pos) == col){
			t.remove(pos);
			res--;
		}

		while(t.size() >= 4){
			if(pos < 0) break;

			int top = 0;
			int bottom = 0;

			for(int j=pos-1;j>=0 && t.get(j) == t.get(j+1);j--,top++);
			for(int j=pos+1;j<t.size() && t.get(j) == t.get(j-1);j++,bottom++);
			if(top + bottom + 1 < 4) break;

			col = t.get(pos);
			while(pos < t.size() && t.get(pos) == col){
				t.remove(pos);
				res--;
			}
			while(--pos >= 0 && t.get(pos) == col){
				t.remove(pos);
				res--;
			}
		}

		return res;
	}
}

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

#define N 100000


typedef struct {
  int t;
  char name[10];
} data;

data dequeue(void);
int min(int x,int y);
void enqueue(data A);

data Q[N];
int head=1;
int tail=0;
int n;



int main(void){
  int t2;
  int k,q,i;
  data D;

  scanf("%d %d",&n,&q);


  for(i = 1;i <= n;i++){
    scanf("%s %d",Q[i].name,&Q[i].t);
  }
  
  tail = n+1;


  while(head != tail){
    D = dequeue();
    k = min(D.t,q); //qまたは必要な時間 u.tだけ処理を行う
    D.t -= k; //残りの必要時間を計算
    t2 += k; //経過時間を加算
    if(D.t > 0){
      enqueue(D);
    } else {
      printf("%s %d\n",D.name,t2);
    }
  }

  return 0;
}





data dequeue(){
  data A = Q[head];
  head = (head + 1)%N;
  
  return A;
}

void enqueue(data A){
  Q[tail] = A;
  tail = (tail + 1)%N;
}


int min(int x,int y){
  if(x < y){
    return x;
  } else {
    return y;
  }
}




Measured memory_bytes: 3256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define pa(x,n) for(ll i=0;i<n;i++){cout<<(x[i])<<" \n"[i==n-1];};
#define pb push_back

using ll = long long;
using namespace std;
using pint = pair<int,int>;
using pll = pair<ll,ll>;
const int INFint = 1e9;
const ll INFll = 1e18;
ll MOD=1e9+7;

ll gcd(ll a, ll b) { return __gcd(a,b); } //最大公約数
ll lcm(ll a, ll b) { return a/gcd(a,b)*b; } //最大公倍数

// aのn乗をMODで割りながら計算する
ll modpow(ll a, ll n) {
  long long res = 1;
  while (n > 0) {
    if (n & 1) res = res * a % MOD;
    a = a * a % MOD;
    n >>= 1; // right shift
  }
  return res;
}

// MODを法としたaの逆元を計算する
ll modinv(ll a) {
  return modpow(a, MOD - 2);
}

int main(){
  string s;
  cin>>s;
  int N = int(s.size());
  string ans;
  for (int i(0);i<N;i++){
    //cout << ans << endl;
    if (s[i] == 'B'){
      if (int(ans.size()) != 0){
        ans = ans.substr(0,int(ans.size())-1);
      }
    }else{
      ans += s[i];
    }
  }
  cout << ans << endl;
  return 0;
}



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

int main() {
	int X; (1<=X<=100);
	int Y; (1<=Y<=100);
	cin >> X;
	cin >> Y;
	if(Y%2==1){
		cout<< "No" << endl;}
    else{
    	if (Y<2*X,Y>4*X){cout << "No" << endl;}
    		else if(Y<=4*X,Y>=2*X){cout << "Yes" << endl;}
    	else{ cout << "No" << endl;}
    }
	return 0;
}

Measured memory_bytes: 3604
#include<iostream>
#include <stdio.h>
#include <stdlib.h>
#include <stdlib.h>
#include<algorithm>
using namespace std;
int main() {
	int x, a, b;
	cin >> x >> a >> b;
	int A = x - a;
	if (A < 0) {
		A = A * -1;
	}
	int B = x - b;
	if (B < 0) {
		B = B * -1;
	}
	int ans = min(A, B);
	if (ans == A) {
		cout << "A" << endl;
	}
	else {
		cout << "B" << endl;
	}
	return 0;

}

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

int main(){
  int n,a,b,c;
  cin >> n >> a >> b >> c;

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

  int ret = -1;
  int cur = 0;
  while(1){
    int ri = 0;
    int ai = 0,bi = 0,ci = 0;
    int tmp = cur;
    int zcnt = 0;
    for(int i = 0;i < n;i++){
      if(tmp%4 == 0)zcnt++;
      if(tmp%4 == 1)ai += l[i];
      if(tmp%4 == 2)bi += l[i];
      if(tmp%4 == 3)ci += l[i];
      tmp /= 4;
    }
    //cout << ai << " " << bi << " " << ci << endl;
    if(tmp > 0)break;
    if(ai != 0 && bi != 0 && ci != 0){
      ri = abs(a - ai) + abs(b - bi) + abs(c - ci) + (n - zcnt - 3)*10;
      if(ret == -1 || ret > ri)ret = ri;
    }
    cur++;
  }

  cout << ret << endl;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main()
{
    int A,B,C;
    cin>>A>>B>>C;
    if(A!=B && B!=C && A!=C)
    cout<<"No";
    else if(A==B && B==C)
    cout<<"No";
    else
    cout<<"Yes";
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
long long gcd(long x,long y){
    if(y==0)return x;

    return gcd(y,x%y);
}
long long lcm(long x,long y){
    return x*y/gcd(x,y);
}

int ctoi(char c) {
	if (c >= '0' && c <= '9') {
		return c - '0';
	}
	return 0;
}

int main()
{
    int N,A[100010]={},o=0,e4=0,f=0;
    cin>>N;

    for(int i=0;i<N;i++){
        cin>>A[i];
        if(A[i]%2==1)o++;
        if(A[i]%2==0&&A[i]%4!=0)f=1;
        if(A[i]%4==0)e4++;

    }

    o+=f;

    if(e4+1>=o){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }

    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i, n, m) for (int i = (int)(n); i < (int)(m); i++)
#define repr(i, n, m) for (int i = (int)(n) - 1; i >= (int)(m); i--)
using namespace std;
using ll = int64_t;
const int MOD = 1000000007; // 10^9+7

struct mod_int {
    ll val;
    constexpr mod_int(ll v = 0) noexcept : val(v % MOD) {
        if (val < 0) val += MOD;
    }
    constexpr int getmod() { return MOD; }
    constexpr mod_int operator - () const noexcept {
        return val ? MOD - val : 0;
    }
    constexpr mod_int operator + (const mod_int& r) const noexcept { return mod_int(*this) += r; }
    constexpr mod_int operator - (const mod_int& r) const noexcept { return mod_int(*this) -= r; }
    constexpr mod_int operator * (const mod_int& r) const noexcept { return mod_int(*this) *= r; }
    constexpr mod_int operator / (const mod_int& r) const noexcept { return mod_int(*this) /= r; }
    constexpr mod_int& operator += (const mod_int& r) noexcept {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr mod_int& operator -= (const mod_int& r) noexcept {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr mod_int& operator *= (const mod_int& r) noexcept {
        val = val * r.val % MOD;
        return *this;
    }
    constexpr mod_int& operator /= (const mod_int& r) noexcept {
        ll a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            ll t = a / b;
            ll tmp = 0;
            // tmp = a; a = b; b = tmp; としてるのは、
            // swap()がconstexprじゃなくて使えないから
            a -= t * b; tmp = a; a = b; b = tmp;
            u -= t * v; tmp = u; u = v; v = tmp;
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr bool operator == (const mod_int& r) const noexcept {
        return this->val == r.val;
    }
    constexpr bool operator != (const mod_int& r) const noexcept {
        return this->val != r.val;
    }
    friend ostream& operator << (ostream &os, const mod_int& x) noexcept {
        return os << x.val;
    }
    friend constexpr mod_int modpow(const mod_int &a, ll n) noexcept {
        if (n == 0) return 1;
        auto t = modpow(a, n / 2);
        t = t * t;
        if (n & 1) t = t * a;
        return t;
    }
};

using mint = mod_int;

int main() {
    ll n, k;
    cin >> n >> k;

    mint ans = 0;
    for (ll i = k; i <= n + 1; i++)
    {
        ll lower = (i - 1) * i / 2;
        ll upper = n * (n + 1) / 2 - (n - i) * (n - i + 1) / 2;
        ll tmp = upper - lower + 1;
        ans += mint(tmp);
    }
    cout << ans << endl;
}


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

struct Card{ char suit, value; };

void bubble(struct Card A[], int N) {
  for(int i=0; i<N; i++) {
    for(int j=N-1; j>=i; j--) {
      if(A[j].value < A[j-1].value) {
        Card t = A[j]; A[j] = A[j-1]; A[j-1] = t;
      }
    }
  }
}

void selection(struct Card A[], int N) {
  for(int i=0;i<N;i++) {
    int minj = i;
    for(int j=i; j<N; j++) {
      if(A[j].value < A[minj].value) minj = j;
    }
    Card t = A[i]; A[i] = A[minj]; A[minj] = t;
  }
}

void print(struct Card A[], int N) {
  for(int i=0; i<N; i++) {
    if(i>0) cout << " ";
      cout << A[i].suit << A[i].value;
  }
  cout << endl;
}

bool isStable(struct Card C1[], struct Card C2[], int N) {
  for(int i=0; i<N; i++) {
    if(C1[i].suit != C2[i].suit) return false;
  }
  return true;
}

int main(void) {
  Card C1[100], C2[100];
  int N;

  cin >> N;
  for(int i=0;i<N; i++) {
    cin >> C1[i].suit >> C1[i].value;
  }

  for(int i=0; i<N; i++) C2[i] = C1[i];

  bubble(C1,N);
  selection(C2,N);

  print(C1,N);
  cout << "Stable" << endl;
  print(C2,N);
  if(isStable(C1,C2,N)) {
    cout << "Stable" << endl;
  } else {
    cout << "Not stable" << endl;
  }

  return 0;
}


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

using namespace std;

int main()
{
    int n, t, a;
    cin >> n >> t >> a;
    vector<long long> h(n);

    for (int i = 0; i < n; i++) {
      cin >> h.at(i);
    }
    
    double tmp;
    double check;
    double carNear = 10000;
    int ans;
    for (int i = 0; i < n; i++){
        tmp = t - h.at(i) * 0.006;
        check = abs(a - tmp);
        carNear = min(carNear, check);
        if (carNear == check) ans = i + 1;
    }
    
    cout << ans << endl;

}

Measured memory_bytes: 256