akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

int main() {
  string s; int K;
  cin >> s >> K;
  vector<string> lst;
  for (int i = 0; i < s.size(); i++) {
    for (int j = 1; j <= K; j++) {
      lst.push_back(s.substr(i, j));
    }
  }
  sort(lst.begin(), lst.end());
  lst.erase(unique(lst.begin(), lst.end()), lst.end());
  cout << lst[K-1] << endl;
  return 0;
}

Measured memory_bytes: 1660
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(int)(a); (i)<(int)(b); ++(i))
#define rFor(i, a, b) for(int (i)=(int)(a)-1; (i)>=(int)(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> pii;
typedef pair<int, lint> pil;
typedef pair<lint, lint> pll;
template<class T>bool chmax(T &a, const T &b){if(a<b){a=b; return true;} return false;}
template<class T>bool chmin(T &a, const T &b){if(a>b){a=b; return true;} return false;}
 
constexpr lint mod = 1e9+7;
constexpr lint INF = mod*mod;
constexpr int MAX = 100010;

int diag(pii p){
    return p.fi*p.fi + p.se*p.se;
}

int main(){
    vector<pii> p;
    For(i, 1, 1000)For(j, i+1, 1000) p.emplace_back(i, j);
    auto cmp = [&](const pii &a, const pii &b){
        if(diag(a) == diag(b)) return a.fi < b.fi;
        return diag(a) < diag(b);
    };
    sort(p.begin(), p.end(), cmp);
    auto check = [&](pii a, pii b){return cmp(a, b);};
    
    int h, w;
    while(scanf("%d%d", &h, &w) && h){
        pii ans;
        int low = 0, high = p.size()-1;
        while(high-low > 1){
            int mid = (high+low)/2;
            (check({h, w}, p[mid]) ? high : low) = mid;
        }
        
        ans = p[high];
        printf("%d %d\n", ans.fi, ans.se);
    }
}


Measured memory_bytes: 6836
# -*- coding: utf-8 -*-

import sys
from bisect import bisect_left

sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
INF=float('inf')

N=INT()
A=[INT() for i in range(N)]

B=[A[0]]
for i in range(1, N):
    if A[i]>B[-1]:
        B.append(A[i])
    else:
        B[bisect_left(B, A[i])]=A[i]
print(len(B))



Measured memory_bytes: 10360
#include<bits/stdc++.h>
using namespace std;
constexpr int64_t mod=1e9+7;

int main()
{
  int a,b;
  cin>>a>>b;
  int ans=(b-1)/(a-1);
  if((b-1)%(a-1)!=0) ans++;
  cout<<ans;
}

Measured memory_bytes: 256
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		
		int ans = 1;
		if(S[0] == 'S' && S[1] == 'S' && S[2] == 'S') ans = 0;
		if(S[0] == 'R' && S[1] == 'R' && S[2] == 'S') ans = 2;
		if(S[0] == 'S' && S[1] == 'R' && S[2] == 'R') ans = 2;
		if(S[0] == 'R' && S[1] == 'R' && S[2] == 'R') ans = 3;
		
		Console.WriteLine(ans);
	}
	String S;
	public Sol(){
		S = rs();
	}

	static String rs(){return Console.ReadLine();}
	static int ri(){return int.Parse(Console.ReadLine());}
	static long rl(){return long.Parse(Console.ReadLine());}
	static double rd(){return double.Parse(Console.ReadLine());}
	static String[] rsa(char sep=' '){return Console.ReadLine().Split(sep);}
	static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));}
	static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));}
	static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));}
}


Measured memory_bytes: 25868
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

N = int(readline())

nodes = [{} for i in range(N+1)]

for i in range(N-1):
    u,v,w = map(int,readline().split())
    nodes[u][v] = w
    nodes[v][u] = w

ans = [-1]*(N+1)
ans[1] = 0

def dfs(start,to,dist):
    ver = nodes[start][to]
    ans[to] = (dist + ver)%2
    for k in nodes[to].keys():
        if k != start:
            dfs(to,k,dist+ver)

for k in nodes[1].keys():
    dfs(1,k,0)

for i in range(N):
    print(ans[i+1])


Measured memory_bytes: 89732
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  long long h, w;
  cin >> h >> w;
  
  bool heven = h%2==0;
  bool weven = w%2==0;
  long long ans;
  
  if (h!=1 && w!=1 ) {
    
    if (heven && weven)
      ans = h * w / 2;
    else if (!heven && weven)
      ans = w / 2 * h;
    else if (heven && !weven)
      ans = h / 2 * w;
    else
     ans = h / 2 * w + w / 2 + 1;
    
  }
  
  else
    ans = 1;
      
  cout << ans << endl;
}

Measured memory_bytes: 3624
import sys
input = sys.stdin.readline

INF = 10**19
N, K = map(int, input().split())
A = list(map(int, input().split()))
pos = []
neg = []
for a in A:
    if a >= 0:
        pos.append(a)
    else:
        neg.append(a)
pos.sort()
neg.sort()
p, n = len(pos), len(neg)
if K <= p * n:
    lb, ub = -INF, INF
    while ub - lb > 1:
        mid = (lb + ub) // 2
        cnt = 0

        s, t = 0, 0
        while s < p:
            while t < n and pos[s] * neg[t] <= mid:
                t += 1
            cnt += t
            s += 1

        if cnt < K:
            lb = mid
        else:
            ub = mid
    print(ub)
else:
    K -= p * n
    neg = neg[::-1]
    lb, ub = -INF, INF
    while ub - lb > 1:
        mid = (lb + ub) // 2
        cnt = 0

        s, t = p-1, 0
        while s >= 0:
            while t < s and pos[s] * pos[t] <= mid:
                t += 1
            cnt += min(s, t)
            s -= 1

        s, t = n-1, 0
        while s >= 0:
            while t < s and neg[s] * neg[t] <= mid:
                t += 1
            cnt += min(s, t)
            s -= 1

        if cnt < K:
            lb = mid
        else:
            ub = mid
    print(ub)


Measured memory_bytes: 90708
#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
using namespace std;
const ll mod=1e18+7;
const ll inf = (ll)1e17;
const ld eps = 1e-12;
const ld PI = 3.14159265358979323846;
ll mul(ll a, ll b, ll m = mod) { return (ll)(a * b) % m;}
ll add(ll a, ll b, ll m = mod) { a += b; if(a >= m) a -= m; if(a < 0) a += m; return a;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}




