akhauriyash/Code-Regression huggingface dataset:
from collections import deque

def solve(tree, distance, w):
    dq = deque()
    dq.appendleft((w, -1))
    while dq:
        x, prev = dq.pop()
        for a in tree[x]:
            if a == prev:
                continue
            distance[a] = distance[x] + 1
            dq.appendleft((a, x))

def main():
    N, u, v = map(int, input().split())
    tree = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(int, input().split())
        tree[a - 1].append(b - 1)
        tree[b - 1].append(a - 1)

    aoki = [0] * N
    solve(tree, aoki, v - 1)
    takahashi = [0] * N
    solve(tree, takahashi, u - 1)

    ans = 1
    for a, t in zip(aoki, takahashi):
        if a > t:
            ans = max(ans, a)
    print(ans - 1)

main()


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

#define pb push_back
#define pbk pop_back
#define mk_pr make_pair

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<string> vss;
typedef queue<int> qi;

const int MX = 123456;
int ar[30];

int main() {
        ios_base :: sync_with_stdio(0); cin.tie(0);
        string s;
        cin >> s;
        for(int i=0; i<s.size(); i++) {
                ar[ s[i]-96 ]++;
        }
        bool flg = true;
        for(int i=1; i<27; i++) if( ar[i] > 1 ) {
                flg = false; break;
        }

        flg ? cout << "yes" : cout << "no";
        cout << endl;

        return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define pi 3.141592653589793
#define mod 1000000007
#define pb push_back
#define all(v) v.begin(),v.end()
#define tc int t;cin>>t;while(t--)
#define pqmax priority_queue<int>
#define pqmin priority_queue<int,vi,greater<int>>
#define fast_io ios_base::sync_with_stdio(0), cin.tie(NULL)
#define tc_g int tt;cin>>tt;for(int ti=1;ti<=tt;ti++)
#define case_g "Case #"<<ti<<": "
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, greater_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<int, int, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_map;

int main() {
	fast_io;
	ll n, m;
	cin >> n >> m;
	vl a(n);
	for (int i = 0;i < n;i++)
		cin >> a[i];
	ll total_vote = accumulate(all(a), 0LL);
	ll min_vote = total_vote / (m * 4);
	if (total_vote % (m * 4) != 0)
		min_vote++;
	int cnt = 0;
	for (int i = 0;i < n;i++)
		if (a[i] >= min_vote)
			cnt++;
	if (cnt >= m)
		cout << "Yes\n";
	else
		cout << "No\n";
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define print(n,ans) for(int i=1;i<=n;i++)out(ans[i]),putchar(" \n"[i==n])

namespace fastIO {
	#define BUF_SIZE 100000
	//fread -> read
	bool IOerror = 0;
	inline char nc() {
		static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
		if(p1 == pend) {
			p1 = buf;
			pend = buf + fread(buf, 1, BUF_SIZE, stdin);
			if(pend == p1) {
				IOerror = 1;
				return -1;
			}
		}
		return *p1++;
	}
	inline bool blank(char ch) {
		return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
	}
	inline bool read(int &x) {
		char ch;
		while(blank(ch = nc()));
		if(IOerror) return false;
		for(x = ch - '0'; (ch = nc()) >= '0' && ch <= '9'; x = x * 10 + ch - '0');
		return true;
	}
	#undef BUF_SIZE
};
using namespace fastIO;

void out(int x)
{
    if(x>9)out(x/10);
    putchar(x%10+'0');
}

#define pa pair<int,int>
const int inf=1e9+7;
const int maxn=1e5+10;
map<pa,int>p;
int n,m,cnt,x,y,c,dis[maxn*10];
vector<int>v[maxn*10];

void dijk()
{
    priority_queue<pa,vector<pa>,greater<pa> >q;
    for(int i=1;i<cnt;i++)dis[i]=inf;dis[1]=0;
    q.push({0,1});
    while(!q.empty()){
        pa tmp=q.top();q.pop();
        int to=tmp.second;
        if(dis[to]<tmp.first)continue;
        for(int i=0;i<v[to].size();i++){
            int toto=v[to][i];
            if(to>n && toto>n){
                if(dis[toto]>dis[to]){
                    dis[toto]=dis[to];
                    q.push({dis[toto],toto});
                }
            }
            else {
                if(dis[toto]>dis[to]+1){
                    dis[toto]=dis[to]+1;
                    q.push({dis[toto],toto});
                }
            }
        }
    }
}

int main()
{
    read(n),read(m);cnt=n+1;
    map<pa,int>::iterator it,is;
    for(int i=1;i<=m;i++){
        read(x),read(y),read(c);
        it=p.find({x,c});int a,b;
        if(it==p.end()){
            p[{x,c}]=cnt;a=cnt;cnt++;
            v[a].push_back(x);
            v[x].push_back(a);
        }
        else {
            a=p[{x,c}];
            v[a].push_back(x);
            v[x].push_back(a);
        }
        is=p.find({y,c});
        if(is==p.end()){
            p[{y,c}]=cnt;b=cnt;cnt++;
            v[b].push_back(y);
            v[y].push_back(b);
        }
        else {
            b=p[{y,c}];
            v[b].push_back(y);
            v[y].push_back(b);
        }
        v[a].push_back(b),v[b].push_back(a);
    }
    dijk();
    if(dis[n]!=inf)printf("%d\n",dis[n]/2);
    else printf("-1\n");
}


Measured memory_bytes: 69372
#include <bits/stdc++.h>
using namespace std;
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
typedef pair<int, int> Pint;
typedef pair<int64_t, int64_t> Pll;

int main() {
    int X, Y, ans = 0;
    cin >> X >> Y;
    if (X == 1) {
        ans += 300000;
    }
    if (X == 2) {
        ans += 200000;
    }
    if (X == 3) {
        ans += 100000;
    }
    if (Y == 1) {
        ans += 300000;
    }
    if (Y == 2) {
        ans += 200000;
    }
    if (Y == 3) {
        ans += 100000;
    }
    if (X == 1 && Y == 1){
        ans += 400000;
    }
    cout << ans << endl;

}


Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
char a[110],b[110];
int main()
{
    scanf("%s",a);
    scanf("%s",b);
    int lena = strlen(a),n;
    bool e = true;
    for(int i = 0; i != lena; ++i)
    {
        n = 0;
        e = true;
        for(int j = i; j != lena; ++j)
        {
            if(a[j] != b[n++]){
                e = false;
                break;
            }
        }
        if(e)
        {
            n = lena - i;
            for(int j = 0; j != i;++j)
            {
                if(a[j] != b[n++])
                    e = false;
            }
        }
        if(e)
        {
            break;
        }

    }
    if(e)
    {
        printf("Yes\n");
    }
    else
        printf("No\n");
    return 0;
}


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

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("3");
            WillReturn.Add("-10 5 -4");
            //19
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5");
            WillReturn.Add("10 -4 -8 -11 3");
            //30
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("11");
            WillReturn.Add("-1000000000 1000000000 -1000000000 1000000000 -1000000000 0 1000000000 -1000000000 1000000000 -1000000000 1000000000");
            //10000000000
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();

        int[] AArr = InputList[1].Split(' ').Select(X => int.Parse(X)).ToArray();

        //負数の数
        int MinusCnt = AArr.Count(X => X < 0);

        //絶対値の最小値
        int MinABS = AArr.Min(X => Math.Abs(X));

        long SumABS = 0;
        Array.ForEach(AArr, X => SumABS += Math.Abs(X));

        //負数が偶数個の場合
        if (MinusCnt % 2 == 0) {
            Console.WriteLine(SumABS);
        }
        else { //負数が奇数個の場合
            Console.WriteLine(SumABS - MinABS*2);
        }
    }
}


