akhauriyash/Code-Regression huggingface dataset:
if __name__ == '__main__':
    from sys import stdin
    input = stdin.readline

    n = int(input())
    count = 0
    for i in range(1, n+1):
        if i%3!=0 and i%5!=0:
            count += i
    print(int(count))
"""
    n = input()
    for i in n:
        if i == '7':
            print('Yes')
            break
    else:
        print('No')
"""

Measured memory_bytes: 9176
unittest
{
	assert( [ "5 3", "1 2", "3 4", "5 1" ].solve == 3 );
	assert( [ "4 10", "1 2", "2 1", "1 2", "2 1", "1 2", "1 3", "1 4", "2 3", "2 4", "3 4" ].solve == 4 );
	assert( [ "10 4", "3 1", "4 1", "5 9", "2 6" ].solve == 3 );
}



import std.algorithm;
import std.conv;
import std.format;
import std.range;
import std.stdio;

void main()
{
	stdin.byLineCopy.solve.writeln;
}

auto solve( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto n = 0L;
	auto m = 0L;
	input.front.formattedRead!"%s %s"( n, m );
	auto abs = new long[ 2 ][ m ];
	foreach( ref ab; abs )
	{
		input.popFront;
		ab = input.front.split.to!( long[] );
		ab[] -= 1;
	}
	
	auto uft = UnionFindTree( n );
	foreach( ab; abs )
	{
		uft.unite( ab[ 0 ], ab[ 1 ] );
	}
	
	auto ans = 0L;
	foreach( i; 0L .. n )
	{
		ans = max( ans, uft.weight( i ) );
	}
	return ans;
}

struct UnionFindTree
{
	long[] ps;
	long[] rs;
	long   rn;
	
	this( long n )
	{
		ps.length = n;
		ps[] = -1;
		rs.length = n;
		rn = n;
	}
	
	long root( long i )
	{
		if( ps[ i ] < 0 ) return i;
		else              return ps[ i ] = root( ps[ i ] );
	}
	
	auto same( long i, long j )
	{
		return root( i ) == root( j );
	}
	
	auto unite( long i, long j )
	{
		i = root( i );
		j = root( j );
		if( i == j ) return;
		if( rs[ i ] < rs[ j ] )
		{
			ps[ j ] += ps[ i ];
			ps[ i ] = j;
		}
		else
		{
			ps[ i ] += ps[ j ];
			ps[ j ] = i;
			if( rs[ i ] == rs[ j ] ) rs[ i ]++;
		}
		rn--;
	}
	
	auto weight( long i )
	{
		return -ps[ root( i ) ];
	}
	
	auto toString()
	{
		return ps.to!( string );
	}
}


Measured memory_bytes: 10204
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  
  int n,a;
  
  cin >> n;
  a = n % 1000;
  
  if(a == 0)
    cout << "Yes" << endl;
  else if(a % 111 < 10)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}

Measured memory_bytes: 256
def p_d():
    N, K = map(int, input().split())
    *rsp, = map(int, input().split())
    li = {
        "r": 0,
        "s": 1,
        "p": 2
    }
    t = input()
    ans = 0
    for k in range(K):
        dp = [0] * 3
        for i in range(k, N, K):
            x = li[t[i]]
            NEXT = [0] * 3
            for p in range(3):
                NEXT[p] = max(dp[(p + 1) % 3], dp[(p - 1) % 3])
                if (p + 1) % 3 == x:
                    NEXT[p] += rsp[p]
            dp = NEXT
        ans += max(dp)
    print(ans)
    
p_d()

Measured memory_bytes: 45148
// Created by ...Lusifer
#include<bits/stdc++.h>
using namespace std;
 
#define pb 		push_back
#define mp 		make_pair
#define prior   priority_queue
#define MOD 	1000000007
#define INF64 	(long long)1e18
#define INF 	(int)1e9
#define PI 		3.1415926535897932384626433832795 
#define ll      long long
#define ld		long double
#define ret     return
#define NUM 	1000001
const int SIZE = 2e5+4;
void fastio(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
}

void solveTest(){
	int n;
	cin>>n;
	set<string> st;
	vector<string> v;
	for(int i=0;i<n;i++){
		string s;
		cin>>s;
		st.insert(s);
		v.push_back(s);
	}
	if(st.size()!=n){
		cout<<"No"<<endl;
		return;
	}
	int flag=0;
	for(int i=1;i<n;i++){
		string p = v[i-1];
		string c= v[i];
		if(p[p.size()-1]!=c[0]){
			flag=1;
			break;
		}
	}
	if(flag)cout<<"No"<<endl;
	else cout<<"Yes"<<endl;
	return ;
}
 
int main(){
	fastio();

	int t=1;
	//cin>>t;
	while(t--){
		solveTest();
 
	}
	return 0;
}

Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)

ans = A[0] * (-1)
cnt = 0
tmp = 0
for i in range(N):
  if cnt == 0:
    ans += A[tmp]
    cnt = 1
  else:
    ans += A[tmp]
    tmp += 1
    cnt = 0
print(ans)

Measured memory_bytes: 31444
import numpy as np
hi = np.zeros((5000,60),np.int64)
hi[0,0]=1
n,a = [int(it) for it in input().split()]
li = [int(it) for it in input().split()]
for i in li:
    hi_ = hi.copy()
    hi[i:-1,1:]+=hi_[:-1-i,:-1]
s = 0
for i in range(n):
  s+=hi[(i+1)*a,i+1]
print (s)


Measured memory_bytes: 19580
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define PB push_back
#define MP make_pair
#define ll long long

inline int toInt(string s){int v;istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x){ostringstream sout;sout<<x;return sout.str();}