int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll n;
    cin>>n;
    vector<ll>v(n);
    for(int i=0;i<n;i++)cin>>v[i];
    ll res=1e18;
    for(int i=0;i<=100;i++){
        ll ans=0;
        for(int j=0;j<n;j++){
            ans+=((i-v[j])*(i-v[j]));
        }
        res=min(res,ans);
    }
    cout<<res<<endl;
    return 0;
    }


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using static Input;

public class Prog
{
    private const int INF = 1000000007;
    private struct Pair { public int x, y; public Pair(int x, int y) { this.x = x; this.y = y; } }
    private struct Triple { public int a, b, c; public Triple(int x, int y, int z) { a = x; b = y; c = z; } }
    public static void Main()
    {
        var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
        Console.SetOut(sw);
        int N = NextInt();
        int Q = NextInt();
        List<Triple> Event = new List<Triple>(2 * N);
        for (int i = 0; i < N; i++)
        {
            int s = NextInt();
            int t = NextInt();
            int x = NextInt();
            Event.Add(new Triple(s - x, 0, x));
            Event.Add(new Triple(t - x, 1, x));
        }
        int[] D = Enumerable.Range(0, Q).Select(v => NextInt()).ToArray();
        //Event.Sort((x,y) => x.a.CompareTo(y.a));
        Event = Event.OrderBy(x => x.a).ToList();
        SortedSet<int> SS = new SortedSet<int>();
        List<int> ans = new List<int>(Q);
        int index = 0;
        foreach (var t in D)
        {
            //Dまでに行われるイベントを済ます
            while (index < Event.Count() && t >= Event[index].a)
            {
                if (Event[index].b == 0)
                {
                    SS.Add(Event[index].c);
                }
                else if (Event[index].b == 1)
                {
                    SS.Remove(Event[index].c);
                }
                index++;
            }
            if (SS.Count() == 0) ans.Add(-1);
            else ans.Add(SS.First());
        }
        ans.ForEach(Console.WriteLine);
        Console.Out.Flush();
    }
}

public class Input
{
    private static Queue<string> q = new Queue<string>();
    private static void Confirm() { if (q.Count == 0) foreach (var s in Console.ReadLine().Split(' ')) q.Enqueue(s); }
    public static int NextInt() { Confirm(); return int.Parse(q.Dequeue()); }
    public static long NextLong() { Confirm(); return long.Parse(q.Dequeue()); }
    public static char NextChar() { Confirm(); return char.Parse(q.Dequeue()); }
    public static string NextString() { Confirm(); return q.Dequeue(); }
    public static double NextDouble() { Confirm(); return double.Parse(q.Dequeue()); }
    public static int[] LineInt() { return Console.ReadLine().Split(' ').Select(int.Parse).ToArray(); }
    public static long[] LineLong() { return Console.ReadLine().Split(' ').Select(long.Parse).ToArray(); }
    public static string[] LineString() { return Console.ReadLine().Split(' ').ToArray(); }
    public static double[] LineDouble() { return Console.ReadLine().Split(' ').Select(double.Parse).ToArray(); }
}


Measured memory_bytes: 48452
N, M = gets.split.map(&:to_i)
edges = Array.new(N){Hash.new}
M.times do |i|
    a, b = gets.split.map{|s|s.to_i-1}
    if edges[a][b]
        edges[a].delete(b)
        edges[b].delete(a)
    else
        edges[a][b] = true
        edges[b][a] = true
    end
end

N.times do |i|
    next if edges[i].length == 0
    prev = i
    loop do
        succ = edges[prev].first[0]
        edges[prev].delete(succ)
        edges[succ].delete(prev)
        if edges[succ].length == 0
            if succ == i
                break
            else
                puts 'NO'
                exit
            end
        end
        prev = succ
    end
end

puts 'YES'

Measured memory_bytes: 32124
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
	ll k;
    cin >> k;
    ll ans=1,mod=7%k;
    while(mod!=0){
    	mod=(mod*10+7)%k;
        ans++;
        if(ans>k){
            cout << "-1" << endl;
            return 0;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3612
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <memory>
#include <complex>
#include <numeric>
#include <cstdio>
#include <iomanip>

#define REP(i,m,n) for(int i=int(m);i<int(n);i++)
#define RREP(i,m,n) for(int i=int(n)-1;i>=int(m);--i)
#define EACH(i,c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

#ifdef LOCAL
#define DEBUG(s) cout << (s) << endl
#define dump(x)  cerr << #x << " = " << (x) << endl
#define BR cout << endl;
#else
#define DEBUG(s) do{}while(0)
#define dump(x) do{}while(0)
#define BR 
#endif
using namespace std;

using UI = unsigned int;
using UL = unsigned long;
using LL = long long int;
using ULL = unsigned long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VVLL = vector<VLL>;
using VS = vector<string>;
using PII = pair<int,int>;
using VP = vector<PII>;

//struct edge {int from, to, cost;};

constexpr double EPS = 1e-10;
//constexpr double PI  = acos(-1.0);
//constexpr int INF = INT_MAX;
constexpr int MOD = 1'000'000'007;
//inline void modAdd(LL &l, LL &r) {l = (l + r) % MOD;}

template<class T> inline T sqr(T x) {return x*x;}

void solve() {
    int n,k;
    cin >> n >> k;
    VLL v(n);
    REP(i,0,n) cin >> v[i];

    LL ans = 0;
    REP(i,0,min(n,k)+1) REP(j,0,min(n,k)-i+1) {
        VLL h;
        REP(l,0,i) h.push_back(v[l]);
        REP(m,0,j) h.push_back(v[n-m-1]);
        sort(all(h));
        LL sum = 0;
        REP(l,0,i+j) {
            if (h[l] < 0 && l < k - i - j) continue;
            sum += h[l];
        }
        ans = max(ans, sum);
    }
    cout << ans << endl;
}

int main() {
    solve();
    
    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 k = Integer.parseInt(sc.next());
        int a = Integer.parseInt(sc.next());
        int b = Integer.parseInt(sc.next());
        sc.close();

        // 主処理
        boolean judge = false;
        for (int i = a; i <= b; i++) {
            if (i % k == 0) {
                judge = true;
                break;
            }
        }
        String result = judge ? "OK" : "NG";

        // 出力
        System.out.println(result);
    }
}


Measured memory_bytes: 35708
#include <bits/stdc++.h>
using namespace std;
int main() {
  int X,Y;
  cin>>X>>Y;
  int ans =0;
  for(int i=0; i<X+1; i++){
    int a =Y-4*i;
    if(a%2==0 && a/2 ==X-i){
      ans = 1;
      break;
    }
  }
  if (ans ==1)
    cout<<"Yes"<<endl;
  else
    cout<<"No"<<endl;
}



Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INFLL = 1e18;
int main() {
    int n, m, l;
    cin >> n >> m >> l;
    vector<vector<ll>> g(n, vector<ll>(n, INFLL));
    
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        g[a][b] = g[b][a] = c;
    }
    
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
            }
        }
    }
    
    vector<vector<ll>> chdist(n, vector<ll>(n, INFLL));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (g[i][j] <= l) {
                chdist[i][j] = 1;
            }
        }
    }
    
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                chdist[i][j] = min(chdist[i][j], chdist[i][k] + chdist[k][j]);
            }
        }
    }
    
    int q;
    cin >> q;
    while (q--) {
        int s, t;
        cin >> s >> t;
        s--; t--;
        if (chdist[s][t] == INFLL) {
            cout << -1 << endl;
        } else {
            cout << chdist[s][t]-1 << endl;
        }
    }
    

            
    return 0;
}