Measured memory_bytes: 30684
#include <bits/stdc++.h>
using namespace std;
int main(){

  int n,q;
  cin>>n;

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

  cin>>q;
  for(int i=0;i<q;i++){

    int b,e,k;
    cin>>b>>e>>k;

    cout<<count(a.begin()+b,a.begin()+e,k)<<endl;

  }

  return 0;

}



Measured memory_bytes: 3088
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cstdlib>
using namespace std;
const int MAXN = 200005;
typedef long long ll;
struct Node{
	ll x,y;
	int id;
	bool operator < (const Node &b)const
	{
		return x==b.x?y<b.y:x<b.x;
	}
}a[MAXN],t[MAXN];
int tot,n;
ll d;
int now,front,back,sa,sb,fa[MAXN];
ll ans[MAXN];
int getan(int x)
{
	return x==fa[x]?x:fa[x]=getan(fa[x]);
}
#define NEXT {++back;continue;}
void solve(int delta)
{
	front=1,back=0;
	int end=0,last=0;
	a[0].x=-998244353;
	for(int i=1;i<=n;++i){
		if(a[i].x!=a[i-1].x){
			while(front<=back && a[front].x+d<a[i].x)++front;
			if(a[front].x+d>a[i].x || front>back)NEXT;
			end=front;
			while(end<back && a[end+1].x+d==a[i].x)++end;
			tot=last=0;
			if(a[end].x+d==a[i].x){
				last=1;
				for(int i=front;i<=end;++i)t[++tot]=a[i],++front;
			}	
		}
		if(a[end].x+d==a[i].x){
			int pos=lower_bound(t+1,t+tot+1,(Node){a[i].x-d,a[i].y-d-delta,a[i].id})-t;
			last=max(last,pos);
			if(pos==tot+1 || t[last].y>a[i].y+d+delta)NEXT;
			for(;last<=tot && t[last].y<=a[i].y+d+delta;++last){
				fa[getan(a[i].id)]=getan(t[last].id);
			}
			ans[a[i].id]+=last-pos;
			if(last!=pos)--last;
		}
		++back;
	}

}
ll final_ans[MAXN],sx,sy,tx,ty;
int main()
{
	scanf("%d%d%d",&n,&sa,&sb);
	for(int i=1,x,y;i<=n;++i){
		fa[i]=i;
		scanf("%d%d",&x,&y);
		a[i].x=x-y,a[i].y=x+y;
		a[i].id=i;
		if(i==sa)sx=x,sy=y;
		if(i==sb)tx=x,ty=y;
	}
	d=abs(sx-tx)+abs(sy-ty);
	sort(a+1,a+n+1);
	solve(0);
	for(int i=1;i<=n;++i)swap(a[i].x,a[i].y);
	sort(a+1,a+n+1);
	solve(-1);
	for(int i=1;i<=n;++i)final_ans[getan(i)]+=ans[i];
	cout<<final_ans[getan(sa)]<<endl;
	return 0;
}


Measured memory_bytes: 9728
# include <stdio.h>

int main(){
    int A, B;
    scanf("%d %d", &A, &B);
    if(A==B)
        printf("%d", A+B);
    else if(A!=B){
        if(A>B)
            printf("%d", A+(A-1));
        else
            printf("%d", B+(B-1));
    }

    return 0;
}


Measured memory_bytes: 128
import numpy as np

A1 = list(map(int,input().split()))
A2 = list(map(int,input().split()))
A3 = list(map(int,input().split()))

A = [A1,A2,A3]
a = np.array(A)

N = int(input())
for i in range(N):
    tmp = int(input())
    a = np.where(a==tmp, 0,a)

ans = 'Yes' if ((a[0][0]==0)and(a[0][1]==0)and(a[0][2]==0)) or ((a[1][0]==0)and(a[1][1]==0)and(a[1][2]==0)) or ((a[2][0]==0)and(a[2][1]==0)and(a[2][2]==0)) or ((a[0][0]==0)and(a[1][0]==0)and(a[2][0]==0)) or ((a[0][1]==0)and(a[1][1]==0)and(a[2][1]==0)) or ((a[0][2]==0)and(a[1][2]==0)and(a[2][2]==0)) or ((a[0][0]==0)and(a[1][1]==0)and(a[2][2]==0)) or ((a[0][2]==0)and(a[1][1]==0)and(a[2][0]==0)) else 'No'
print(ans)

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

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

    static class A {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int[] cnt = new int[100_002];
            int n = in.nextInt();
            for (int i = 0; i < n; i++) {
                int x = in.nextInt();
                cnt[x + 1]++;
            }

            int ans = 0;
            for (int i = 1; i < cnt.length - 1; i++) {
                int v = cnt[i - 1] + cnt[i] + cnt[i + 1];
                if (v > ans) {
                    ans = v;
                }
            }
            out.println(ans);
        }

    }
}