int main(){
    std::ios::sync_with_stdio(false);
    string s, t;
    int chars=0, chart=0;
    cin >> s;
    cin >> t;
    vector<int> pos_s[26];
    for(int i=0;i<s.length();++i)
    {
        int c = s[i] - 'a';
        pos_s[c].push_back(i);
        chars |= 1 << c;
    }

    for(int i=0;i<26;++i)
    {
        pos_s[i].push_back(-1);
    }

    for(int i=0;i<t.length();++i)
    {
        chart |= 1 << (t[i] - 'a');
    }
    if ((chars & chart) != chart) {
        cout << -1 << endl;
        return 0;
    }

    int current_ind[26] = {};
    ll ret = 0;
    int pos = -1;
    for(int i=0;i<t.length();++i)
    {
        // dump(t[i])
        int c = t[i] - 'a';
        int next_pos;        
        while(true){
            next_pos = pos_s[c][current_ind[c]];
            if(next_pos > pos){
                pos = next_pos;
                break;
            }
            current_ind[c]++;
            next_pos = pos_s[c][current_ind[c]];
            if(next_pos == -1) break;
        }

        if(next_pos == -1)
        {
            fill(current_ind, current_ind + 26, 0);
            ret += s.length();
            next_pos = pos_s[c][0];
        }
        //dump(next_pos)
        pos = next_pos;
    }
    ret += pos + 1;
    cout << ret << endl;
}

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

bool IsPrime(long long int num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false; // 偶数はあらかじめ除く

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            // 素数ではない
            return false;
        }
    }

    // 素数である
    return true;
}

std::vector<long long int> enum_div(long long int n) {
    std::vector<long long int> ret;
    for(long long int i=1 ; i*i<=n ; ++i) {
        if(n%i == 0) {
            ret.push_back(i);
            if(i!=1 && i*i!=n) {
                ret.push_back(n/i);
            }
        }
    }
    ret.push_back(n);
    return ret;
}

int main() {
    long long int a, b, i = 0, j = 0, ans = 1;
    vector<long long int> a_div, b_div;
    cin >> a >> b;
    a_div = enum_div(a);
    b_div = enum_div(b);
    sort(a_div.begin(), a_div.end());
    sort(b_div.begin(), b_div.end());
    while(i < a_div.size() && j < b_div.size()) {
        if(a_div[i] == b_div[j]) {
            if(IsPrime(a_div[i])) ans++;
            i++;
            j++;
        } else if(a_div[i] < b_div[j]) {
            i++;
        } else {
            j++;
        }
    }
    cout << ans << endl;
}

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

#define fi first
#define se second
#define long long long
typedef pair<int,int> ii;

int main()
{
	// freopen("input.in", "r", stdin);
	int a, b, c;
	scanf("%d %d %d", &a, &b, &c);
	if(a+b+c <= 21) printf("win\n");
	else printf("bust\n");
}

Measured memory_bytes: 256
N = int(input())
x = list(map(int,input().split()))
s = sum(x)
ans1,ans2 = 0,0
for i in range(N):
    ans1 += (-x[i]+s//N)**2
    ans2 += (-x[i]+s//N+1)**2
print(min(ans1,ans2))

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int main(){
	string s;
	cin >> s;
	int num = 0;
	for(int i = 0; i < s.length(); i++){
		if(s[i] == 'C' && num == 0) num++;
		if(s[i] == 'F' && num == 1) num++;
	}
	if(num == 2) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
H, W = map(int, input().split())
S = [input() for _ in range(H)]

INF = 10 ** 18
dp = [[INF for _ in range(W)] for _ in range(H)]

if S[0][0] == "#":
    dp[0][0] = 1
else:
    dp[0][0] = 0

for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            dp[i][j] = min(dp[i][j], dp[i - 1][j], dp[i][j - 1])
        else:
            dp[i][j] = min(dp[i][j],
                            dp[i - 1][j] if S[i - 1][j] == "#" else dp[i - 1][j] + 1,
                            dp[i][j - 1] if S[i][j - 1] == "#" else dp[i][j - 1] + 1)

print(dp[-1][-1])

Measured memory_bytes: 41840
n,m,x = map(int,input().split())
li=[input() for i in range(n)]
li2 = []
for i in range(n):
    li2.append( [int(x.strip()) for x in li[i].split()])
    
ans = 10**7

for i in range(2 ** n):
    res = ""
    b = str(format(i, '012b')) #2進数に変換
    a = [0]*(m+1)
    for j in range(n):
        if b[-1-j] == "1":
            a = [x1 + x2 for (x1, x2) in zip(a, li2[j])]
           # print(a)
            
    c = len([j for j in a[1:] if j>=x])
    if c ==m and ans>a[0]:
        
        ans = a[0]
        #print(ans)

if ans == 10**7:
    print(-1)
else:
    print(ans)


Measured memory_bytes: 68996
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N;cin>>N;
  vector<long long>A(N);
  long long shou=10000000000000;
  int c=0;
  long long count=0;
  for(int i=0;i<N;i++){
    cin>>A[i];
    if(A[i]<0)c++;
    count+=abs(A[i]);
    shou=min(shou,abs(A[i]));
  }
  if(c%2==0)cout<<count<<"\n";
  else cout<<count-shou*2<<"\n";
}

Measured memory_bytes: 3984
n, m = map(int, input().split())

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

UF = UnionFind(n)

for i in range(m):
    a, b, c = map(int, input().split())
    UF.union(a-1, b-1)

print(UF.group_count())



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

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

constexpr int INF = 1e9;

constexpr int dx[4] = {0, 1, 0, -1};
constexpr int dy[4] = {1, 0, -1, 0};

int main() {
    int W, H;
    cin >> W >> H;
    vector<string> v(H);
    int s, g;
    int fcnt = 0;
    queue<int> que;
    vector<int> sd(H * W, INF);
    for(int i = 0; i < H; ++i) {
        cin >> v[i];
        for(int j = 0; j < W; ++j) {
            if(v[i][j] == 's') {
                s = i * W + j;
            } else if(v[i][j] == 'g') {
                g = i * W + j;
            } else if(v[i][j] == '*') {
                que.push(i * W + j);
                sd[i * W + j] = 0;
            }
            fcnt += v[i][j] == '.' || v[i][j] == 's';
        }
    }

    while(!que.empty()) {
        int y = que.front() / W;
        int x = que.front() % W;
        que.pop();
        for(int i = 0; i < 4; ++i) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny < 0 || H <= ny || nx < 0 || W <= nx || v[ny][nx] == '#' || v[ny][nx] == 'g' || sd[ny * W + nx] != INF) {
                continue;
            }
            sd[ny * W + nx] = sd[y * W + x] + 1;
            que.push(ny * W + nx);
        }
    }

    vector<int> gd(H * W, INF);
    que.push(g);
    gd[g] = 0;
    double total_gd = 0;
    while(!que.empty()) {
        int y = que.front() / W;
        int x = que.front() % W;
        que.pop();
        for(int i = 0; i < 4; ++i) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny < 0 || H <= ny || nx < 0 || W <= nx || v[ny][nx] == '#' || v[ny][nx] == '*' || gd[ny * W + nx] != INF) {
                continue;
            }
            gd[ny * W + nx] = gd[y * W + x] + 1;
            total_gd += gd[ny * W + nx];
            que.push(ny * W + nx);
        }
    }

    vector<pll> d;
    int scnt = 0;
    double total_sd = 0;
    for(int i = 0; i < H * W; ++i) {
        if(i == g || v[i / W][i % W] == '*' || v[i / W][i % W] == '#') {
            continue;
        }
        if(gd[i] == INF && sd[i] != INF) {
            scnt++;
            total_sd += sd[i];
        } else if(sd[i] != INF) {
            d.emplace_back(-gd[i] + sd[i], i);
        }
    }
    sort(d.begin(), d.end());

    double res = 1e18;
    auto it = d.begin();
    for(int i = -H * W; i <= H * W; ++i) {
        while(it != end(d) && it->first <= i) {
            scnt++;
            total_sd += sd[it->second];
            total_gd -= gd[it->second];
            it++;
        }
        if(scnt == fcnt) {
            continue;
        }
        double E = (total_gd + total_sd) / (1 - (double)scnt / fcnt) / fcnt;
        if(gd[s] == INF || -gd[s] + sd[s] <= i) {
            res = min(res, E + sd[s]);
        } else {
            res = min(res, (double)gd[s]);
        }
    }

    cout << fixed << setprecision(10) << res << endl;
}