Measured memory_bytes: 1920
//-------------------------------------------
//-               Train Fare                -
//-                                         -
//-       autumn_eel niha katemasen!        -
//-------------------------------------------



#include<iostream>
#include<functional>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;

void reader(int *x) {
	int k = getchar_unlocked(); *x = k - '0';
	while (true) {
		k = getchar_unlocked();
		if (k < '0' || k > '9') break;
		*x = ((*x) << 1) + ((*x) << 3) + k - '0';
	}
}
void writeln(int x) {
	int s = 0; char f[10];
	while (x) {
		f[s++] = x % 10;
		x /= 10;
	}
	if (!s) f[s++] = 0;
	while (s--) putchar_unlocked(f[s] + '0');
	putchar_unlocked('\n');
}
#pragma warning(disable:4996)
int n, m, q, a[200003], b[200003], c[200003], d[200003], e[100003], dist[100003], E[200003];
vector<pair<int, int> > z[100003]; vector<int> x[100003];
vector<int>D[100003];
int main() {
	reader(&n); reader(&m); reader(&q);
	fill(d, d + m + 1, 1 << 30);
	for (int i = 1; i <= m; i++) reader(&a[i]), reader(&b[i]);
	for (int i = 1; i <= q; i++) reader(&c[i]), d[c[i]] = i;
	for (int i = 1; i <= m; i++) {
		x[a[i]].push_back(b[i]);
		x[b[i]].push_back(a[i]);
	}
	fill(dist, dist + n + 1, -1); dist[1] = 0;
	queue<int> Q1; Q1.push(1);
	while (!Q1.empty()) {
		int a1 = Q1.front(); Q1.pop();
		for (int i : x[a1]) {
			if (dist[i] == -1) {
				dist[i] = dist[a1] + 1;
				Q1.push(i);
			}
		}
	}
	for (int i = 1; i <= m; i++) {
		if (dist[a[i]] > dist[b[i]]) z[a[i]].push_back(make_pair(b[i], d[i]));
		if (dist[b[i]] > dist[a[i]]) z[b[i]].push_back(make_pair(a[i], d[i]));
	}
	for (int i = 1; i <= n; i++) D[dist[i]].push_back(i);
	e[1] = (1 << 30);
	for (int i = 1; i < n; i++) {
		for (int j : D[i]) {
			for (pair<int, int>k : z[j]) {
				e[j] = max(e[j], min(e[k.first], k.second));
			}
		}
	}
	for (int i = 2; i <= n; i++) {
		if (e[i] < 300000) E[e[i]]++;
	}
	for (int i = 1; i <= q; i++) {
		E[i] += E[i - 1];
		writeln(E[i]);
	}
	return 0;
}

Measured memory_bytes: 23320
n = int(input())
s = input()
dp_L = [0]*(n+1)
dp_R = [0]*(n+1)

for i in range(n):
    dp_L[i+1] = dp_L[i]+[0, 1][s[i] == 'W']

for i in reversed(range(n)):
    dp_R[i] = dp_R[i+1]+[0, 1][s[i] == 'E']
    
print(min(L+R for L, R in zip(dp_L, dp_R)))


Measured memory_bytes: 27148
#include<bits/stdc++.h>
int ctoi(char c) {
 switch (c) {
 case '0': return 0;
 case '1': return 1;
 case '2': return 2;
 case '3': return 3;
 case '4': return 4;
 case '5': return 5;
 case '6': return 6;
 case '7': return 7;
 case '8': return 8;
 case '9': return 9;
 default: return 0;
 }
}

#define ll long long
using namespace std;
int main(){
	string a,b,c;
   cin>>a;
   int q= ctoi(a[0])+ctoi(a[1])+ctoi(a[2]);
   cout<<q;
 return 0;
}


Measured memory_bytes: 3608
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int H = sc.nextInt();
        int W = sc.nextInt();
        int h = sc.nextInt();
        int w = sc.nextInt();
        
        System.out.println(H * W - (h * W + w * H) + h * w);
    }           
}

Measured memory_bytes: 23124
using System;

namespace TestSpace
{
    class Test
    {
        static void Main(string[] args)
        {
            string[] arrRead;
            int x, y;

            while (true)
            {
                arrRead = Console.ReadLine().Split(' ');
                x = int.Parse(arrRead[0]);
                y = int.Parse(arrRead[1]);

                if (x == 0 && y == 0) break;
                if (x < y)
                {
                    Console.WriteLine("{0} {1}", x, y);
                }
                else
                {
                    Console.WriteLine("{0} {1}", y, x);
                } 
            }
        }
    }
}