Measured memory_bytes: 51172
// -*- coding:utf-8-unix -*-

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
 
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}
 
macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
 
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}
 
macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
 
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
 
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
 
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
 
 
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}
 // ABC086C - Traveling
// https://atcoder.jp/contests/abs/fasks/arc089_a
 

fn main() {
    /*     input! {
        n: usize,
        mut plan: [(i32, i32, i32); n],  // Vec<(i32, i32, i32)>
    }
 */
    input! {
        n: usize,
        xs: [i32;n],
    }
    let min = xs.iter().min().unwrap();
    let max = xs.iter().max().unwrap();
    let mut ans = i32::max_value();
    for i in *min..*max + 1 {
        let tot = xs.iter().fold(0,|acc,cur|acc + (cur - i).pow(2));
        ans = std::cmp::min(ans,tot);
    }
    println!("{}",ans);
}


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

using namespace std;
using ll = long long;
const int INF = 1e9;

vector<int> BFS(vector<vector<int>> Hen, int s, pair<int,int> dam) {
    int n = Hen.size();
    vector<int> dist(n, INF);
    queue<int> que;
    dist[s] = 0;
    que.push(s);
    while(que.size()) {
        auto cur = que.front(); que.pop();
        for(auto i : Hen[cur]) {
            if(dist[i] != INF || pair<int,int>(cur, i) == dam)continue;
            dist[i] = dist[cur] + 1;
            que.push(i);
        }
    }
    return dist;
}


/***********debug tools***********/
template<typename A, typename B> ostream& operator<<(ostream& os, const pair<A,B>& p){os << "{" << p.first << "," << p.second << "}";return os; }
template<typename A, typename B> inline void print(pair<A,B> p){cerr << p << endl;}
template<class T> inline void print(vector<T> arr) {cerr << "["; for(int i = 0; i < (int)arr.size(); i++)cerr << arr[i] << (i == (int)arr.size() - 1 ? "]" : ",");cerr << endl;}
template<class T> inline void print(vector<vector<T>> arr) {cerr << "[-------------------" << endl; for(int i = 0; i < (int)arr.size(); i++) { print(arr[i]);} cerr << "-------------------]" << endl;}
/*********************************/


int main()
{
    int n, m; cin >> n >> m;
    vector<vector<int>> hen(n), ot(n);
    for(int i = 0; i < m; i++){
        int a, b; cin >> a >> b; a--,b--;
        hen[a].push_back(b);
        ot[b].push_back(a);
    }

    int nax = INF;
    pair<int,int> ai;
    

    for(int u = 0; u < n; u++) {
        for(auto v: hen[u]) {
            pair<int,int> voi = {u, v};
            int dist = BFS(hen, v, voi)[u];
            if(dist < nax) {
                ai = voi;
                nax = dist;
            }
        }
    }
    if(nax == INF) {
        cout << -1 << endl;
        return 0;
    }

    vector<int> dist = BFS(hen, ai.second, ai);
    vector<int> path = {ai.first};
    int vert = ai.first;
    while(dist[vert] != 0) {

        for(auto i : ot[vert]) {
            if(dist[i] == dist[vert] - 1) {
                path.push_back(i);
                vert = i;
                break;
            }
        }
    }
    reverse(path.begin(), path.end());
    cout << path.size() << endl;
    for(auto i : path)cout << i + 1 << endl;
}

Measured memory_bytes: 3776
use std::io::*;
use std::str::FromStr;

const MOD: usize = 1_000_000_007;

fn main() {
    let n: usize = read();
    let m: usize = read();
    let s: Vec<usize> = (0..n).map(|_| read()).collect();
    let t: Vec<usize> = (0..m).map(|_| read()).collect();

    let mut dp: Vec<Vec<usize>> = vec![vec![0; m+1]; n+1];
    for i in 0..n {
        for j in 0..m {
            if s[i] == t[j] {
                dp[i+1][j+1] += dp[i][j] + 1;
                dp[i+1][j+1] %= MOD;
            }
            dp[i+1][j+1] += dp[i+1][j] + dp[i][j+1];
            dp[i+1][j+1] %= MOD;
            dp[i+1][j+1] += MOD - dp[i][j];
            dp[i+1][j+1] %= MOD;
        }
    }/*
    for i in 0..n {
        for j in 0..m {
            print!("{} ", dp[i+1][j+1]);
        }
        println!();
    }*/
    println!("{}", dp[n][m] + 1);
}

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}


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

int main() {
    int n;
    cin >> n;
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        if (a != i + 1) cnt++;
    }
    if (cnt <= 2) cout << "YES" << endl;
    else cout << "NO" << endl;
}   

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

#define F first
#define S second
#define prev azaza
#define MP make_pair
#define PB push_back

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

const int max_n = 1, inf = 1000111222;

int sumd(ll a) {
    int ans = 0;
    while (a) {
        ans += a % 10;
        a /= 10;
    }
    return ans;
}

bool is_sn(ll a) {
    int suma = sumd(a);
    for (int i = a + 1; i < a + 10000; ++i) {
        int b = i;
        int sumb = sumd(b);
        if (a * sumb > b * suma) return false;
    }
    return true;
}

bool is_sn1(ll a, ll add) {
   // cout << "=-===" << endl;
    ll suma = sumd(a);
    //cout << a << endl;
    for (int i = 0; i <= 1000; ++i) {
        ll b = a + add * i;
        //cout << b << endl;
        ll sumb = sumd(b);
        if (a * sumb > b * suma) return false;
    }
    return true;
}

int main()
{
    //freopen("input.txt", "r", stdin);

    int k;
    cin >> k;
    for (int i = 1; i <= 1000; ++i) {
        if (k == 0) return 0;
        if (is_sn(i)) {
            k--;
            cout <<i  << endl;
        }
    }
    ll dev = 9;
    ll add = 10;
    for (int cnt9 = 2; cnt9 < 65; ++cnt9) {
        if (k == 0) return 0;
        for (int i = 100; i <= 999; ++i) {
            ll a = i * add + dev;
            //cout << a << endl;
            if (k == 0) return 0;
            if (is_sn1(a, add)) {
                --k;
                cout << a << endl;
            }
        }
        dev = dev + add * 9;
        add *= 10;
    }
    return 0;
}




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