Measured memory_bytes: 9436
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
#define repe(i,n) for (int i = 0; i <= (n); ++i)
#define repe1(i,n) for (int i = 0; i <= (n); ++i)
#define all(x) (x).begin(),(x).end()
#define pb(x) push_back(x)
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
typedef long long ll;
const int INF = 1e9;
const ll mod = 1000000007;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a * b / gcd(a, b);}

ll pow_kai(ll a, ll n) {
    ll x = 1;
    while(n > 0) {
        if(n&1) {
            x = x*a;
        }
        a = a*a;
        n >>= 1;
    }
    return x;
}

int main() {
    string s;
    string t;
    cin >> s >> t;
    sort(all(s));
    sort(all(t), greater<char>());
    if (s<t) {
        cout << "Yes" << "\n";
    } else {
        cout << "No" << "\n";
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<int,int> P;
const LL mod=998244353;
const LL LINF=1LL<<62;
const int INF=1<<20;


string s[12];
int h,w;
bool used[12];
int order[12];

bool check(){
    bool cc[12];
    memset(cc,false,sizeof(cc));
    string t[h];
    for (int i = 0; i < h; i++) {
        if(i%2) t[i/2]=s[order[i]];
        else t[h-i/2-1]=s[order[i]];
    }
    for (int i = 0; i < w; i++) {
        if(cc[i]) continue;
        string a="";
        for (int j = 0; j < h; j++) {
            a.pb(t[j][i]);
        }
        for (int j = i+1; j < w; j++) {
            if(cc[j]) continue;
            string b="";
            for (int k = 0; k < h; k++) {
                b.pb(t[k][j]);
            }
            reverse(ALL(b));
            if(a==b){
                cc[i]=true;
                cc[j]=true;
                break;
            }
        }
    }
    int cnt=0;
    for (int i = 0; i < w; i++) {
        cnt+=(!cc[i]);
    }
    return cnt<=1;
}

bool dfs(int m,int l){
    if(m==h){
        return check();
    }
    if(m==h-1){
        for (int i = 0; i < h; i++) {
            if(used[i]) continue;
            used[i]=1;
            order[m]=i;
            if(dfs(m+1,l)) return true;
            used[i]=0;
        }
        return false;
    }
    if(m%2){
        for (int i = l+1; i < h; i++) {
            if(used[i]) continue;
            used[i]=1;
            order[m]=i;
            if(dfs(m+1,l)) return true;
            used[i]=0;
        }
    }
    else{
        for (int i = l-1; i >= 0; i--) {
            if(used[i]) continue;
            used[i]=1;
            order[m]=i;
            if(dfs(m+1,i)) return true;
            used[i]=0;
        }
    }
    return false;
}

int main(){
    cin >> h >> w;
    for (int i = 0; i < h; i++) {
        cin >> s[i];
    }
    if(dfs(0,h)) puts("YES");
    else puts("NO");
    return 0;
}



Measured memory_bytes: 256
import numpy as np
n=int(input())
a=np.array([int(x) for x in input().split()])
b=np.array([int(x) for x in input().split()])
c=np.array([int(x) for x in input().split()])

tf = np.array([a[i+1] - a[i] == 1 for i in range(n-1)])

print(sum(b) + sum([c[j-1] for j in a[tf]]))


Measured memory_bytes: 12472
#include<iostream>
#include<complex>
#include<vector>
#include<algorithm>
#include<cmath>
#include<map>

#define EPS (1e-10)
#define EQ(a,b) (abs((a)-(b)) < EPS)
#define fs first
#define sc second
#define pb push_back
#define sz size()
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)

using namespace std;

typedef complex<double> P;
typedef pair<P,P> L;
typedef vector<P> Poly;

inline double dot(P x,P y){return real(conj(x)*y);}

inline double cross(P x,P y){return imag(conj(x)*y);}

//for line(segment)
inline int ccw(P a,P b,P c){
  b -= a;c -= a;
  if (cross(b,c)>EPS) return 1;   //counter clockwise
  if (cross(b,c)<-EPS) return -1; //clockwise
  if (dot(b, c)<-EPS) return 2;   //c--a--b on line
  if (abs(b)<abs(c)) return -2;   //a--b--c on line
  return 0;                       //on segment
}

inline P line_cp(L a,L b){
  return a.fs+(a.sc-a.fs)*cross(b.sc-b.fs,b.fs-a.fs)/cross(b.sc-b.fs,a.sc-a.fs);
}

//for polygon

//all vertex is already sorted.
inline double area(Poly &p){
  if(p.size()<3)return 0;
  double res = cross(p[p.size()-1],p[0]);
  for(int i=1;i<p.size();i++)res += cross(p[i-1],p[i]);
  return res/2;
}

//all vertex is already sorted.
inline Poly convex_cut(Poly &p,L l){
  Poly res;
  int n = p.size();
  for(int i=0;i<n;i++){
    int nxt = (i+1)%n;
    if(ccw(l.fs,l.sc,p[i]) != -1)res.pb(p[i]);
    if(ccw(l.fs,l.sc,p[i]) * ccw(l.fs,l.sc,p[nxt]) < 0){
      res.pb( line_cp(l, L(p[i],p[nxt]) ) );
    }
  }
  return res;
}

int main(){
  int n,m;
  int bx,by,dx,dy,s;
  P p[110];
  Poly vor[110];
  const int lim = 30000;
  double ans[110];

  while(cin >> n >> m,n+m){
    FOR(i,0,n)cin >> p[i].real() >> p[i].imag();
    
    FOR(i,0,n){
      ans[i] = 0.0;

      vor[i].resize(4);
      vor[i][0] = P(-lim,-lim); vor[i][1] = P(lim,-lim);
      vor[i][2] = P(lim,lim); vor[i][3] = P(-lim,lim);

      FOR(j,0,n){
	if(i!=j){
	  P nor = (p[i]-p[j]) * P(0,-1);
	  P mid = (p[i]+p[j])/2.0;
	  vor[i] = convex_cut(vor[i],L(mid,mid+nor));
	}
      }
    }
    FOR(i,0,m){
      cin >> bx >> by >> dx >> dy >> s;
      double rect = 4*dx*dy;
      Poly cut(4);
      cut[0] = P(bx-dx,by-dy); cut[1] = P(bx+dx,by-dy);
      cut[2] = P(bx+dx,by+dy); cut[3] = P(bx-dx,by+dy);
	
      FOR(j,0,n){
	Poly tmp = vor[j];
	FOR(k,0,4){
	  tmp = convex_cut(tmp,L(cut[k],cut[(k+1)%4]));

	}
	ans[j] += area(tmp)/rect*s;
      }
    }
    double res = 0.0;
    FOR(i,0,n)res = max(res,ans[i]);
    cout.setf(ios::fixed); cout.precision(9);
    cout << res << endl;
  }
}

Measured memory_bytes: 1340
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
using namespace std;
#define int long long
#define REP(i,m,n) for(int i=(m);i<(n);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define all(a) a.begin(),a.end()
#define rall(c) (c).rbegin(),(c).rend()
#define mp make_pair
#define endl '\n'
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll inf=1e9+7;
const ll mod=998244353;
signed main(){
    ll n;cin>>n;
    vector<pll>pp(0);
    vector<pll>nn(0);
    rep(i,n){
        string s;cin>>s;
        ll k=0;
        ll mi=0;
        rep(i,s.size()){
            if(s[i]=='('){
                k++;
            }else{
                k--;
            }
            mi=min(mi,k);
        }
        if(k>=0){
            pp.pb(mp(mi,k));
        }else{
        reverse(all(s));
        k=0;
        mi=0;
        rep(i,s.size()){
            if(s[i]==')'){
                k++;
            }else{
                k--;
            }
            mi=min(mi,k);
        }
        nn.pb(mp(mi,k));
        }
    }
    bool f=1;
    ll now=0;
    sort(rall(pp));
    rep(i,pp.size()){
        if(now+pp[i].first<0)f=0;
        now+=pp[i].second;
    }
    ll now2=0;
    sort(rall(nn));
    rep(i,nn.size()){
        if(now2+nn[i].first<0){
            f=0;
        }
        now2+=nn[i].second;
    }
    if(now!=now2)f=0;
    //cout<<now<<' '<<now2<<endl;
    if(f==0){
        cout<<"No"<<endl;
        return 0;
    }
    cout<<"Yes"<<endl;
}

Measured memory_bytes: 19024
#include <stdio.h>

int main(void){
    int N,oturi;
    
    scanf("%d",&N);
    if(N%1000==0){
        oturi=0;
    }else{
        oturi=1000-(N%1000);
    }
    
    printf("%d\n",oturi);
    
    return 0;
}

Measured memory_bytes: 2148
k = int(input())

num = [0] * 10
num[0] = 1
keta = 1
for i in range(k-1):
  change = 0
  for j in range(keta-1):
    if (num[j] < num[j+1]) or (num[j]==num[j+1] and num[j+1]<9):
      num[j] += 1
      change = 1
      for x in range(j, 0, -1):
        num[x-1] = max(0, num[x]-1) 
      break
  if not change:
    if num[keta-1]<9:
      num[keta-1] += 1
      for x in range(keta-1, 0, -1):
        num[x-1] = max(0, num[x]-1) 
    else:
      num[keta-1] = 0
      num[keta] = 1
      for x in range(keta, 0, -1):
          num[x-1] = max(0, num[x]-1) 
      keta += 1
  #print(num)
ans = 0
d = 1
for i in range(10):
  #print(num[i])
  ans += num[i]*d
  d *= 10
  
print(ans)       

  
  
      
  

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

int32_t main(){
    ios::sync_with_stdio(0),cin.tie(0);
    string st;
    cin >> st;
    for(auto &i:st){
        if(i=='?')i='D';
    }
    cout << st;
}

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

int main() {
	long n,k,i,j,cur,ans,jud,res;
	cin >> n >> k;
	vector<long> a(n);
	set<long> b;
	for(i=0; i<n; i++){
		cin >> a[i];
	}
	for(i=0; i<k; i++){
		b.insert(a[i]);
	}
	auto itr=b.begin();
	ans=n-k+1;
	for(i=0; i<n-k; i++){
		itr=b.begin();
		jud=0;
		if(*itr==a[i]) jud++;

		b.erase(a[i]);
		b.insert(a[i+k]);
		itr=b.end();
		itr--;

		if(*itr==a[i+k]) jud++;

		if(jud==2){
			ans--;
		}
	}
	
	res=0; cur=0;
	for(i=1; i<n; i++){
		if(a[i-1]<a[i]){
			cur++;
			if(cur==k-1) res++;
		}else{
			cur=0;
		}
		
	}
	if(res>=2){
		ans-=res-1;
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 11136
N, K = map(int, input().split())

def countZero(f):
    if f >= 0:
        return -1
    s = '{:.11f}'.format(f)
    if s.find('.') < 0:
        return -1

    n = s.split('.')[1]
    ss = str(n)
    count = 0
    for i in range(len(ss)):
        if ss[i] == '0':
            count +=1
        else:
            break
    return count
    
prob = 0
for i in range(N):
    n = N - i
    n2 = n
    count = 0
    while True:
        if n2 >=K:
            break
        count+=1
        n2 = n2*2
#     print(n, n2, count, (1/N) * pow(0.5, count))
    ans = (1/N) * pow(0.5, count)
    if countZero(ans) >= 11:
        break
    else:
        prob += ans

print(prob)

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

    using namespace std;
    typedef long long ll;
    # define M_PI  3.14159265358979323846
    const int MOD=1e9+7;

    void solve(){
        int n;
        cin>>n;
        vector<int>a(n);
        int ans=0;
        for(int i=0;i<n;i++){
            cin>>a[i];
            ans=ans^a[i];
        }
        for(int i=0;i<n;i++)
            a[i]=ans^a[i];
        for(int i=0;i<n;i++)
            cout<<a[i]<<" ";
    }
    int main(){
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        cout<<fixed;
        cout<<setprecision(10);
        int t=1;
//        cin>>t;
        for(int i=1;i<=t;i++){
            solve();
        }
        return 0;
    }


Measured memory_bytes: 3968
#include<bits/stdc++.h>
using namespace std;
int a[200005];
int b[200005];
int n;
int num=1;
int main()
{
    //freopen("input.txt","r",stdin);
    cin>>n;
    cin>>a[0];
    b[0]=a[0];
    for(int i=1;i<n;i++)
    {
    	scanf("%d",&a[i]);
    	b[i]=min(b[i-1],a[i]);
	}
	for(int i=1;i<n;i++)
	{
		if(a[i]<=b[i-1]) num++;
	}
	cout<<num<<endl;
	return 0; 
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,n-1,0)
#define REPL(i,m,n) for(ll i=(ll)(m); i<(ll)(n); i++)
#define repl(i,n) REPL(i,0,n)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N;
  cin >> N;
  vector<ll> A(N);
  bool zero = false;
  rep(i, N) {
    cin >> A[i];
    if(A[i] == 0) zero = true;
  }
  if(zero) cout << 0 << endl;
  else {
    ll large = 1000000000000000000LL;
    ll ans = 1;
    rep(i, N) {
      if(ans > LONG_LONG_MAX / A[i]) {
        cout << -1 << endl;
        return 0;
      }
      ans *= A[i];
      if(ans > large) {
        cout << -1 << endl;
        return 0;
      }
    }
    cout << ans << endl;
  }
  return 0;
}


Measured memory_bytes: 3980
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cstring>
#include <cmath>
#include <stack>
#include <iomanip>
#include <tuple>
#include <functional>
#include <cfloat>
#include <map>
#include <stdio.h>
#include <string.h>
using ll = long long;

//LLONG_MAX
#define int long long
#define CONTAINS(v,n) (find((v).begin(), (v).end(), (n)) != (v).end())
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
#define ARY_SORT(a, size) sort((a), (a)+(size))
#define REMOVE(v,a) (v.erase(remove((v).begin(), (v).end(), (a)), (v).end()))
#define REVERSE(v) (reverse((v).begin(), (v).end()))
#define LOWER_BOUND(v,a) (lower_bound((v).begin(), (v).end(), (a)))
#define UPPER_BOUND(v,a) (upper_bound((v).begin(), (v).end(), (a)))
#define REP(i, n) for (int (i)=0; (i) < (n); (i)++)
#define CONTAINS_MAP(m, a) (m).find((a)) != m.end()

using namespace std;


signed main()
{
	int N, R;
	cin >> N >> R;

	int ans = R;
	if (N < 10)
	{
		ans += (100) * (10 - N);
	}
	cout << ans << endl;
}




Measured memory_bytes: 256
from collections import defaultdict

n = int(input())
A = list(map(int, input().split()))
q = int(input())
BC = [tuple(map(int, input().split())) for _ in range(q)]
total = sum(A)
d = defaultdict(int)
for a in A:
    d[a] += 1
for b, c in BC:
    total = total - b*d[b] + c*d[b]
    d[c] += d[b]
    d[b] = 0
    print(total)


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

bool cmp(pair<int,int> a, pair<int,int> b)
{
	if( a.first == b.first ) return a.second < b.second;
	return a.first > b.first;
}

int main()
{
	int n,m;
	
	while(cin>>n>>m,n|m){
		pair<int,int> memo[100];
		for(int i=0; i<m; i++)memo[i].second = i;
		
		for(int i=0; i<n; i++){
			for(int j=0; j<m; j++){
				int a; scanf("%d",&a);
				memo[j].first += a;
				//printf(" %d,",a);
			}
			//puts("");
		}
		stable_sort(memo,memo+m,cmp);
		
		if( m>0 )printf("%d",memo[0].second+1);
		for(int i=1; i<m; i++){
			printf(" %d",memo[i].second+1);
		}
		puts("");
	}
	return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long ll;
typedef pair<ll,ll> P;
const ll mod=1000000007;
const ll LINF=1LL<<60;
const int INF=1<<30;
ll n,k;
vector<ll> a;
vector<ll> b;

ll search(ll x){
	ll res = 0LL;
	long double key;
	for(int i = 0; i < n; i++) {
		ll tmp = 0LL;
		if (a[i] == 0LL){//0のとき
			if (x >= 0LL){//基準となる値が非負なら全部オーケー
				res += n - 1;
			} 
		}
		else if(a[i] > 0){
			key = (long double)x / a[i];
			tmp += upper_bound(ALL(a),key) - a.begin();//より大きいもの-begin = x以下の数
			res += tmp;
		}
		else{
			key = (long double)x / a[i];
			tmp += (a.end() - lower_bound(ALL(a),key));
			res += tmp;
		}
	}
	res -= (upper_bound(ALL(b),x) - b.begin());
	return res /2; 
}

int main(){
	cin>>n>>k;
	ll x;
	for(int i = 0; i < n; i++) {
		cin>>x;
		a.pb(x);
		if (x != 0)b.pb(x * x);
	}
	sort(ALL(a));
	sort(ALL(b));
	ll ok = 1e18;
	ll ng = -1e18;
	ll mid;
	while(abs(ok - ng) > 1LL){
		mid = (ok + ng) / 2LL;
		if(search(mid) >= k){
			ok = mid;
		}
		else{
			ng = mid;
		}
	}
	cout << ok << endl;

	return 0;
}

Measured memory_bytes: 3688
#include <stdio.h>
#define n_max 101

int n,time=0;
int adj[n_max][n_max];
int used[n_max];
int f[n_max],d[n_max];

void dfs(int x){
  int i;
  
  for(i=1;i<=n;i++){
    if(adj[x][i]==1 && used[i]==0){
      used[i]=1;
      time++;
      d[i]=time;
      dfs(i);
    }
  }  
  f[x]=++time;  
}

int main(){
  int i,j,u,k,num;
  
  scanf("%d",&n);//ヴァーテックスの数
  for(i=0;i<n;i++){
    scanf("%d %d",&u,&k);//頂点のナンバーと、その頂点からのびる線の数
    for(j=0;j<k;j++){
      scanf("%d",&num);
      adj[u][num]=1;
    }
  }
  
  for(i=1;i<=n;i++){
    if(used[i]==0){
      d[i]=++time;
      used[i]=1;
      dfs(i);
    }
  }
  for(i=1;i<=n;i++)printf("%d %d %d\n",i,d[i],f[i]);
  return 0;
}



Measured memory_bytes: 2112
import java.util.*;

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

    String result = "";
    for(int i = 0 ; i <  S.length();  i ++){
      switch( S.charAt(i)  ){
        case '0':
          result = result + "0";
        break;
        case '1':
          result = result + "1";
        break;
        case 'B':
          if(!result.isEmpty()){
            result = result.substring(0,result.length() - 1);
          }
        break;
      }
    }
    System.out.println(result);
  }
}


Measured memory_bytes: 21844
s = gets.chomp

deleted_cube = 0
while !(index1 = s.index("01")).nil? || !(index2 = s.index("10")).nil?
  index = !index1.nil? ? index1 : index2
  s.slice!(index, 2)
  deleted_cube += 2
end
print("#{deleted_cube}\n")

Measured memory_bytes: 81040
#include<bits/stdc++.h>
#define int long long
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
static const int INF = 1ll<<60;
typedef pair<int,int> pii;

struct P{
    int p;
    int q;
    int r;
    int b;
    P(){}
    P(int p1,int p2,int p3,int p4){
        p=p1;
        q=p2;
        r=p3;
        b=p4;
    }
};

int N;
double R,B;
vector<P> S;
bool cone[110];

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

int LCM(int a,int b){
    return a*b/GCD(max(a,b),min(a,b));
}

int dfs(int n){
    if(n==-1)return 1;
    int R = dfs(S[n].r)*S[n].p;
    int B = dfs(S[n].b)*S[n].q;
    int lcm = LCM(R,B);
    return lcm/S[n].p+lcm/S[n].q;
}

signed main(){
    while(1){
        cin>>N;
        if(N==0)break;
        for(int i=0;i<N;++i){
            int p,q,r,b;
            cin>>p>>q>>r>>b;
            r--;
            b--;
            cone[r]=true;
            cone[b]=true;
            S.PB(P(p,q,r,b));
        }
        for(int i=0;i<N;++i){
            if(!cone[i]){
                cout<<dfs(i)<<endl;
                break;
            }
        }
        S.clear();
        memset(cone,0,sizeof(cone));
    }
    return 0;
}

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

int main() {
  //clock_t start, end; //開始時刻・終了時刻
  //double req_time; //所要時間
  //start = clock();
  
  int N;
  vector<int> card;
  int Alice = 0, Bob = 0;
  int ans;

  cin >> N;
  card.resize(N);
  for (int i=0; i<N; i++){
      cin >> card.at(i);
  }
  
  sort(card.begin(),card.end());
  reverse(card.begin(),card.end());
  
  for (int i=0; i<N-1; i+=2){
      Alice += card.at(i);
      Bob += card.at(i+1);
      //cout << "iterator : " << i << endl;
  }
  if(N%2==1){
      Alice += card.at(N-1);
  }

  ans = Alice - Bob;
  cout << ans << endl;

  //end = clock();
  //req_time = (double)(end-start) / CLOCKS_PER_SEC;
  //cout << req_time << endl;
  }

Measured memory_bytes: 384
#include <iostream>
#include <cstdlib>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

const int cost[9] = {2,5,5,4,5,6,3,7,6};



bool cmp_state(string a, string b){
    if(a.size() != b.size()){
        return a.size() < b.size();
    }else{
        for (int i=0;i<a.size();i++){
            if (a[i] != b[i]) return a[i] < b[i];
        }
        return true;
    }
}

signed main() {
    int N;
    int M;
    cin >> N >> M;
    int A[M];
    int B[M];
    vector<string> maxstate(N+10,"");
    for(int i=0;i<M;i++){
        cin >> A[i];
        B[i] = cost[A[i] - 1];
        maxstate[B[i]] = to_string(A[i]);
    }
    // initialize
    for (int i=0;i<N+1;i++){
        string now_maxstate = maxstate[i];
        for (int j=0;j<M;j++){
            if(i - B[j] < 0) continue;
            string pre_state = maxstate[i-B[j]];
            if(pre_state == "") continue;
            if(pre_state.size() + 1 < now_maxstate.size()) continue;
            string appended = pre_state + to_string(A[j]);
            sort(appended.begin(), appended.end(), greater<int>());
            now_maxstate = max(now_maxstate, appended, cmp_state);
        }
        maxstate[i] = now_maxstate;
    }
    cout << maxstate[N] << endl;
}


Measured memory_bytes: 26496
import Foundation

////print("Hello, World!")
//
//let input = readLine()!
////print(input)
//
//let nums = input.components(separatedBy: " ")
////print(nums)
//
//let a = Int(nums[0])!
//let b = Int(nums[1])!
//print("\(a * b)")


let input = readLine()!
let inputLast = input.dropFirst(input.count - 1)
let nums = Int(inputLast)!

if nums == 2 || nums == 4 || nums == 5 || nums == 7 || nums == 9{
    print("hon")
} else if nums == 0 || nums == 1 || nums == 6 || nums == 8 {
    print("pon")
} else {
    print("bon")
}


Measured memory_bytes: 13412
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
int main(){
    int A,B;
    cin>>A>>B;
    for(int i=1;i<=10000;i++){
        if(floor(i*0.08)==A&&floor(i*0.1)==B){
           cout<<i<<endl;
           return 0;
        }
    }
    puts("-1");
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vb = vector<bool>;
using vs = vector<string>;
using msi = map<string, int>;
using mii = map<int, int>;
using psi = pair<string, int>;
using pii = pair<int, int>;
using vlai = valarray<int>;
#define rep(i,n) for(int i=0;i<n;i++)
#define range(i,s,n) for(int i=s;i<n;i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define fs first
#define sc second
#define mp make_pair
#define INF 1E9
#define LINF 1E18*5
#define EPS 1E-9
#define MOD 1000000007
#define PI 3.1415926535897932384

template<class S, class T>ostream& operator<<(ostream&os, pair<S, T>p) { os << "[" << p.first << ", " << p.second << "]"; return os; };
template<class S>auto&operator<<(ostream&os, vector<S>t) { bool a = 1; for (auto s : t) { os << (a ? "" : " ") << s; a = 0; } return os; }

//int dx[]={1,1,1,0,-1,-1,-1,0},dy[8]={1,0,-1,-1,-1,0,1,1,1};
//
constexpr ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }

class compare {
public:
	bool operator()(tuple<int, int> a, tuple<int, int> b) {
		return (get<1>(a) < get<1>(b));
	}

};

int main() {
	int n, t;
	int mn=INF;
	cin >> n >> t;
	vi v(n),m(n);
	rep(i, n){
		cin >> v[i];
		mn = min(mn, v[i]);
		m[i] = mn;
	}
	int ans = 0;
	int dif = -1;
	rep(i, n) {
		if (dif == v[i] - m[i]) {
			ans++;
		}
		if (dif < v[i] - m[i]) {
			dif = v[i] - m[i];
			ans = 1;
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 1024
#include <iostream>
using namespace std;
int main(void){
    int A,B,C,D,E;
    cin >> A >> B >> C >> D >> E;
    int T = 0;
    
    if(A <= 0){
        int a = (-1)*A;
        T = a*C + B*E + D;
        cout << T << endl;
    }
    else{
        int b = B - A;
        T = b*E;
        cout << T << endl;
    }
   
}


Measured memory_bytes: 3084
#include <iostream>

int a, b, c, d;
int count[101];
int main()
{
  std::cin >> a >> b >> c >> d;

  for(int i=a; i<=b; i++) count[i]++;
  for(int j=c; j<=d; j++) count[j]++;

  int ans = 0;

  for (int i = 0; i<101; i++)
  {
    if (count[i]==2) ans++;
  }
  if(ans>0) ans--;
  
  std::cout << ans << '\n';
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>
#include <math.h>
#include <set>
#include <bitset>
#include <stack>
#include <cmath>
#include <iomanip>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
#define mp make_pair;

const ll prime = 1000000000 + 7;
const ld PI = 2 * acos(0.0);

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

bool my_comp(pll a, pll b) {
	if (a.first != b.first) {
		return a.first < b.first;
	}

	return a.second < b.second;
}

int main() {

	ll n;
	cin >> n;
	vector<ll> a(n), condition(3, 0);
	for (ll i = 0; i < n; i++)
	{
		cin >> a[i];
	}

	ll sum = 1, cnt;

	for (ll i = 0; i < n; i++)
	{
		cnt = 0;
		for (ll j = 0; j < 3; j++)
		{
			if (a[i] == condition[j]) {
				if (cnt == 0) {
					cnt++;
					condition[j]++;
				}
				else {
					cnt++;
				}
			}
		}
		sum *= cnt;
		sum %= prime;
	}

	cout << sum << endl;


	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<ll, ll, ll> T;

int H, W;
vector<vector<int>> A(201, vector<int>(201, 0));
const int INF = 100000000; //INT_MAXにしたらオーバーフローを起こす
vector<vector<int>> dist(201, vector<int>(201, INF)); //dist[u][v]は辺(u,v)のコスト（辺が存在しない場合はINF、ただしdist[i][i] = 0

void Warshallfloyd(int n = 10){ //nは頂点数
    for(int i = 0; i < n; i++){      // 経由する頂点
        for(int j = 0; j < n; j++){    // 開始頂点
            for(int k = 0; k < n; k++){  // 終端
                dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]);
            }
        }
    }
    return;
}

int main(void){
    
    scanf("%d %d", &H, &W);
    for(int i = 0; i <= 9; ++i){
        for(int j = 0; j <= 9; ++j){
            int a; scanf("%d", &a);
            dist[i][j] = a;
        }
    }
    for(int i = 0; i < H; ++i) for(int j = 0; j < W; ++j) scanf("%d", &A[i][j]);

    Warshallfloyd();
    
    int ans = 0;
    for(int i = 0; i < H; ++i){
        for(int j = 0; j < W; ++j){
            if(A[i][j] == -1 || A[i][j] == 1) continue;
            ans += dist[A[i][j]][1];
        }
    }
    printf("%d\n", ans);
    
    return 0;
}



Measured memory_bytes: 512
#include <algorithm>
#include <bitset>
#include <boost/multiprecision/cpp_int.hpp>
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstring>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <set>
#include <numeric>
#include <sstream>
#include <stdio.h>
#include <string>
#include <tuple>
#include <vector>
#include<iomanip>
namespace mp = boost::multiprecision;
using namespace std;
using ull = unsigned long long;
using ld = long double;
using lll = boost::multiprecision::cpp_int;
using ll = long long;
#define FOR(i, N) for(ll i = 0; i < N; ++i)

#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
// using int = ll;
ll gcd(ll m, ll n) {
    if(n == 0)
        return abs(m);
    return (gcd(n, m % n));
}
void putYN(bool b) {
    if(b) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}
ll combi(ll n, ll k) {
    ll r = 1, rr = 1;
    for(ll i = 0; i < k; ++i) {
        r *= (n - i);
        rr *= (i + 1);
        // r %= 1000000007;
        // rr %= 1000000007;
    }
    r /= rr;
    // r %= 1000000007;
    return r;
}
int main(){
  ll A,B;
  cin>>A>>B;
  cout<<A*B/gcd(A,B)<<endl;
      
  return 0;
}


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

typedef long long int ll; 
#define MOD 1000000007
#define ON 200000
#define rep(i,n) fp(i,0,n)  
#define fp(i,a,b) for(ll i=(a);i<(b);++i)
#define fn(i,a,b) for(ll i=(a);i>(b);i--)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define FF first
#define SS second
typedef pair<ll, ll> pll; 
typedef vector<pll> vpll;
typedef vector<ll> vll;
#define rs(t) string t;cin>>t
#define ri(t) int t;cin>>t
#define rll(t) long long int t;cin>>t
#define MK make_pair
#define PB push_back
#define PO pop_back


int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  rll(n);
  rll(k);
  rs(s);
  string ns = "";
  ll ans = 0;
  rep(i,n-1){
  	if(s[i]==s[i+1])
  		ans++;	
  }
  if(k==0){
  	cout << ans << endl;
  	return 0;
  }
  for(ll i=0;i<n;i++){
  	ns+= s[i];
  	ll j = i+1;
  	while(j<n && s[j]==s[i]){
  		j++;
  	}
  	j--;
  	i = j;
  	
  }
  if(ns.size()<=2){

  	cout << n-1 << endl;
  	return 0;
  }
  ll l = 0;
  ll r = ns.size()-1;
  if(ns[l]==ns[r]){
  	cout << ans+min(k,r/2)*2 << endl;
  	return 0;
  }
  r--;
  if(k<=r/2){
  	cout << ans+k*2 << endl;
  	return 0;	
  }
  ans += r;
  ans++;

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

Measured memory_bytes: 592
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<bitset>
using namespace std;
const int maxn = 5005;
const int inf = 0x3f3f3f3f;
typedef long long ll;
int a[maxn];
int n , k;
int b[maxn];
bitset<maxn> dp;
int judge(int x)
{
    if(a[x]>=k) return 1;
    //剔除当前数，剩余的数dp一发；存在性判断.
    dp.reset();
    dp[0] = 1;
    for(int i = 0; i < n; i++){
        if(i==x) continue;
        dp|=(dp<<a[i]);
    }
    for(int i = k-1; i >= k-a[x]; i--){
        if(dp[i]){
            return 1;
        }
    }
    return 0;
}
int solve()
{

    sort(a,a+n);
    /*
    int lo = -1, hi = n;
    while(hi-lo>1){
        int m = (lo+hi)/2;
        if(judge(m)) hi = m;
        else lo = m;
    }
    return hi;
    */
    int lo = 0, hi = n-1;
    int mas = -1;//这里必须-1，因为我后面+1了，如果不这样的话，结果>=1;
    while(lo<=hi){
        int m = (lo+hi)/2;
        if(judge(m)) hi = m-1;
        else{
            lo = m+1;
            mas = max(mas,m);
        }
    }
    return mas+1;//下标是mas，所以要再加一；
}
int main()
{
    scanf("%d%d",&n,&k);

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

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repr(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define FORR(i, m, n) for (int i = (m); i >= (n); --i)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll mod2 = 998244353;
const int INF = 1000000005;


int main() {
  int n, u, k, v;
  cin >> n;
  bool G[n][n];
  rep(i, n) {
    rep(j, n) {
      G[i][j] = false;
    }
  }
  rep(i, n) {
    cin >> u >> k;
    rep(i, k) {
      cin >> v;
      G[u-1][v-1] = true;
    }
  }

  rep(i, n) {
    rep(j, n) {
      if (j) cout << " ";
      cout << G[i][j];
    }
    cout << endl;
  }


  
  return 0;
}


Measured memory_bytes: 3092
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    a=sorted([-1*random.randint(1,5) for _ in range(n)])[::-1]
    return n,a

show_flg=False
show_flg=True

x,y=MI()
n=64
a=0
def f(x):
    if x%4==0:
        r=x
    elif x%4==1:
        r=1
    elif x%4==2:
        r=x+1
    else:
        r=0
    return r
    
print(f(x-1)^f(y))

Measured memory_bytes: 38640
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair

int main()
{
int n,k;
scanf("%i %i",&n,&k);
vector<int> a(n),dp(n,0);
for(int &i:a) scanf("%i",&i);
for(int i=1;i<n;i++) 
{
dp[i]=dp[i-1]+abs(a[i]-a[i-1]);
for(int j=2;j<=k;j++)
if(i>=j) 
dp[i]=min(dp[i],dp[i-j]+abs(a[i]-a[i-j]));
}
printf("%i\n",dp.back());
return 0;
}

Measured memory_bytes: 1024
///not today

#include <bits/stdc++.h>
using namespace std;

#define SZ(x) (int)(x).size()
#define pb push_back
#define ll long long
#define xmax(x, y) (x) = max((x), (y))
#define xmin(x, y) (x) = min((x), (y))
#define F first
#define S second
#define pii pair<int, int>
#define pll pair<long long, long long>
#define int long long
#define pipii pair<int, pair<int, int> >
#define pf push_front
#define accept_sho ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

const ll maxn = 1000* 100 + 5, maxx = maxn* 1000* 1000* 1000 + 5;
int a[maxn], b[maxn];

int32_t main(){
    int n, m, vv, p;
    cin >>n >>m >>vv >>p;
    for(int i = 0; i < n; i ++){
        cin >>a[i];
        b[i] = a[i];
    }
    sort(b, b + n);
    int mn = b[n - p];
    int v = vv - p + 1;
    int l = mn - 1, r = maxx;
    while(r - l > 1){
        int mid = (r + l)/ 2;
        //cout <<mid <<endl;
        int x = 0;
        for(int i = 0; i <= n - p; i ++){
            int z = min(m, mid - b[i]);
            xmax(z, (ll)0);
            x += z;
        }
        if(x >= m* v)
            r = mid;
        else
            l = mid;
        }
    mn = r;
    //cout <<mn <<endl;
    int ans = 0;
    for(int i = 0; i < n; i ++){
        if(a[i] + m >= mn)
            ans ++;
    }
    cout <<ans <<endl;
    return false;
}


Measured memory_bytes: 1792
N, M = map(int, input().split())
L, R = [], []
for _ in range(M):
  l, r = map(int, input().split())
  L.append(l)
  R.append(r)

# 共通部分を求め、共通部分が無ければ0を出力する
m = max(L)
M = min(R)
if M >= m: print(M-m+1)
else: print(0)

Measured memory_bytes: 16824