Measured memory_bytes: 17904
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int a[520000],n,k;
int del(){
	int top=n;
	while(a[top]==0)top--;
	if(a[top]==1){a[top]=0;return 0;}
	a[top]--;
	for(int i=top+1;i<=n;i++)a[i]=k;
}
int main(){
	scanf("%d%d",&k,&n);
	if(k==1){
		for(int i=1;i<=(n+1)/2;i++)printf("1 "); 
		return 0;
	}
	if(k%2==0){
		printf("%d ",k/2);
		for(int i=1;i<n;i++)printf("%d ",k);
	}
	if(k%2==1){
		for(int i=1;i<=n;i++)a[i]=(k+1)/2;
		for(int i=1;i<=n/2;i++)
			del();
		for(int i=1;i<=n;i++)if(a[i]!=0)printf("%d ",a[i]);
	} 
}


Measured memory_bytes: 3456
#include<stdio.h>

int main( void ){

    int i,j;    /*ループカウンタ*/

    /*loop*/
    for( i = 1; i < 10; i++ ){
        for( j = 1; j < 10; j++ ){       
            printf( "%dx%d=%d\n", i, j, i * j );
        }
    }

    return 0;
}


Measured memory_bytes: 2048
#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
typedef long long ll;
const long long INF = 1LL << 60;
int main()
{
    int N;
    cin >> N;
    vector<int> p(N);

    rep(i, N) {
        int a;
        cin >> a;
        if (a == i + 1) {
            p[i] = 1;
        }
        else {
            p[i] = 0;
        }
    }

    rep(i, N - 1) {
        if (p[i] == 1 && p[i + 1] == 1) p[i + 1] = 0;
    }

    int ans = 0;
    rep(i, N) {
        ans += p[i];
    }

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

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

int main() {
	string s, t;
	cin >> s >> t;
	if(s == t){
		cout << "Yes" << endl;
	}else{
		int a = s.size();
		for(int i = 0; i < a; i++){
			for(int j = 0; j < a; j++){
				int k;
				if(i + j >= a){
					k = i + j - a;
				}else{
					k = i + j;
				}
				if(t[j] != s[k]){
					break;
				}else if(t[j] == s[k] && j == a - 1){
					cout << "Yes" << endl;
					return 0;
				}	
			}
		}
		cout << "No" << endl;
	}
	// your code goes here
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int N,K;
    string S;
    char A,B,C,a,b,c;
    cin >> N >>K;
    cin >>S;
    if(S.at(K-1)=='A'){
        S.at(K-1) = 'a';
        cout << S << endl;
    }
    else if(S.at(K-1)=='B'){
        S.at(K-1) = 'b';
         cout << S << endl;
    }
    else if(S.at(K-1)=='C'){
        S.at(K-1) = 'c';
        cout << S << endl;
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
#define ff              first
#define ss              second
#define ll              long long
#define dd              double
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define vll             vector<long long>
#define vdd             vector<double>
#define vpii            vector<pair<int,int>>
#define vpll            vector<pair<long long,long long>>
#define vvi             vector<vector<int>>
#define vvll            vector<vector<long long>>
#define mii             map<int,int>
#define mll             map<long long,long long>
#define umii            unordered_map<int,int>
#define umll            unordered_map<long long,long long>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define rep(i,n)        for(int i=0;i<n;i++)
#define rep2(i,a,b)     for(int i=a;i<b;i++)
#define rev(i,n)        for(int i=n;i>=0;i--)
#define rev2(i,a,b)     for(int i=a;i>=b;i--)
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define inf             9e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
#define fio             ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl            '\n'
#define all(x)          x.begin(),x.end()
#define d0(x)           cout <<x<<" "
#define d1(x)           cout <<x<<endl
#define d2(x,y)         cout <<x<<" "<<y<<endl
#define d3(x,y,z)       cout <<x<<" "<<y<<" "<<z<<endl
#define d4(x,y,z,w)     cout <<x<<" "<<y<<" "<<z<<" "<<w<<endl
#define read2(x,y)      cin>>x>>y
#define read3(x,y,z)    cin>>x>>y>>z
#define read4(x,y,z,w)  cin>>x>>y>>z>>w
#define read5(x,y,z,w,a)cin>>x>>y>>z>>w>>a
#define sz(a)           (int)a.size()
const ll mod=1e9+7;
const double PI = 3.14159265359;
const ll MOD=998244353;
void i_o()
{
   #ifndef ONLINE_JUDGE
   freopen("input.txt", "r", stdin);
   freopen("output.txt", "w", stdout);
   #endif
}

int main() {
   fio
   //i_o();
   int r,c;
   cin>>r>>c;
   vector<vector<char>> A(r,vector<char>(c,'.'));
   rep(i,r){
      rep(j,c){
         char c;
         cin>>c;
         if(c!='.') A[i][j]='#';
      }
   }
   vvll dp(r,vll(c,0));
   if(A[0][0]=='#'||A[r-1][c-1]=='#'){
      d1(0);
      return 0;
   }
   rep(i,r){
      rep(j,c){
         if(A[i][j]=='#') continue;
         if(i==0&&j==0) dp[i][j]=1;
         else if(i==0) dp[i][j]=dp[i][j-1];
         else if(j==0) dp[i][j]=dp[i-1][j];
         else dp[i][j]=dp[i-1][j]+dp[i][j-1];
         dp[i][j]%=mod;
      }
   }
   d1(dp[r-1][c-1]);
   return 0;
}



Measured memory_bytes: 9088
// ABC095 A
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <utility>

using namespace std;

int main() {
    int n = 0;
    for (int i = 0; i < 3; i++) {
        char c = getc(stdin);
        if (c == 'o') {
            n++;
        }
    }

    cout << 700 + 100 * n << endl;
}


Measured memory_bytes: 888
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <map>
#include <queue> 
#include <stack>
#include <set>
#include <list>

using namespace std;
typedef long long ll;
#define rep(i, s, e) for (int(i) = (s); (i) <= (e); ++(i))
#define all(x) x.begin(),x.end()


int main()
{
    int n;cin>>n;
    map<int,int> mp;
    rep(i,1,n){
        int a;cin>>a;
        ++mp[a];
    }
    int cnt = 0;
    for(auto x:mp){
        if(x.second%2==0)++cnt;
    }
    if(cnt%2)cout<<mp.size()-1<<endl;
    else cout<<mp.size()<<endl;
}


Measured memory_bytes: 4992
#include<bits/stdc++.h>
#define pll              pair<long,long>
#define pii              pair<int,int>
#define scn(a)           scanf("%d", &a)
#define scn2(a, b)       scanf("%d%d", &a, &b)
#define scn3(a, b, c)    scanf("%d%d%d", &a, &b, &c)
#define pairl            pair<ll , ll >
#define scnl(a)          scanf("%lld", &a)
#define scnl2(a, b)      scanf("%lld%lld", &a, &b)
#define scnl3(a, b, c)   scanf("%lld%lld%lld", &a, &b, &c)
#define scns(s)          scanf("%s",s)
#define prts(s)          printf("%s\n",s)
#define prt(a)           printf("%d\n", a)
#define prtl(a)          printf("%lld\n", a)
#define prs(a)           printf("%d ", a)
#define prt2(a, b)       printf("%d %d\n", a, b)
#define prt3(a, b, c)    printf("%d %d %d\n", a, b, c)
#define prsl(a)          printf("%lld ", a)
#define prtl2(a, b)      printf("%lld %lld\n", a, b)
#define prtl3(a, b, c)   printf("%lld %lld %lld\n", a, b, c)
#define ptcs(a)          printf("Case %d: ", a)
#define pf               printf
#define sc               scanf
#define vi               vector<int >
#define vil              vector<ll >
#define pb               push_back
#define mem(a, b)        memset((a), (b), sizeof(a))
#define lg2(n)           (31-__builtin_clz(n))
#define N                300005
#define inf              999999999
#define ll               long long
#define ull              unsigned long long
#define MIN              INT_MIN
#define MAX              INT_MAX
#define fast             ios_base::sync_with_stdio(false),cin.tie(NULL)
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
typedef tree<int , null_type, less<int >, rb_tree_tag, tree_order_statistics_node_update> odrst;
ll gcd(ll a, ll b){if(b==0) {return a;}return gcd(b, a % b);}
ll BigMod(ll B,ll P,ll M){     ll R=1; while(P>0)      {if(P%2==1){R=(R*B)%M;}P/=2;B=(B*B)%M;} return R;}
//________________________________________________________________________________________________________________
bool cmp(pair<ll,ll> a, pair<ll,ll> b)
{
    if(a.first>b.first) return true;
    if(a.first<b.first) return false;
    if(a.second<b.second) return true;
    else return false;

}
bool ok=false;
ll cnt[N],a[N];
ll t,n,m,x,p,r,y,z,mod=998244353,ans=0;
vector<ll>v[N];
string s,s1;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        v[a[i]].pb(i);
    }
    x=0;
    for(int i=1;i<N;i++)
    {
        bool ok=false;
        for(int j=0;j<v[i].size();j++)
        {
            if(v[i][j]>x)
            {
                ok=true;
                x=v[i][j];
                break;
            }
        }
        if(!ok) break;
        ans++;
    }
    if(ans==0) cout<<-1<<endl;
    else cout<<n-ans<<endl;
    return 0;
}


Measured memory_bytes: 16768
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i=0; i<(int)(n); i++)
#define all(x) x.begin(), x.end()
#define mod 1000000007
typedef long long ll;