#define rep(i, a) for (int i = 0; i < (int)a; ++i)
#define REP(i, a, b) for (int i = (a); i < (int)b; ++i)
// debug methods
// usage: debug(x,y);
#define CHOOSE(a) CHOOSE2 a
#define CHOOSE2(a0, a1, a2, a3, a4, x, ...) x
#define debug_1(x1) cout << #x1 << ": " << x1 << endl
#define debug_2(x1, x2) cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << endl
#define debug_3(x1, x2, x3) cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " << x3 << endl
#define debug_4(x1, x2, x3, x4) cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " << x3 << ", " #x4 << ": " << x4 << endl
#define debug_5(x1, x2, x3, x4, x5) cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " << x3 << ", " #x4 << ": " << x4 << ", " #x5 << ": " << x5 << endl
#ifdef _DEBUG
#define debug(...) CHOOSE((__VA_ARGS__, debug_5, debug_4, debug_3, debug_2, debug_1, ~)) (__VA_ARGS__)
#else
#define debug(...)
#endif

using namespace std;
using ll = long long;
using P = pair<int, int>;

void Main() {
  int a, b;
  cin >> a >> b;
  if ((a+b)%2==1) {
    cout << "IMPOSSIBLE" << endl;
    return;
  }
  cout << (a+b)/2 << endl;
}

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


Measured memory_bytes: 256
#include <cstdio>
#include <stack>
#include <set>
#include <cmath>
#include <map>
#include <time.h>
#include <vector>
#include <iostream>
#include <string>
#include <algorithm>
#include <memory.h>
#include <cstdlib>
#include <queue>
#include <iomanip>
#define P pair<int, int>
#define LL long long
#define LD long double
#define PLL pair<LL, LL>
#define mset(a, b) memset(a, b, sizeof(a))
#define rep(i, a, b) for (int i = a; i < b; i++)
#define PI acos(-1.0)
#define random(x) rand() % x
using namespace std;
const int inf = 0x3f3f3f3f;
const LL __64inf = 0x3f3f3f3f3f3f3f3f;
const int MAX = 1e5 + 5;
const int Mod = 1e9 + 7;

int n, m, s, t;
vector<int> E[MAX];
bool  used[MAX][3];
int main()
{
    cin >> n >> m;
    rep(i, 0, m)
    {
        int u, v;
        cin >> u >> v;
        E[u].push_back(v);
    }
    cin >> s >> t;
    queue<P> Q;
    Q.push({s, 0});
    used[s][0] = 1;
    while(!Q.empty()){
        int u = Q.front().first;
        int dep = Q.front().second;
        Q.pop();
        if(u == t && dep % 3 == 0){
            cout << dep/3 << endl;
            return 0;
        }
        int t_dep = (1 + dep) % 3;
        for(int i = 0; i < E[u].size(); i++){
            int v = E[u][i];
            if(used[v][t_dep])
                continue;
            else{
                used[v][t_dep] = 1;
                Q.push({v, dep+1});
            }
        }
    }
    puts("-1");
    return 0;
}

Measured memory_bytes: 6524
/*
      Ashraful Islam Paran
      15-August-2020
      17:57:36
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define f(i, x, n) for (int i = x; i < n; i++)
#define fb(i, x, n) for (int i = n - 1; i >= 0; i--)
#define w(t) int t; cin >> t; while (t--)



typedef unsigned long long ull;
typedef vector<long long> vi;
#define ull unsigned long long
#define msi map<string, long long>
#define mii map<long long, long long>
const int MX = 2e5 + 5;
const int INF = 1e18;
#define pb push_back
#define endl "\n"
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define all(x) x.begin(), x.end()
#define ff first
#define ss second


int32_t main()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    // online submission
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    string s;
    cin >> s;
    int cnt{0};
    int mx = 0;
    f(i,0,s.size())
    {
        if(s[i]=='R')
        {
            cnt++;
            mx = max(mx, cnt);
        }
        else
        {
            cnt = 0;
        }
        
    }
    cout << mx << endl;

    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
    return 0;
}

Measured memory_bytes: 3788
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
using namespace std;
typedef long long  ll;
#define rep(i,s,n)for(ll i=s;i<n;i++)
#define repe(i,s,n)for(ll i=s;i<=n;i++)
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
using namespace std;
typedef long long  ll;
#define rep(i,s,n)for(ll i=s;i<n;i++)
#define repe(i,s,n)for(ll i=s;i<=n;i++)

int main() {
	string s; cin >> s;
	rep(i, 0, s.size() - 1) {
		if (s[i] == s[i + 1]) {
			cout << i + 1 << " " << i + 2 << endl;
			return 0;
		}
		else if (i != s.size() - 2 && s[i] == s[i + 2]) {
			cout << i + 1 << " " << i + 3 << endl;
			return 0;
		}
	}

	cout << -1 << " " << -1 << endl;
	return 0;
}

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

int main()
{
	int N, l = 0, r = 0, ml = 0, mr = 0;
	string S;
	cin >> N >> S;
	for (int i = 0; i < N; i++) {
		if (S[i] == '(') {
			l++;
		}
		else {
			r++;
		}
	}
	for (int i = 0, cnt = 0; i < N; i++) {
		if (S[i] == ')') {
			cnt++;
		}
		else {
			cnt--;
		}
		ml = max(ml, cnt);
	}
	for (int i = N - 1, cnt = 0; i >= 0; i--) {
		if (S[i] == '(') {
			cnt++;
		}
		else {
			cnt--;
		}
		mr = max(mr, cnt);
	}
	if (ml + l <= mr + r) {
		ml += mr + r - ml - l;
	}
	else {
		mr += ml + l - mr - r;
	}
	cout << string(ml, '(') << S << string(mr, ')') << endl;
	return 0;
}


Measured memory_bytes: 256
N = int(input())
H = list(map(int,input().split()))

if N == 1:
    print("Yes")
else:
    for i in list(range(N)[::-1]):
        if i == 0:
            print("Yes")
            break

        if H[i] < H[i-1]:
            if H[i-1] - H[i] == 1:
                H[i-1] -= 1
            else:
                print("No")
                break

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

int main()
{
	int N,sum;
	cin >> N;
	sum = 0;


	for (int i = 0; i < N; i++) {
		int l, r;
		cin >> l >> r;
		sum += (r - l +1);
	}

	cout << sum << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int M=200010;
long long a[M],b[M],n,i,l,r;
int main()
{
	cin>>n; 
	for(i=1;i<=n;i++)
		cin>>a[i]>>b[i];
	sort(a+1,a+n+1);
	sort(b+1,b+n+1);
	if(n%2==1)
	{
		l=a[(n+1)/2];
		r=b[(n+1)/2];
		cout<<r-l+1<<endl;
	}
	else
	{
		l=(a[n/2]+a[n/2+1]);
		r=(b[n/2]+b[n/2+1]);
		cout<<r-l+1;
	}
	return 0;
}


Measured memory_bytes: 6684
import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int i = 1; //一つの整数nが一行に与えられる。
        while(true){
            int x = i;
            if (x % 3 == 0){ //３で割り切れるなら表示
                System.out.print(" " + i);//一行で出力する。
            }
            else{
                while(true){
                    if(x % 10 == 3){ //xを10で割った時余りが3になるときは表示
                        System.out.print(" " + i); //一行で出力する。
                        break;
                    }
                    x /= 10; // x=x/10をしてxが0になるときは動作終わり。
                    if( x == 0 ){
                        break;
                    }
                }
            }
            if(++i <= n){ //iを１ずつ増やしてもnより小さければスキップ
                continue;
            }
            else{
                break;
            }
        }
        System.out.println();
    }
}


Measured memory_bytes: 28884
#include <bits/stdc++.h>
     
#define all(A) begin(A), end(A)
#define rall(A) rbegin(A), rend(A)
#define sz(A) int(A.size())
#define pb push_back
#define mp make_pair
     
using namespace std;
     
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector <int> vi;
typedef vector <ll> vll;
typedef vector <pii> vpii;
typedef vector <pll> vpll;

int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  ll n, k;
  cin >> n >> k;
  vi a(n);
  for (auto& x: a) cin >> x;
  double l = 1, r = 1e9;
  for (int i = 0; i < 60; i++) {
    ll need = 0;
    double m = (l + r) / 2;
    for (auto ai: a) {
      need += floor(ai / m);
    }
    if (need <= k) r = m;
    else l = m;
  }
  cout << int(ceil(l)) << '\n';
  return (0);
}


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

int main(){
    deque<int> dq;
    int a,b;
    string s;
    while(cin >> s){
        if(s.at(0)=='+'){
            a=dq.back();
            dq.pop_back();
            b=dq.back();
            dq.pop_back();
            dq.push_back(a+b);
        }
        else if(s.at(0)=='-'){
            b=dq.back();
            dq.pop_back();
            a=dq.back();
            dq.pop_back();
            dq.push_back(a-b);
        }
        else if(s.at(0)=='*'){
            a=dq.back();
            dq.pop_back();
            b=dq.back();
            dq.pop_back();
            dq.push_back(a*b);
        }
        else{
            dq.push_back(atoi(s.c_str()));
        }
    }
    cout << dq.front() << endl;
}


Measured memory_bytes: 3156
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
long long int ans=0;
for(int i=1;i<=n;i++)
{
	for(int j=1;j<=n;j++)
	{
		if(i*j<n)
		ans++;
		else
		break;
	}
}
cout<<ans<<endl;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=(ll)1e9+7;

int main() {
    string S,T; int K;
    cin>>S>>K;
    T=S;
    for (int i = 0; i < S.length(); ++i) {
        if(S[i]=='a') continue;

        if('z'-S[i]+1<=K) {
            T[i]='a';
            K-='z'-S[i]+1;
        }
    }

    int amari=K%26;
    //cout<<amari<<endl;
    if(amari<='z'-T[S.length()-1]){
        T[S.length()-1]+=amari;
    }else{
        T[S.length()-1]='a'+amari-('z'-T[S.length()-1]+1);
    }

    cout<<T<<endl;

    return 0;
}


Measured memory_bytes: 512
a = int(input())
b = int(input())
c = int(input())
x = int(input())
count = 0
for i in range(a+1):
    l = x - i*500
    if l == 0:
        count += 1
        break
    if l < 0:
        break
    for j in range(b+1):
        if (l - j * 100) / 50 <= c and (l - j*100) >= 0:
            count += 1
print(str(count))

Measured memory_bytes: 3064
from heapq import heapify, heappop
from collections import deque

x, y, a, b, c = list(map(int, input().split(' ')))
p = list(map(int, input().split(' ')))
q = list(map(int, input().split(' ')))
r = list(map(lambda x: -1 * int(x), input().split(' ')))

p = sorted(p, reverse=True)
q = sorted(q, reverse=True)

s = p[:x] + q[:y]
s.sort()

heapify(r)

for i, _s in enumerate(s):
    if len(r) == 0:
        break

    n = -1 * heappop(r)
    if n > _s:
        s[i] = n

print(sum(s))


Measured memory_bytes: 23616
from math import ceil

R, G, B, n = map(int, input().split())
rm = ceil(n / R)
gm = ceil(n / G)
bm = ceil(n / B)
ans = 0
for r in range(rm+1):
    for g in range(gm+1):
        x = n-(r*R+g*G)
        if x >= 0:
            ans += (x%B == 0)

print(ans)


Measured memory_bytes: 68024
import fractions
n = int(input())
A = list(map(int,input().rstrip().split(' ')))
def lcm(a,b):
  return int(a*b//fractions.gcd(a,b))
L=1
for x in A:
  L=lcm(L,x)
L-=1
ans=0
for x in A:
  ans+=L%x
print(ans)


Measured memory_bytes: 5344
#include<bits/stdc++.h>
using namespace std;
pair<int,int> pii;
vector<int> vec;
int main()
{
  int n,sum=0,min=1000000000;
  int x[105];
  cin>>n;
  for(int i=0; i<n; i++){
    cin>>x[i];
  }
  sort(x,x+n);
  
  for(int i=x[0]; i<=x[n-1]; i++){
    sum=0;
    for(int j=0; j<n; j++){
      sum+=((x[j]-i)*(x[j]-i));
    }
    if(min>sum)min=sum;
  }

  cout<<min<<'\n';
  return 0;
}


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

int main() {
  int N, D;
  cin >> N >> D;
  vector<vector<long long>> x(N, vector<long long>(D));
  for (int i = 0; i < N; ++i) for (int j = 0; j < D; ++j) cin >> x[i][j];
  
  long long res = 0;
  for (int i = 0; i < N; ++i) {
    for (int j = i+1; j < N; ++j) {
      long long dis = 0;
      for (int d = 0; d < D; ++d) dis += (x[i][d] - x[j][d]) * (x[i][d] - x[j][d]);
      long long s = (long long)(sqrt(dis) + 0.1);
      if (s*s == dis) ++res;
    }
  }
  cout << res << endl;
}

Measured memory_bytes: 3608
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll c[200005];
ll  gg;
void com(){
	c[0]=0;
	c[1]=0;
	c[2]=1;
	ll k;
	for (ll i=3;i<=200000;i++){
		k=(i-1)*i/2;
		c[i]=k;
		//if (i>190000) printf("%lld\n",k);
	}
}
int n,a[200005];
int num[200005];
ll ans;
ll vers;
int m;
int main(){
	com();
	cin>>n;
	for (int i=1;i<=n;i++){
		cin>>m;
		a[i]=m;
		num[m]++;
	}
	ans=0;
	for (int i=1;i<=200000;i++){
		ans+=c[num[i]];
	}
	for (int i=1;i<=n;i++){
		vers=ans-c[num[a[i]]]+c[num[a[i]]-1];
		cout<<vers<<endl;
	}
	return 0;
}

Measured memory_bytes: 5248
#include<bits/stdc++.h>
#include<boost/variant.hpp>
using namespace std;
typedef long long ll;
typedef vector<boost::variant<bool, ll, int, string, double, char*, const char*>> any;
template<typename T> inline void pr(const vector<T> &xs){
	for(int i=0; i<xs.size()-1; i++) cout<<xs[i]<<" ";
	(xs.empty()?cout:(cout<<xs[xs.size()-1]))<<endl;
}
#ifdef DEBUG
#define debug(...) pr(any{__VA_ARGS__})
#define debugv(x) pr((x))
#else
#define debug(...)
#define debugv(x)
#endif

struct mint {
	typedef long long ll;
	ll x, m;
	mint(ll x=0, ll m=1e9+7): x(x%m), m(m) {}
	mint operator-() const { return mint(m-x, m); }
	mint operator+(const mint o) const { return mint(x+o.x, m); }
	mint operator-(const mint o) const { return mint(x-o.x+m, m); }
	mint operator*(const mint o) const { return mint(x*o.x, m); }
	mint& operator+=(const mint o) { x = (x+o.x)%m; return *this; }
	mint& operator-=(const mint o) { x = (x-o.x+m)%m; return *this; }
	mint& operator*=(const mint o) { x = x*o.x%m; return *this; }
	bool operator==(const mint o) const { return x==o.x; }
	bool operator!=(const mint o) const { return x!=o.x; }
	template<typename T> mint& operator=(const T o) { x = o%m; return *this; }
	template<typename T> mint operator+(const T o) const { return mint(x+o, m); }
	template<typename T> mint operator-(const T o) const { return mint(x-((ll)o)%m+m, m); }
	template<typename T> mint operator*(const T o) const { return mint(x*o, m); }
	template<typename T> mint& operator+=(const T o) { x = (x+(ll)o%m)%m; return *this; }
	template<typename T> mint& operator-=(const T o) { x = (x-((ll)o)%m+m)%m; return *this; }
	template<typename T> mint& operator*=(const T o) { x = x*((ll)o%m)%m; return *this; }
	template<typename T> bool operator==(const T o) const { return x==o%m; }
	template<typename T> bool operator!=(const T o) const { return x!=o%m; }

	mint pow(ll k) const {
		if(k==0) return mint(1, m);
		if(k%2) return pow(k-1)*x;
		mint z = pow(k/2);
		return z*z;
	}

	mint inv() const { return pow(m-2); }
};

int _main(){
	for(auto x: std::vector<int>{3, 5, 7, 11, 13, 17, 19}){
		assert((mint(4, x)*mint(4, x).inv())==1);
	}
	return 0;
}

int main(){
	ll N, A, B;
	cin >> N >> A >> B;

	mint ans = mint(2).pow(N) - 1;
	mint xa = mint(1);
	for(int i=0; i<A; i++){
		xa *= mint(N-i) * mint(i+1).inv();
	}
	ans -= xa;
	mint xb = mint(1);
	for(int i=0; i<B; i++){
		xb *= mint(N-i) * mint(i+1).inv();
	}
	ans -= xb;
	cout << ans.x << endl;

	return 0;
}


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

int main(int argc, char **argv)
{
	ll n, m;
	cin >> n >> m;
	vector<ll> l(m), r(m);
	for (int i = 0; i < m; ++i)
		cin >> l[i] >> r[i];

	ll begin{LLONG_MIN}, end{LLONG_MAX};
	for (int i = 0; i < m; ++i)
	{
		begin = max(begin, l[i]);
		end = min(end, r[i]);
	}

	if (begin <= end)
		std::cout << end - begin + 1 << std::endl;
	else
		std::cout << 0 << std::endl;
	
}


Measured memory_bytes: 1792
#include <stdio.h>
int main(){
	int r,c;
	int i,j;
	int rc[110][110];
	int SUM;
	scanf("%d %d",&r,&c);
	for(i=0;i<r;i++){
		SUM=0;
		for(j=0;j<c;j++){
			scanf("%d",&rc[i][j]);
			SUM+=rc[i][j];
		}
		rc[i][c]=SUM;
	}
	for(i=0;i<c+1;i++){
		SUM=0;
		for(j=0;j<r;j++){
			SUM+=rc[j][i];
		}
		rc[r][i]=SUM;
	}
	for(i=0;i<r+1;i++){
		for(j=0;j<c+1;j++){
			if(j!=0) printf(" ");
			printf("%d",rc[i][j]);
		}
		puts("");
	}
	return 0;
}

Measured memory_bytes: 660
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        int mod = (int)1e9 + 7;
        
        Combination com = new Combination(2000);
        
        int A = Math.min(N-K+1, K);
        long ans = 0;
        for(int i = 1; i <= A; i++){
            ans = com.nCk(N-K+1,i) * com.nCk(K-1,i-1) % mod;
            System.out.println(ans);
        }
        
        for(int i = 0; i < K-A; i++){
            System.out.println(0);
        }
        
    }
}

class Combination {

    long factorial[];
    long inverse[];
    int MOD;

    public Combination(int size){
        this(size, (int)1e9 + 7);
    }

    public Combination(int size, int mod){
        this.factorial = new long[size + 1];
        this.inverse = new long[size + 1];
        this.MOD = mod;

        this.factorial[0] = 1;
        this.inverse[0] = 1;

        for(int i = 1; i <= size; i++){
            factorial[i] = (factorial[i-1] * i) % MOD;
            inverse[i] = pow(factorial[i], (int) MOD - 2 ) % MOD;
        }
    }

    long nCk(int n, int k){
        return factorial[n] * inverse[k] % MOD * inverse[n-k] % MOD;
    }

    long nPk(int n, int k){
        return factorial[n] * inverse[n-k] % MOD;
    }

    private long pow(long x, int n){
        long ans = 1;
        while(n > 0){
            if( (n & 1) == 1 ){
                ans = ans * x % MOD;
            }
            n >>= 1;
            x = x * x % MOD;
        }

        return ans;
    }
}


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

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


int main(){
  ll n, m, l;
  cin >> n >> m >> l;
  ll a[105][105], b[105][105];
  rep(i,n)rep(j,m) cin >> a[i][j];
  rep(i,m)rep(j,l) cin >> b[i][j];

  rep(i, n){
    rep(j,l){
      ll c = 0;
      rep(k, m){
        c += a[i][k] * b[k][j];
      }
      cout << c;
      if(j != l-1) cout << " ";
    }
    cout << endl;
  }  
}






Measured memory_bytes: 3172
/*  -*- coding: utf-8 -*-
 *
 * b.cc: B: NarrowRectanglesEasy
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

/* typedef */