int main() {
    int n;
    cin >> n;
    int sum = 0;
    vector<int> vec;
    rep(i, n){
        int num;
        cin >> num;
        vec.push_back(num);
    }
    vector<int> sumvec(100, 0);
    for(int i=1; i<=100; i++){
        for(int j=0; j<n; j++){
            sumvec[i-1] += pow(vec[j]-i, 2);
        }
    }
    int smallest = mod;
    for(auto a : sumvec){
        smallest = min(smallest, a);
    }
    cout << smallest << endl;
    return 0;
}

Measured memory_bytes: 256
N = int(input())


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


L1 = factorization(N - 1)
s = 1
# print(L1)
for [a, b] in L1:
    s *= (b + 1)
# print(s)


def make_divisors(n):
    lower_divisors, upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]


for i in set(make_divisors(N))-{1}:
    temp = N
    while temp % i == 0:
        temp //= i
    if (temp-1) % i == 0:
        s += 1
s -= 1
if N == 2:
    print(1)
else:
    print(s)

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

using namespace std;

int main() {
  int a, b;

  cin >> a >> b;

  int minimo = min(a, b);
  int maximo = max(a, b);

  for(int i = minimo; i <= maximo; i++) {
    if((a*b*i) & 1) {
      cout << "Yes\n";
      return 0;
    }
  }

  cout << "No\n";

  return 0;
}

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

//g??°???
vector<int>G;
long long cnt;
int A[1000000 + 10];

// ??´??????g????????\??????
void insertionSort(int A[], int n, int g) {
	for (int i = g; i < n; i++) {
		int v = A[i];
		int j = i - g;
		while (j >= 0 && A[j] > v) {
			A[j + g] = A[j];
			j -= g;
			cnt++;
		}
		A[j + g] = v;
	}
}
//????°???????
void shellsort(int A[], int n) {
	for (int i = G.size() - 1; i >= 0; i--) {
		insertionSort(A, n, G[i]);
	}
}

// ??????g??°???
void getArray(int n) {
	for (int h = 1; h <= n;) {
		G.push_back(h);
		h = 3 * h + 1;
	}
}


int main() {
	
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d", &A[i]);
	getArray(n);
	shellsort(A,n);
	
	int len = G.size();
	printf("%d\n", len);
	for (int i = len - 1; i >= 0; i--)
		printf("%d%c", G[i], i == 0 ? '\n' : ' ');
	printf("%lld\n", cnt);
	for (int i = 0; i < n; i++)
		printf("%d\n", A[i]);
	return 0;
}

Measured memory_bytes: 7172
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <queue>
#include <stack>
#include <complex>
#include <utility>
#include <set>
#include <cmath>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
#define pi acos(-1)
#define all(v) v.begin(),v.end()
#define EPS (1e-10)
#define EQ(a,b) (abs((a)-(b))<EPS)
#define EQV(a,b) (EQ((a).real(),(b).real()) && EQ((a).imag(),(b).imag()))
using namespace std;
typedef pair<int,int> point;
typedef complex<double> P;
typedef long long ll;

const double eps = 1e-8;
const double INF = 1e12;


double dot(P a,P b){
	return a.real()*b.real()+a.imag()*b.imag();
}
double cross(P a,P b){
	return a.real()*b.imag()-a.imag()*b.real();
}