/* global variables */

/* subroutines */

/* main */

int main() {
  int w, a0, b0;
  cin >> w >> a0 >> b0;
  int a1 = a0 + w, b1 = b0 + w;

  int d = (a1 < b0) ? b0 - a1 : (b1 < a0) ? a0 - b1 : 0;
  printf("%d\n", d);
  return 0;
}


Measured memory_bytes: 256
N, M, K = map(int, input().split())
mod = 998244353
 
inv = [0,1]
for i in range(2, N):
  inv.append((-inv[mod%i]*(mod//i))%mod)
 
if N == 1:
  print(M)
  exit()
 
m = [1]
s = 1
for _ in range(N-1):
  s = s*(M-1)%mod
  m.append(s)
 
ncombi = [1]
c = 1
for k in range(K):
  c = c*(N-1-k)*inv[k+1]
  c %= mod
  ncombi.append(c)
 
ans = 0
for k in range(K+1):
  ans = ans + m[-k -1]*ncombi[k]
  ans %= mod
 
ans = ans*M%mod
print(ans)

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

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

    int n;
    cin >> n;
    int k;
    cin >> k;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        if (a >= k) ans++;
    }

    cout << ans << endl;
}


Measured memory_bytes: 892
while(True):
  loopNum = int(input())
  if loopNum == 0 :
    break
  firstScore = 0
  secondScore = 0
  for i in range(loopNum):
    scoreList = list(map(int,input().split()))
    firstNum, secondNum = scoreList
    if firstNum > secondNum:
      firstScore += firstNum + secondNum
    elif firstNum < secondNum:
      secondScore += firstNum + secondNum  
    else :
      firstScore += firstNum
      secondScore += secondNum
  print(firstScore,secondScore)


Measured memory_bytes: 5616
#include <iostream>
#include <string>
#include <vector>
#include <queue>

using namespace std;

string str;


int n;
vector<int> index;
priority_queue<int> diff;

void solve()
{   
    index.push_back(-1);
    for(int i = 0; i < str.length(); i++)
    {
        if(str[i] != 'A' && str[i] != 'C' && str[i] != 'G' && str[i] != 'T'){
            index.push_back(i);
            //cout << i << endl;
        }
    }
    index.push_back(str.length());
    for(int i = 0; i < index.size() - 1; i++){
        diff.push(index[i+1] - index[i] - 1);
        //cout << index[i+1] - index[i] << endl;
    }

    
    cout << diff.top() << endl;
    
}

int main()
{
    cin >> str;

    solve();

    return EXIT_SUCCESS;
}

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

#define _USE_MATH_DEFINES
#include<cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iterator>
#include<iomanip>
#include<unordered_set>
#include<unordered_map>
#include<bitset>
#include<complex>

using namespace std;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

#define int ll
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

//typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;
typedef vector< vector<int> > mat;

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 (b < a) { a = b; return true; } return false; }

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD =  (int)1e9 + 7;
const double EPS = 1e-9;

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

	int N;
	cin >> N;

	set<int> ans;

	set<int> dset;
	rep(i, 1, sqrt(N) + 1)
	{
		if (N%i == 0)
		{
			dset.insert(i);
			if (i < (N / i))dset.insert(N / i);
		}
	}

	for (auto d : dset)
	{
		if (d == 1)continue;
		int tN = N;
		while (tN%d == 0)tN /= d;
		if ((tN - 1) % d == 0)ans.insert(d);
	}

	N--;
	rep(i, 1, sqrt(N) + 1)
	{
		if (N%i == 0)
		{
			ans.insert(i);
			if (i < (N / i))ans.insert(N / i);
		}
	}

	if (ans.find(1) == ans.end())
	{
		cout << SZ(ans) << endl;
	}
	else
	{
		cout << SZ(ans)-1 << endl;
	}

	return 0;
}

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

int main(void){
    int n = 0;
    char s[51][100];
    char x[101];
    int t[51];
    int last = 0;
    int ans = 0;

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

    for(int i = 0; i < n; i++){
        if(strcmp(x, s[i]) == 0){ 
            last = i;
        }
    }

    for(int i = last + 1; i < n; i++){
        ans += t[i];
    }

    printf("%d\n", ans);


    return 0;

} 


Measured memory_bytes: 256
N = int(input())
hs = list(map(int, input().split()))

costs = [0 for _ in range(N)]
costs[0] = 0
costs[1] = abs(hs[0] - hs[1])

for i in range(2, N):
  costs[i] = min(costs[i-2] + abs(hs[i] - hs[i-2]), \
                 costs[i-1] + abs(hs[i] - hs[i-1]))

print(costs[N-1])


Measured memory_bytes: 52720
#![allow(unused_imports)]
#![allow(non_snake_case, unused)]

use std::cmp::*;
use std::collections::*;
use std::ops::*;

// https://atcoder.jp/contests/hokudai-hitachi2019-1/submissions/10518254

macro_rules! eprint {
	($($t:tt)*) => {{
		use ::std::io::Write;
		let _ = write!(::std::io::stderr(), $($t)*);
	}};
}
macro_rules! eprintln {
	() => { eprintln!(""); };
	($($t:tt)*) => {{
		use ::std::io::Write;
		let _ = writeln!(::std::io::stderr(), $($t)*);
	}};
}
macro_rules! dbg {
	($v:expr) => {{
		let val = $v;
		eprintln!("[{}:{}] {} = {:?}", file!(), line!(), stringify!($v), val);
		val
	}}
}