bool is_orthogonal(P a1,P a2,P b1,P b2){
	return EQ(dot(a1-a2,b1-b2),0.0);
}
bool is_parallel(P a1,P a2,P b1,P b2){
	return EQ(cross(a1-a2,b1-b2),0.0);
}

bool is_point_on_line(P a,P b,P c){
	return EQ(cross(b-a,c-a),0.0);
}

bool is_point_on_linesegment3(P a,P b,P c){
	return (abs(a-c)+abs(c-b)<abs(a-b)+EPS);
}

double distance_l_p(P a,P b,P c){
	return abs(cross(b-a,c-a))/abs(b-a);
}


double distance_ls_p(P a,P b,P c){
	if(dot(b-a,c-a)<EPS)return abs(c-a);
	if(dot(a-b,c-b)<EPS)return abs(c-b);
	return abs(cross(b-a,c-a))/abs(b-a);
}

bool prime[1000001];

int main(){
	int n,x;
	rep(i,1000001)prime[i]=true;
	prime[0]=prime[1]=false;
	for(int i=2;i<1001;i++){
		for(int j=2;i*j<1000000;j++){
			prime[i*j]=false;
		}
	}
	while(1){
		cin>>n>>x;
		if(n==0 && x==0)break;
		int menu[n];
		rep(i,n)cin>>menu[i];
		bool cost[1000001];
		rep(i,1000001)cost[i]=false;
		cost[0]=true;
		rep(i,x+1){
			if(cost[i]){
				rep(j,n)if(i+menu[j]<=x)cost[i+menu[j]]=true;
			}
		}
		bool check=true;
		for(int i=x;i>=2;i--){
			if(cost[i]==1 && prime[i]==1){
				cout<<i<<endl;
				check=false;
				break;
			}
		}
		if(check)cout<<"NA"<<endl;
	}
	return 0;
}

Measured memory_bytes: 3116
using System;

public class AtCoderA
{
    static void Main()
    {
        int h;
        int a;
        {
            var line = Console.ReadLine();
            var words = line.Split(' ');
            h = int.Parse(words[0]);
            a = int.Parse(words[1]);
        }

        int answer = (h / a) + (h % a == 0 ? 0 : 1);

        Console.WriteLine(answer);
    }
}

Measured memory_bytes: 13140
fun main(args: Array<String>) {
    var i = readLine()!!.split(" ").map { it.toDouble() }
    print(if (i[1] == 100.0) (Math.pow(100.0, i[0]) * 101).toInt() else (Math.pow(100.0, i[0]) * i[1]).toInt())
}



Measured memory_bytes: 37896
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class ModTools:
    """ 階乗たくさん使う時用のテーブル準備 """

    def __init__(self, MAX, MOD):
        """ MAX：階乗に使う数値の最大以上まで作る """
        
        MAX += 1
        self.MAX = MAX
        self.MOD = MOD
        # 階乗テーブル
        factorial = [1] * MAX
        factorial[0] = factorial[1] = 1
        for i in range(2, MAX):
            factorial[i] = factorial[i-1] * i % MOD
        # 階乗の逆元テーブル
        inverse = [1] * MAX
        # powに第三引数入れると冪乗のmod付計算を高速にやってくれる
        inverse[MAX-1] = pow(factorial[MAX-1], MOD-2, MOD)
        for i in range(MAX-2, 0, -1):
            # 最後から戻っていくこのループならMAX回powするより処理が速い
            inverse[i] = inverse[i+1] * (i+1) % MOD
        self.fact = factorial
        self.inv = inverse
    
    def nCr(self, n, r):
        """ 組み合わせの数 (必要な階乗と逆元のテーブルを事前に作っておく) """

        if n < r: return 0
        # 10C7 = 10C3
        r = min(r, n-r)
        # 分子の計算
        numerator = self.fact[n]
        # 分母の計算
        denominator = self.inv[r] * self.inv[n-r] % self.MOD
        return numerator * denominator % self.MOD

H, W, K = MAP()

N = H * W
mt = ModTools(N, MOD)

ansh = 0
for i in range(1, H+1):
    ansh += i * (H-i) * pow(W, 2, MOD)
    ansh %= MOD
ansh *= mt.nCr(N-2, K-2)
ansh %= MOD

answ = 0
for i in range(1, W+1):
    answ += i * (W-i) * pow(H, 2, MOD)
    answ %= MOD
answ *= mt.nCr(N-2, K-2)
answ %= MOD

print((ansh + answ) % MOD)


Measured memory_bytes: 18804
#include<bits/stdc++.h>
 
#define rep(i,n) for(ll i = 0;i < n;++i)
#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;
typedef pair<int,int> P;
 
const int INF = 1001001001;
const long double PI = (acos(-1));
const int mod = 1e9+7;

ll func(ll x,ll c){
    if(x >= 0) {
        return x/c+1;
    }
    if(x = -1){
        return 0;
    }
    return 0;
}

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

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

    ll ans = func(b,c)-func(a-1,c);
    cout << ans << endl;


    cout << endl;
    return 0;
}


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

int main(){
  int N;
  string S;
  cin>>N>>S;
  
  int count=0;
  for(int i=0;i<N;i++){
    if(S.at(i)=='E'){
      count++;
    }
  }
  //cout<<count<<endl;
  
  int min_n=count;
  for(int i=0;i<N;i++){
    if(S.at(i)=='E'){
      count--;
    }else{
      count++;
    }
    min_n=min(min_n,count);
  }
  cout<<min_n<<endl;
  return 0;
}

Measured memory_bytes: 900
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
    ll N,A,B;
    cin >> N >> A >> B;
    if ((N == 1 && A != B) || (A > B)) {
        cout << 0 << endl;
        return 0;
    }
    cout << (B * N - B + A) - (A * N - A + B) + 1 << endl;
}

Measured memory_bytes: 3624
N,M = map(int, input().split())

a = [int(input()) for i in range(M)]

#初期化
dp=[-1]*N
dp[0]=1

for i in a:
    dp[i-1] = 0

for i in range(1,N):
    if dp[i]==0:
        continue
    elif i==1:
        dp[i]=dp[i-1] + 1
    else:
        dp[i]=dp[i-1]+dp[i-2]

print(dp[N-1]%1000000007)


Measured memory_bytes: 460020
import sys
from itertools import combinations

index = {"M": 0, "A": 0, "R": 0, "C": 0, "H": 0}

N = int(sys.stdin.readline())
for _ in range(N):
    s = sys.stdin.readline().strip()
    if s[0] in index:
        index[s[0]] += 1

ans = 0
for (a, b, c) in combinations(index.items(), 3):
    ans += a[1] * b[1] * c[1]

print(ans)

Measured memory_bytes: 9216
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define loop(i,a,b) for(int i=a;i<b;i++)
#define test() int t;cin>>t;loop(test,1,t+1)
#define pb push_back
#define eb emplace_back
#define mkp make_pair
#define nl cout<<"\n"
#define sp cout<<" "
#define F first
#define S second
#define vi vector<int>
#define vl vector<ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vii vector<pii>
#define vll vector<pll>
#define MOD 1000000007
#define all(x) x.begin(),x.end()

template<class C> void min_self( C &a, C b ){ a = min(a,b); }
template<class C> void max_self( C &a, C b ){ a = max(a,b); }

void mod( ll &n, ll m=MOD ){ n%=m,n+=m,n%=m; }

const int MAXN = 1e5+5;
const int INF = 1e9;
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};

int main() 
{
    fastio();

    int n,k;
    cin>>n>>k;
    vector<int>a(n),dp(n,INF);
    for(int i=0;i<n;i++) cin>>a[i];
    dp[0] = 0;
    for(int i=1;i<n;i++)
    {
        for(int j=1;j<=k;j++)
        {
            if( i-j < 0 ) break;
            min_self( dp[i], abs(a[i]-a[i-j]) + dp[i-j] );
        }
    }
    cout<<dp[n-1],nl;
    return 0;
}

Measured memory_bytes: 1024
program name
    use,intrinsic :: iso_fortran_env
    implicit none
    integer(int32):: n,i,j
    integer(int32), allocatable:: b(:), te(:), ind(:)
    logical:: find
    read*, n
    allocate(b(n), te(n), ind(n))
    read*, b(:)

    do i=1,n
        ind(i) = i
    end do

    i=n

    do while(i>0)
        find=.false.
        do j=n,1,-1
            if (b(j)==ind(j)) then
                find=.true.
                te(i)=b(j)
                ind(j:) = ind(j:)-1
                i=i-1
                exit
            end if
        end do

        if (.not.find) then
            print'(i0)', -1
            stop
        end if
    end do

    do i=1,n
        print'(i0)', te(i)
    end do
end program name

Measured memory_bytes: 256
def check_prime(n):
    root_n = n ** 0.5
    for i in range(2, int(root_n) + 1):
        if n == i:
            continue
        elif n % i == 0:
            return 0
    return 1

ans = 0
for i in range(int(input())):
    num = int(input())
    ans += check_prime(num)
print(ans)


Measured memory_bytes: 5704
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;

const int MAX_N = 1000000;

vector<int> init(void){
    vector<int> prime;
    bool is_prime[MAX_N];
    memset(is_prime, true, MAX_N);
    
    is_prime[0] = is_prime[1] = false;
    for(int i=2; i<MAX_N; i++){
        if(is_prime[i]){
            prime.push_back(i);
            for(int j=2*i; j<MAX_N; j+=i) is_prime[j] = false;
        }
    }
    return prime;
}

int main(int argc, const char * argv[])
{
    int n;
    vector<int> prime = init();
    while(cin>>n){
        cout << upper_bound(prime.begin(), prime.end(), n)-prime.begin() << endl;
    }
    return 0;
}

Measured memory_bytes: 2564
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n, m, c;
  cin >> n >> m >> c;
  vector<int> bs(m);
  for (int i = 0; i < m; i++) { cin >> bs.at(i); }
  int count = 0;
  for (int i = 0; i < n; i++) {
    vector<int> as(m);
    for (int j = 0; j < m; j++) { cin >> as.at(j); }
    int sum = c;
    for (int j = 0; j < m; j++) { sum += as.at(j) * bs.at(j); }
    if (sum > 0) { count++; }
  }
  cout << count << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define M 1000000007