macro_rules! mat {
	($($e:expr),*) => { Vec::from(vec![$($e),*]) };
	($($e:expr,)*) => { Vec::from(vec![$($e),*]) };
	($e:expr; $d:expr) => { Vec::from(vec![$e; $d]) };
	($e:expr; $d:expr $(; $ds:expr)+) => { Vec::from(vec![mat![$e $(; $ds)*]; $d]) };
}

macro_rules! ok {
	($a:ident$([$i:expr])*.$f:ident()$(@$t:ident)*) => {
		$a$([$i])*.$f($($t),*)
	};
	($a:ident$([$i:expr])*.$f:ident($e:expr$(,$es:expr)*)$(@$t:ident)*) => { {
		let t = $e;
		ok!($a$([$i])*.$f($($es),*)$(@$t)*@t)
	} };
}

pub fn readln() -> String {
	let mut line = String::new();
	::std::io::stdin().read_line(&mut line).unwrap_or_else(|e| panic!("{}", e));
	line
}

macro_rules! read {
	($($t:tt),*; $n:expr) => {{
		let stdin = ::std::io::stdin();
		let ret = ::std::io::BufRead::lines(stdin.lock()).take($n).map(|line| {
			let line = line.unwrap();
			let mut it = line.split_whitespace();
			_read!(it; $($t),*)
		}).collect::<Vec<_>>();
		ret
	}};
	($($t:tt),*) => {{
		let line = readln();
		let mut it = line.split_whitespace();
		_read!(it; $($t),*)
	}};
}

macro_rules! _read {
	($it:ident; [char]) => {
		_read!($it; String).chars().collect::<Vec<_>>()
	};
	($it:ident; [u8]) => {
		Vec::from(_read!($it; String).into_bytes())
	};
	($it:ident; usize1) => {
		$it.next().unwrap_or_else(|| panic!("input mismatch")).parse::<usize>().unwrap_or_else(|e| panic!("{}", e)) - 1
	};
	($it:ident; [usize1]) => {
		$it.map(|s| s.parse::<usize>().unwrap_or_else(|e| panic!("{}", e)) - 1).collect::<Vec<_>>()
	};
	($it:ident; [$t:ty]) => {
		$it.map(|s| s.parse::<$t>().unwrap_or_else(|e| panic!("{}", e))).collect::<Vec<_>>()
	};
	($it:ident; $t:ty) => {
		$it.next().unwrap_or_else(|| panic!("input mismatch")).parse::<$t>().unwrap_or_else(|e| panic!("{}", e))
	};
	($it:ident; $($t:tt),+) => {
		($(_read!($it; $t)),*)
	};
}


pub fn main() {
	let _ = ::std::thread::Builder::new().name("run".to_string()).stack_size(32 * 1024 * 1024).spawn(run).unwrap().join();
}

const MOD: i64 = 1_000_000_007;
const INF: i64 = std::i64::MAX/3;

fn solve() {
	let s = read!(String);
	for c in s.chars() {
		if c=='?' {
			print!("D");
		}
		else {
			print!("{}",c);
		}
	}
	println!();
}

fn run() {
    solve();
}


Measured memory_bytes: 2324
#ifdef __APPLE__
#include <iostream>
#include <vector>
#include <utility>
#include <stack>
#include <queue>
#include <set>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <random>
#else
#include <bits/stdc++.h>
#endif

using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef vector<long long int> VLLI;
typedef vector<pair<int, int> > VPI;
typedef long long ll;
typedef pair<int,int> PII;
mt19937 mrand(random_device{}()); 
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
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;}
// head

bool hasSt(string& row) {
    for (auto x : row) {
        if (x =='#')
            return true;
    }
    return false;
}

int main() {
    int h, w, k;
    cin >> h >> w >> k;
    vector<string> mat(h);
    vector<vector<int>> ans(h, vector<int>(w));
    for (int i = 0; i < h; i++) {
        cin >> mat[i];
    }

    int p = 1, seen;
    bool s = false;

    for (int i = 0; i < h; i++) {
        if (hasSt(mat[i])) {
            seen = 0;
            for (int j = 0; j < mat[i].size(); j++) {
                if (mat[i][j] == '#')
                    seen++;
                if (seen <= 1)
                    ans[i][j] = p;
                else
                    ans[i][j] = p+seen-1;
            }
            p += seen;
            if (!s) {
                int row = i - 1;
                while (row >= 0) {
                    for (int j = 0; j < mat[row].size(); j++) {
                        ans[row][j] = ans[i][j];
                    }
                    row--;            
                }
            }
            s = true;
        } else {
            if(s) {
                for (int j = 0; j < mat[i].size(); j++) {
                    ans[i][j] = ans[i-1][j];
                }
            }
        }
    }
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cout << ans[i][j] << " ";
        }
        cout << "\n";
    }
}



Measured memory_bytes: 1280