int main(void){
	long long n,i,j,add,flg;
	char s[53],s2[53];
	cin>>n;
	cin>>s>>s2;
	if(s[0]==s2[0]) add=3,flg=0,i=0;
	else add=6,flg=1,i=1;
	for(;i<n-1;i++){
		if(flg==0){
			if(s[i+1]!=s2[i+1]){
				add=add*2%M;
				flg=1;
				i++;
			}
			else add=add*2%M;
		}
		else {
			if(s[i+1]!=s2[i+1]){
				add=add*3%M;
				i++;
			}
			else flg=0;
		}
	}
	cout<<add<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{ 
 LL p,n;
 cin>>p>>n;
 double x=1.0/p;
 LL mm=pow(n,x)+1.0;
 for(LL i=mm;i>=1;i--)
 {
 	 if(n%(LL)pow(i,p)==0)
 	 {
 	 	cout<<i<<"\n";
 	 	return 0;
	  }
 }
}

Measured memory_bytes: 256
#include <stdio.h>
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <time.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:336777216")
using namespace std;

#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define ldb ldouble

typedef tuple<int, int, int> t3;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;

int IT_MAX = 1 << 19;
int MOD = 10000000;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1e-10;
#define szz(x) (int)(x).size()
#define rep(i, n) for(int i=0;i<n;i++)
#define Se second
#define Fi first

const int MX = 100005;

struct UF{
	int t[MX];
	int find(int x){ return t[x] ? t[x] = find(t[x]): x;}
	int merge(int a, int b){
		a = find(a), b = find(b);
		return a == b ? 0 : (t[a] = b, 1);
	}
}uf;

int A[MX], occ[MX], used[MX];

int main()
{
	int N, M;
	scanf("%d%d", &N, &M);
	for(int i = 1; i <= N; i++) scanf("%d", A+i);
	int a, b, cnt = N-1;
	for(int i = 1; i <= M; i++){
		scanf("%d%d", &a, &b); a++; b++;
		cnt -= uf.merge(a, b);
	}
	if( cnt == 0 ) return !printf("0\n");
	vector<pii> L;
	for(int i = 1; i <= N; i++) L.emplace_back(A[i], uf.find(i));
	sort(L.begin(), L.end());
	ll ans = 0, tot = 0;
	for(int i = 0; i < L.size(); i++){
		pii c = L[i];
		if( occ[c.second] ) continue;
		used[i] = 1;
		occ[c.second]++;
		ans += c.first; tot++;
	}
	for(int i = 0; i < L.size(); i++){
		if( used[i] ) continue;
		pii c = L[i];
		if( occ[c.second] == cnt ) continue;
		occ[c.second]++;
		ans += c.first; tot++;
		if( tot == cnt*2 ) break;
	}
	if( tot != cnt*2 ) printf("Impossible\n");
	else printf("%lld\n", ans);
}


Measured memory_bytes: 2676
N, T = [int(v) for v in input().split()]
min_c = float('inf')
for _ in range(N):
	c, t = [int(v) for v in input().split()]
	if t <= T:
		min_c = min(min_c, c)
if min_c == float('inf'):
	print('TLE')
else:
	print(min_c)

Measured memory_bytes: 3060
import sys
input = sys.stdin.readline
n = int(input())
a,b,c = map(int,input().split())

dpa = [a]+[0]*(n-1)
dpb = [b]+[0]*(n-1)
dpc = [c]+[0]*(n-1)

for i in range(1,n):
    a,b,c = map(int,input().split())
    dpa[i] = max(dpb[i-1],dpc[i-1])+a
    dpb[i] = max(dpc[i-1],dpa[i-1])+b
    dpc[i] = max(dpa[i-1],dpb[i-1])+c
    
print(max(dpa[-1],dpb[-1],dpc[-1]))


Measured memory_bytes: 15596
#include <algorithm>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

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

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

const double EPS = 1e-10;
const int INF = 1001001001;

struct Sweet {
	int i, p, q, r;
	int cal() {
		return p*4 + q*9 + r*4;
	}
};

int main()
{
	int n;
	while(scanf("%d", &n), n){
		Sweet sw[1000];
		rep(i, n)
			scanf("%d%d%d%d", &sw[i].i, &sw[i].p, &sw[i].q, &sw[i].r);
		
		int P, Q, R, C;
		scanf("%d%d%d%d", &P, &Q, &R, &C);
		
		bool found = false;
		rep(i, n){
			if(sw[i].p<=P && sw[i].q<=Q && sw[i].r<=R && sw[i].cal()<=C){
				printf("%d\n", sw[i].i);
				found = true;
			}
		}
		if(!found)
			puts("NA");
	}
	return 0;
}

Measured memory_bytes: 1056
#include <cstdio>
#include <vector>
#define N 100005
using namespace std;
int n, m, gr, ans, a[N], v[N];
vector<int> g[N];

void f(int p) {
	if(v[p]) return;
	v[p] = gr;
	for(int i=0; i<g[p].size(); i++) f(g[p][i]);
}

int main() {
	int i, x, y;
	scanf("%d%d", &n, &m);
	for(i=1; i<=n; i++) scanf("%d", a+i);
	while(m--) {
		scanf("%d%d", &x, &y);
		g[x].push_back(y);
		g[y].push_back(x);
	}
	for(i=1; i<=n; i++) if(!v[i]) ++gr, f(i);
	for(i=1; i<=n; i++)	if(v[i]==v[a[i]]) ans++;
	printf("%d", ans);
	return 0;
}

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

int n, a[105];
long long sol = 0;

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    sort(a + 1, a + n + 1);
    for(int i = 1; i <= n; i++) {
        for(int j = i + 1; j <= n; j++) {
            for(int k = j + 1; k <= n; k++) {
                if(a[i] != a[j] && a[j] != a[k] && a[i] + a[j] > a[k]) {
                    sol++;
                }
            }
        }
    }
    cout << sol;
    return 0;
}

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

int main(){
	/*input*/
	int a, b, c, x;	cin >> a >> b >> c >> x;
	/*calculation*/
	int ans = 0;
	for(int i = 0; i <= a; i++){
		for(int j = 0; j <= b; j++){
			for(int k = 0; k <= c; k++){
				if(500*i + 100*j + 50*k == x)ans++;
			}
		}
	}
	/*output*/
	cout << ans << endl;
}


Measured memory_bytes: 256
//#include<bits/stdc++.h>
#include<iostream>
#include <vector>
using namespace std;
#define rep(i,b) for (ll i =0; i < (b); i++)
typedef long long ll;
 
// ---** Functions **---
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
// ---** START FROM HERE **---
int d,s,t;
cin>>d>>s>>t;
if(s*t>=d) cout<<"Yes"<<endl;
else cout<<"No"<<endl;













return 0;



}


Measured memory_bytes: 3056
#include <bits/stdc++.h>
#include <vector> 
# include <cstdint>
#define FOR(i,l,r) for(int i=(l);i<(r);++i)
#define RFOR(i,l,r) for(int i=(l);i>=(int)(r);i--)
#define rep(i,n)  FOR(i,0,n)
#define rrep(i,n)  RFOR(i,n-1,0)

#define int long long
using namespace std;
const int MX = 1e6;
const int inf = 1e9;
const int mod = 1e9+7;
using ll = long long;
using P = pair<ll, ll>;
vector<int> to[100005];
int cost[100005];

int x[10];
int y[10];

double dist(ll i, ll j) {
    int xx = (x[i]-x[j])*(x[i]-x[j]);
    int yy = (y[i]-y[j])*(y[i]-y[j]);
    return sqrt(xx+yy);
}

signed main(){
    ll n;
    cin >> n;

    ll lim = (ll)sqrt(min(1e12+1, (double)(n+1)));
    ll ans = 1000000000000;
    FOR(i, 1, lim+1) {
        if(n%i==0) {
            ll a = i-1;
            ll b = (ll)n/(ll)i-1;
            ans = min(ans , a+b);
           // cout << i<<" " << (ll)n/(ll)i << endl;
        }
    }
    cout << ans << endl;

    return 0;
}



Measured memory_bytes: 2560
import sys
Input = sys.stdin.readline

N, M = map(int, Input().split())
S = Input()
T = Input()

def lcm(x, y):
    from fractions import gcd
    return (x * y) // gcd(x, y)

l = lcm(N, M)
s = S[0:N:l//M]
t = T[0:M:l//N]

if all(map(lambda a: a[0] == a[1], zip(s, t))):
    print(l)
else:
    print(-1)

Measured memory_bytes: 5304