akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>  
#include <functional>
#define ll long long int
#define INF 1000000000
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
#define ff first
#define ss second
#define ps(x,y) fixed<<setprecision(y)<<x
#define setbits(x) __builtin_popcountll(x)			//counts no of ones in binary representation
#define w(t) 	int t; cin>>t; while(t--)
#define pi 3.141592653589793238
#define sortt(v)  sort(v.begin(),v.end())
#define lb(v,x) std::lower_bound(v.begin(),v.end(),x)
#define ub(v,x) std::upper_bound(v.begin(),v.end(),x)
 
using namespace std;


int main()
{
	ll n,i,a,b,c,ans=0;
    cin >> n;
    map<ll,ll>ma;
    for(i=2;i*i<=n;i++){
    	if(n%i==0){
    		c=0;
    		while(n%i==0){
    			c++;
				n/=i;
    		}
    		ma[i]=c;
    	}
    }
    if(n!=1)	ma[n]=1;
    for(auto it=ma.begin();it!=ma.end();it++){
    	b=it->second;
    	c=1;
    	while(b>=c){
    		ans++;
			b-=c;
			c++;
    	}
    }
    cout<<ans;
	return 0;
}

Measured memory_bytes: 3632
#include <iostream>
#include<string>
#include<fstream>
#include<vector>
#include <algorithm>
#include <set>
#include <math.h>
using namespace ::std;
#define int long long 
vector<int > v;
signed  main()
{
	int n, k;
	
	cin >> n>>k;
	v.resize(100040, 10000000000);
	v[0] = 0;
	int f = 0;
	int ans = 0;
	for (int i = 0; i < n; i++)
	{
		int w;
		int q;
		cin >> w>>q;
		for (int j = f; j >= 0; j--)
		{
			if (v[j] == -1)
				continue;
			if (v[j] + w >k)
				continue;
			v[q + j] = min(v[q + j], v[j] + w);
			f = max(f,q + j); 
		}
	}
	int j = 100020;
	while (v[j] == 10000000000)
		j--;
	cout << j;
}
//   aaaddda

Measured memory_bytes: 1024
#ifdef _DEBUG
#include "MyLib.h"
#else
#define main_C main
#include "bits/stdc++.h" 
#include <regex>
#define _USE_MATH_DEFINES
#include <math.h>
#define FOR(i,s,e) for (int i = int(s); i < int(e); ++i)
#define REP(i,e) FOR(i,0,e)
#define INF (INT_MAX/2)
#define EPS (1.0e-8)
#define LINF (LONG_MAX/2)
const int MGN = 8;
const int ARY_SZ_MAX = 10000000;
using namespace std;
using ll = long long; using ull = unsigned long long;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vl = vector<ll>; using vvl = vector<vl>;
using vd = vector<double>; using vs = vector<string>;
using pii = pair<int, int>; using pll = pair<ll, ll>;
// functions
bool second_greater(const pii& left, const pii& right) {
    return left.second > right.second;
}
#endif


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

    int N;  cin >> N;
    vi A(N); REP(i, N) cin >> A[i];

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

    ll ans = 0;
    vi p;
    if (N%2==1) {
        // (i) updown
        p.push_back(-1);
        p.push_back(-1);
        for(int i=1; i<N-1; i++) {
            if (i % 2 == 0) p.push_back(-2);
            else p.push_back(2);
        }
        sort(p.begin(), p.end());
        ll sum = 0;
        REP(i, N) sum += p[i] * A[i];

        ans = max(ans, sum);

        // (ii) downup
        p.clear();
        p.push_back(1);
        p.push_back(1);
        for(int i=1; i<N-1; i++) {
            if (i % 2 == 1) p.push_back(-2);
            else p.push_back(2);
        }
        sort(p.begin(), p.end());
        sum = 0;
        REP(i, N) sum += p[i] * A[i];

        ans = max(ans, sum);
    } else {
        // (i) updown
        p.push_back(-1);
        p.push_back(1);
        for(int i=1; i<N-1; i++) {
            if (i % 2 == 0) p.push_back(-2);
            else p.push_back(2);
        }
        sort(p.begin(), p.end());
        ll sum = 0;
        REP(i, N) sum += p[i] * A[i];

        ans = max(ans, sum);

        // (ii) downup
        p.clear();
        p.push_back(1);
        p.push_back(-1);
        for(int i=1; i<N-1; i++) {
            if (i % 2 == 1) p.push_back(-2);
            else p.push_back(2);
        }
        sort(p.begin(), p.end());
        sum = 0;
        REP(i, N) sum += p[i] * A[i];

        ans = max(ans, sum);
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 1404
use proconio::{input, fastout};

#[fastout]
fn main() {
  input!{
    n:i64,
    mut a:[i64;n]
  }
  a.sort();
  a.reverse();
  let mut ans = 0;
  let mut test = vec![0,a[0]];
  for i in 1..n {
      for l in 0..2 {
          test.push(a[i as usize]);
      }
  }
  for i in 0..n {
      ans += test[i as usize];
  }
  println!("{}",ans);
}


Measured memory_bytes: 9404
#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

const int INF = 1<<30;

int n, m, data[16], dp[2][256], in;

main(){
  while(1){
    scanf("%d%d", &n, &m);
    if(!n && !m) break;
    for(int i=0;i<m;i++) scanf("%d", &data[i]);
    fill(dp[0], dp[2], INF);
    dp[0][128] = 0;
    for(int i=0;i<n;i++){
      for(int j=0;j<256;j++) dp[(i+1)%2][j] = INF;
      scanf("%d", &in);
      for(int j=0;j<256;j++){
        if(dp[i%2][j] == INF) continue;
        for(int k=0;k<m;k++){
          int next = j + data[k];
          if(next < 0) next = 0;
          if(next > 255) next = 255;
          dp[(i+1)%2][next] = min(dp[(i+1)%2][next], abs(in-(next)) * abs(in-(next)) + dp[i%2][j]);
        }
      }
    }
    int ans = INF;
    for(int i=0;i<256;i++) ans = min(ans, dp[n%2][i]);
    printf("%d\n", ans);
  }
}

Measured memory_bytes: 1188
//BROWNIE TK

#include <bits/stdc++.h>
typedef long long int lli;
typedef unsigned long long int ulli;
typedef long double ldb;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define pb push_back
#define popb pop_back()
#define pf push_front
#define popf pop_front()

#define si size()
#define be begin()
#define en end()
#define all(v) v.be, v.en

#define le length()
#define mp make_pair
#define mt make_tuple
#define acc(v) accumulate(all(v), 0)
#define F first
#define S second

#define pll pair<lli, lli>
#define pii pair<int, int>
#define pil pair<int, lli>

#define forz(i, n) for (int i = 0; i < n; i++)
#define fore(i, m, n) for (int i = m; i <= n; i++)
#define rforz(i, n) for (int i = n - 1; i >= 0; i--)
#define rfore(i, m, n) for (int i = n; i >= m; i--)

#define deci(n) fixed << setprecision(n)
#define high(n) __builtin_popcount(n)
#define highll(n) __builtin_popcountll(n)
#define parity(n) __builtin_parity(n)
#define ctz(n) __builtin_ctz(n)

#define bset(a, p) ((a) | (1ll << (p)))
#define bchk(a, p) ((a) & (1ll << (p)))
#define bxor(a, p) ((a) ^ (1ll << (p)));
#define brem(a, p) (bchk(a, p) ? (bxor(a, p)) : (a))
/*SOME BITMASK KNOWLEDGE
1)x & (x - 1):sets the last one bit of x to zero
power of two exactly when x & (x − 1) = 0.
2)x & -x:sets all the one bits to zero, except last one bit
3)x | (x - 1):inverts all the bits after the last one bit*/

#define lb lower_bound
#define ub upper_bound
#define er equal_range

#define findnot find_first_not_of

#define maxe *max_element
#define mine *min_element

#define mod 1000000007
#define mod2 998244353
#define gcd __gcd
#define kira ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)

#define endl "\n"
#define p0(a) cout << a << " "
#define p1(a) cout << a << endl
#define p2(a, b) cout << a << " " << b << endl
#define p3(a, b, c) cout << a << " " << b << " " << c << endl
#define p4(a, b, c, d) cout << a << " " << b << " " << c << " " << d << endl

#define oset tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define osetlli tree<lli, null_type, less<lli>, rb_tree_tag, tree_order_statistics_node_update>
//member functions :
//1. order_of_key(k) : number of elements sbtriectly lesser than k
//2. find_by_order(k) : k-th element in the set
#define ofk order_of_key
#define fbo find_by_order
using namespace std;

/*STD funcions*/
lli power(lli x, lli y, lli p)
{
    lli res = 1;
    x = x % p;
    while (y > 0)
    {
        if (y & 1)
            res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}
lli modi(lli a, lli m) { return power(a, m - 2, m); }
/*CODE BEGINS*/
const int N=2e5+5;
lli cnt[N];
int main()
{
    kira;
    lli n;
    cin>>n;
    if(n%2)
    {
        cout<<0;
        return 0;
    }
    lli k=n/2;
    lli c=0;
    lli val=5;
    while(k>=val)
    {
        c+=k/val;
        val*=5;
    }
    cout<<c;
    return 0;
}

Measured memory_bytes: 256
// Range Sum Query.cpp : このファイルには 'main' 関数が含まれています。プログラム実行の開始と終了がそこで行われます。
//

#include <iostream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <functional>
#include <map>
#include <string>
#include <cstdlib>
#include <cassert>


using lolo=long long;
using namespace std;
using vec=vector<lolo>;
using vvec=vector<vec>;
using vecb=vector<bool>;
#define FOR(i,n) for (lolo i=0; i<n; ++i)
#define FORN(i,a,b) for (lolo i=a; i<b; ++i)
#define REV(i,a,b) for (lolo i=a; i>b; --i)
#define ALL(x) x.begin(), x.end()



// 抽象 SegmentTree (0-indexed・一点更新・区間取得)
template <typename MonoidType>
struct SegmentTree
{
	using Function = function< MonoidType(MonoidType, MonoidType) >;

	// node, identity element
	int n;
	vector<MonoidType> node;
	MonoidType E0;

	// update / combine function
	Function upd_f, cmb_f;

	void build(int m, vector<MonoidType> v = vector<MonoidType>())
	{
		if (v != vector<MonoidType>()) m = v.size();
		n = 1; while (n < m) n *= 2;

		node = vector<MonoidType>(2 * n - 1, E0);
		if (v != vector<MonoidType>()) {
			for (int i = 0; i < m; i++) {
				node[n - 1 + i] = v[i];
			}
			for (int i = n - 2; i >= 0; i--) {
				node[i] = cmb_f(node[2 * i + 1], node[2 * i + 2]);
			}
		}
	}

	// initialize
	SegmentTree() {}
	SegmentTree(int n_, MonoidType E0_,
				Function upd_f_, Function cmb_f_,
				vector<MonoidType> v = vector<MonoidType>()) :
		E0(E0_), upd_f(upd_f_), cmb_f(cmb_f_)
	{
		build(n_, v);
	}

	// update k-th element (applied value: x)
	void update(int k, MonoidType x)
	{
		k += n - 1;
		node[k] = upd_f(node[k], x);
		while (k > 0) {
			k = (k - 1) / 2;
			node[k] = cmb_f(node[2 * k + 1], node[2 * k + 2]);
		}
	}

	// range query for [a, b)
	// 非再帰のアイデア: http://d.hatena.ne.jp/komiyam/20131202/1385992406
	MonoidType query(int a, int b)
	{
		MonoidType vl = E0, vr = E0;
		for (int l = a + n, r = b + n; l < r; l >>= 1, r >>= 1) {
			if (l & 1) vl = cmb_f(vl, node[(l++) - 1]);
			if (r & 1) vr = cmb_f(node[(--r) - 1], vr);
		}
		return cmb_f(vl, vr);
	}
};



int main()
{
	lolo N, Q;
	cin >> N >> Q;
	SegmentTree<lolo> seg(N, 0, [](lolo a, lolo b) { return a + b; },
		  					  [](lolo a, lolo b) {return a + b; });

	FOR(i, Q)
	{
		lolo com, x, y;
		cin >> com >> x >> y;
		x -= 1;
		if (com == 0) /* add */ {
			seg.update(x, y);
		}
		else {
			cout << seg.query(x, y ) << endl;
		}
	}
}




Measured memory_bytes: 4956
n=int(input())
L=sorted(list(map(int,input().split())))
if L[-1]-L[0]>1:
  s='No'
elif L[-1]-L[0]==1:
  c=L.count(L[0])
  s = ('Yes'if c<L[-1] and 2*(L[-1]-c)<=n-c else 'No')
else:
  s = ('Yes'if L[0]==n-1 or 2*L[-1]<=n else 'No')
print(s)

Measured memory_bytes: 13964
import sys
#input=sys.stdin.readline

def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

k,a,b=MAP()
if a >= b-2  or k <= a:
    print(k+1)
else:
    print(a+int((k+1-a)//2)*(b-a)+(k+1-a)%2)


Measured memory_bytes: 2940
import sys
import os

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

MOD = 10 ** 9 + 7


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    S = iss()
    key = ['Sunny', 'Cloudy', 'Rainy']
    print(key[(key.index(S) + 1) % 3])


if __name__ == '__main__':
    main()


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

int main() {
	int N;
	cin >> N;
	int T[N];
	int sum =0;
	for(int i=0; i<N; i++){
		cin >> T[i];
		sum+=T[i];
	}
	
	
	
	int M;
	cin >> M;
	for(int i=0; i<M; i++){
		int P,X;
		cin >> P >> X;
		P--;
		cout << sum + X - T[P]<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<math.h>
#include<algorithm>
#include<stdint.h>
#include<vector>
#include<deque>
#include<stack>
#include<string>
#include<cstring>
#include<time.h>
#include<iomanip>
#include<list>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<random>
#include<bitset>
#include <queue>
#include <map>


using namespace std;
using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
using ldouble = long double;

#define repi(i,a,b) for(ll i = (a); i < (b); i++)
#define rep(i, n) for(ll i = 0; i < (n); ++i)
ll MOD = 1000000007;
int main() {
    int N, K;
    cin >> N >> K;
    ll sum = 0;
    repi(k, K, N + 2) {
        sum += (k * (N - k + 1)) + 1;
        sum %= MOD;
    }
    cout << sum << endl;
    return 0;
}



Measured memory_bytes: 3648
N, K = map(int, input().split())
A = list(map(int, input().split()))

memo = {}
nxts = [None] * N
for i, x in enumerate(A + A):
  if x in memo:
    nxts[memo[x] % N] = i % N
  memo[x] = i

k = 0
visited = [-1] * N
p = 0
flag = False
ans = []
while k < K:
  if flag == False and visited[p] >= 0:
    vp = visited[p]
    k = vp + ((K-1) - vp) // (k - vp) * (k - vp)
    flag = True
  visited[p] = k
  nxt = nxts[p]
  if k == K-1 and nxt <= p:
    ans.append(A[p])
    nxt = p + 1
    if nxt >= N:
      break
  else:
    if nxt <= p:
      k += 1
    nxt = nxt + 1
    if nxt >= N:
      nxt %= N
      k += 1
  p = nxt

print(' ' .join(map(str, ans)))

Measured memory_bytes: 126792
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define rep2(i, s, n) for (ll i = s; i < (ll)(n); i++)
#define repr(i, n) for (ll i = n; i >= 0; i--)
#define pb push_back
#define COUT(x) cout << (x) << endl
#define COUTF(x) cout << setprecision(15) << (x) << endl
#define ENDL cout << endl
#define DF(x) x.erase(x.begin())  // 先頭文字削除
#define ALL(x) x.begin(), x.end()
#define SORT(x) sort(ALL(x))
#define REVERSE(x) reverse(ALL(x))
#define ANS cout << ans << endl
#define RETURN(x)    \
  cout << x << endl; \
  return 0
#define init() \
  cin.tie(0);  \
  ios::sync_with_stdio(false)
#define debug(x) cerr << "[debug] " << #x << ": " << x << endl;
#define debugV(v)                       \
  cerr << "[debugV] " << #v << ":";     \
  rep(i, v.size()) cerr << " " << v[i]; \
  cerr << endl;
using namespace std;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using P = pair<ll, ll>;
constexpr ll INF = 0x3f3f3f3f3f3f3f3f;
constexpr ld PI = 3.141592653589793238462643383279;
ll get_digit(ll x) {
  return to_string(x).size();
}

ll gcd(ll x, ll y) {
  return y ? gcd(y, x % y) : x;
}

ll lcm(ll a, ll b) {
  return a / gcd(a, b) * b;
}

vector<P> factorize(ll n) {
  vector<P> result;
  for (ll i = 2; i * i <= n; ++i) {
    if (n % i == 0) {
      result.pb({i, 0});
      while (n % i == 0) {
        n /= i;
        result.back().second++;
      }
    }
  }
  if (n != 1) {
    result.pb({n, 1});
  }
  return result;
}

vll divisor(ll n) {
  vll ret;
  for (ll i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      ret.push_back(i);
      if (i * i != n) ret.push_back(n / i);
    }
  }
  SORT(ret);
  return (ret);
}

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;
}

signed main() {
  init();
  string S;
  cin >> S;

  char c = S[0];
  ll ans = 0;
  rep(i, S.size()) {
    if (i == 0) continue;
    if (S[i] != c) {
      ans++;
      c = S[i];
    }
  }
  ANS;
  return 0;
}

Measured memory_bytes: 3688
#include<iostream>
using namespace std;
int main(){
    int a,b;
    int c;
    int s[50];
    int n = 0;
    while(cin >> a >> b){
        while(1){
            c = b;
            b = a % b;
            a = c;
            if(b == 0){
                s[n] = a;
                n++;
                break;
            }
        }
    }
    for(int i = 0;i<n;i++){
        cout << s[i] << endl;
    }
    return 0;
}


Measured memory_bytes: 3112
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(i=a;i<b;i++)
#define pb push_back
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define hell 1000000007
using namespace std;
void solve()
{
  ll n,m,i,j,k,c=0,y=0,ans=0,a,b;
  string s;
  cin>>n;
  if(n<600) cout<<8;
  else if(n<800) cout<<7;
   else if(n<1000) cout<<6;
    else if(n<1200) cout<<5;
     else if(n<1400) cout<<4;
      else if(n<1600) cout<<3;
       else if(n<1800) cout<<2;
       else cout<<1;


}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
   // cin>>t;
    while(t--)
    solve();
}


Measured memory_bytes: 3644
use std::io::prelude::*;

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

fn main() {
    let mut n = input::<usize>();
    let m = input::<usize>();
    let aa = (0..m).map(|_| input::<usize>()).collect::<Vec<_>>();
    let nums = [
        0, 2, 5, 5, 4, 5, 6, 3, 7, 6
    ];
    let mut usable = vec![false; 10];
    for a in aa { usable[a] = true; }
    let mut dp = vec![None; n+1];
    dp[0] = Some(0);
    for i in 0..n+1 {
        for j in 1..10 {
            if !usable[j] { continue; }
            if i >= nums[j] {
                dp[i] = std::cmp::max(dp[i], dp[i-nums[j]].map(|v| v+1));
            }
        }
    }
    let mut ans = vec![];
    while n > 0 {
        for j in (1..10).rev() {
            if !usable[j] { continue; }
            if n >= nums[j] && dp[n-nums[j]] == dp[n].map(|v| v-1) {
                n-=nums[j];
                ans.push(j);
                break;
            }
        }
    }
    println!("{}", ans.iter().map(|v| v.to_string()).collect::<String>());

}


Measured memory_bytes: 4352
import sys
input=sys.stdin.readline
import bisect

def main():
    _ = int(input())
    A = list(map(int,input().split()))
    A.sort()
    a = A.pop()
    bi = bisect.bisect_left(A, a//2)
    br = A[bi-1]
    if bi < len(A):
        if abs(a/2-A[bi-1]) > abs(a/2-A[bi]):
            br = A[bi]
    print(a, br)

if __name__ == '__main__':
    main()


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

int main(){
    int n;string s;
    cin >> n >> s;
    rep(i,s.size()){
        if((int)s.at(i) + n <= 90) s.at(i) += n;
        else s.at(i) = 64 + ((int)s.at(i) + n - 90);
    }
    cout << s << endl;
}

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

#define all(a) a.begin(), a.end()
#define allr(a) a.rbegin(), a.rend()
#define rev(v) reverse(v.begin(), v.end());
#define io() ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); srand(time(NULL));
 
using namespace std;

using ll = long long;
using ld = long double;
using ull = unsigned long long;

signed main(){
    io();
    int a, b, c; cin >> a >> b >> c;
    int x =  a + b + c;
    cout << (x >= 22 ? "bust":"win") << '\n';
    return 0;
}

Measured memory_bytes: 3592
#include<stdio.h>

int main(){
    int N,K,X,Y;
    scanf("%d %d %d %d",&N,&K,&X,&Y);
    if(N<= K)
{
    printf("%d\n",N*X);
    }
    else
 {  printf("%d\n",K*X+(N-K)*Y);
}
    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <set>
#include <stack>
#include <deque>
#include <cmath>
#include <map>
using namespace std;
using ll = long long;
#define rep(i, n) for (ll i = 0; i < n; i++)
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

int main() {
    ll x, y;
    cin >> x >> y;
    if (x % y == 0) cout << -1 << endl;
    else cout << x << endl;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define rep(i,n)  for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define deb(x) cerr << #x <<": " << x << '\n';
#define ios ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
using namespace std;
typedef long double ld;
typedef long long ll;

vector<ll> precalc(10000009);
void findDivisors(int n, vector<int>&div)
{
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j * i <= n; j++)
            div[i * j]++;
    }
}
int main(){
    ios;
    int n; cin >> n;
    vector<int> div(n + 1,0);
    //memset(div, 0, sizeof div);
    findDivisors(n,div);
    ll ans = 0;
    for(ll i = 1; i <= n; i++){
        ans += i * div[i];
       // deb(ans); deb(precalc[i]);
    }
    cout << ans;
    return 0;
}


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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N;
ll A[101010];
ll L[101010];
ll Lmi[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
	}
	int mi=0;
	FOR(i,N) {
		if(A[i]<0) mi++;
		A[i]=abs(A[i]);
	}
	sort(A,A+N);
	ll ret=0;
	FOR(i,N) {
		if(mi%2&&i==0) ret+=-A[i];
		else ret+=A[i];
	}
	cout<<ret<<endl;
	
	
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 1024
#!/usr/bin/python3
# import bisect
from collections import Counter, deque, OrderedDict, defaultdict
# from copy import copy, deepcopy # pythonのみ．copyは1次元，deepcopyは多次元．
# from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
# from functools import reduce
# from heapq import heapify, heappop, heappush
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    N=int(input())
    A=list(map(int,input().split()))
    Q=int(input())
    B, C = [0] * Q, [0] * Q
    for i in range(Q):
        B [i], C [i] = map(int, input().split())
    
    ans=sum(A)
    l=Counter(A)
    for i in range(Q):
        dif=C[i]-B[i]
        ans+=dif*l[B[i]]
        l[C[i]]+=l[B[i]]
        l[B[i]]=0
        print(ans)



    
resolve()

Measured memory_bytes: 94796
N,K,S=map(int,input().split())
A=[]
if 1<=S<10**9:
  for i in range(K):
    A.append(S)
  for i in range(N-K):
    A.append(S+1)
  print(*A)
else:
  for i in range(K):
    A.append(S)
  for i in range(N-K):
    A.append(S-1)
  print(*A)

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

typedef long long ll ; 
typedef unsigned long long ull ; 
typedef vector<int> vi ; 
typedef vector<vi> vii ;
typedef vector<ll> vl ;
typedef vector<vl> vll ;
typedef set<int> si ; 
typedef map<int,int> mii ; 
typedef map<ll,ll>  mll ; 
typedef map<string,int> msi ;
typedef set<ll> sl ; 
typedef set<char> sc ; 
typedef pair<int,int> pii ;


#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
const int INF = 1 << 29 ; 
#define MOD (ll)(1e9+7)
#define eps 1e-6
#define pb push_back 
#define mp make_pair 
#define DEBUG(x)		cout << '>' << #x << ':' << x << endl;
#define F first 
#define S second 

int main() 
{
	ios::sync_with_stdio(0) ;
	
	int n , m ;
	cin >> n >> m ;
	string a[n];
	REP(i,n)  cin >> a[i];


	long long dp[n][m];
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < m; ++j) dp[i][j] =0 ;
	}
	int curr = 1;
	for(int i = 0; i < n; ++i) {
		if(a[i][0] == '#') {
			curr = 0;
		}
		dp[i][0] = curr;
	}
	curr = 1;
	for(int i = 0; i < m; ++i) {
		if(a[0][i] == '#') {
			curr = 0;
		}
		dp[0][i] = curr;
	}

	for(int i = 1; i < n; ++i) {
		for(int j = 1; j < m; ++j) {
			if(a[i][j] == '#') {
				dp[i][j] = 0;
				continue;
			}
			dp[i][j] = dp[i-1][j] + dp[i][j-1];
			dp[i][j] %= MOD;
		}
	}

	// REP(i,n) {
	// 	REP(j,m) {
	// 		cout << dp[i][j] << " ";
	// 	}
	// 	cout << endl;
	// }

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

	return 0 ; 
}


Measured memory_bytes: 9088
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <tuple>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <cstdio>
#include <numeric>
#define REP(i, n) for(LL i = 0;i < n;i++)
#define REPR(i, n) for(LL i = n;i >= 0;i--)
#define FOR(i, m, n) for(LL i = m;i < n;i++)
#define FORR(i, m, n) for(LL i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()
#define INF (LL)1e15
#define MOD 1000000007
using namespace std;
typedef long long LL;
typedef pair<int, int> P;
typedef pair<LL, LL> LP;
typedef pair<int, P> PP;
typedef pair<LL, LP> LPP;
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

/*************** using variables ***************/
int n;
vector<LL> t, a;
LL t_num = 0, a_num = 0;
/**********************************************/
int main(){
    cin >> n;
    t.resize(n); a.resize(n);
    REP(i, n) cin >> t[i] >> a[i];
    
    t_num = t[0]; a_num = a[0];
    
    FOR(i, 1, n){
        LL j = max(t_num/t[i] + min(t_num%t[i], 1LL), a_num/a[i] + min(a_num%a[i], 1LL));
        t_num = t[i]*j; a_num = a[i]*j;
    }
    
    cout << t_num+a_num << endl;
}


Measured memory_bytes: 256
//  main.cpp
//  CppTest

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

int main(int argc, const char * argv[]) {
    /////////////////////
    // Write code below /
    /////////////////////
    int numberOfHinaarare;
    cin >> numberOfHinaarare;
    bool isFour = false; // 黄色があれば4種類
    for (int indexOfHinaarare = 0; indexOfHinaarare < numberOfHinaarare; indexOfHinaarare++) {
        string colorOfHinaarare;
        cin >> colorOfHinaarare;
        if (colorOfHinaarare == "Y") {
            isFour = true;
            break;
        }
    }
    
    if (isFour) {
        cout << "Four" << endl;
    } else {
        cout << "Three" << endl;
    }
    
    return 0;
}


Measured memory_bytes: 256
def snu(n):
    s=str(n)
    kei=sum(int(x) for x in s)
    return n/kei

def nn(n):
    s=str(n)
    kt=len(str(int(snu(n))))
    if s[-kt:].count("9")==kt:
        if s[-kt-1]=="9":
            n+=10**kt
            s=str(n)
            kt = len(str(int(snu(n))))
            if s[-kt:].count("9") == kt:
                return n
            else:
                s = s[:-kt] + "9" * kt
                return int(s)
        else:
            return n+10**kt
    else:
        s=s[:-kt]+"9"*kt
        return int(s)

k=int(input())
t=9 if k>9 else k
for i in range(1,t+1):
    print(i)
if k<=9:exit()
n=19
for _ in range(k-9):
    print(n)
    n=nn(n)

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

int main(){
    int n,m;
    cin >> n >> m;
    if(n >= m){
        cout << 0 << endl;
        return 0;
    }
    vector<int> x(m);
    for(int i=0;i<m;i++){
        cin >> x[i];
    }
    sort(x.begin(),x.end());

    vector<int> diffs(m);
    for(int i=1;i<m;i++){
        diffs.push_back(x[i]-x[i-1]);
    }
    sort(diffs.begin(),diffs.end(),greater<int>());
    
    int ans = x[m-1]-x[0];
    for(int i=0;i<n-1;i++){
        ans -= diffs[i];
    }
    cout << ans << endl;
}


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

int main(){
  int n,a[100];
  int x=0,y=0;
  cin>>n;
  for(int i=0;i<n;++i){
    cin>>a[i];
  }
  sort(a,a+n,greater<int>());
  for(int i=0;i<n;++i){
    if(i%2==0)
      x+=a[i];
    else
      y+=a[i];
  }
  cout<<x-y;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int gcd(int a, int b) {
    return b? gcd(b, a%b) : a;
}
int a[100005];
int main(int args, const char * argv[]) {
    int n, k; 
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; ++i) {
        scanf("%d", a+i);
    }
    int tmp = a[1], mx = a[1];
    for(int i = 2; i <= n; ++i) {
        tmp = gcd(tmp, a[i]);
        mx = max(mx, a[i]);
    
    }
    if(mx < k) {
        puts("IMPOSSIBLE");
        return 0;
    }
    if(k%tmp == 0) puts("POSSIBLE");
    else puts("IMPOSSIBLE");
    return 0;
}


Measured memory_bytes: 640
N=int(input())
for i in range(N):
    a,b,c=input().split()
    a=int(a)
    b=int(b)
    c=int(c)
    
    X=int(max(a,b,c))
    Y=int(min(a,b,c))
    Z=int(a+b+c-X-Y)
    
    if X**2 == Y**2 + Z**2:
        print("YES")
    else:
        print("NO")


Measured memory_bytes: 5592
n = int(input())
a = [0 for _ in range(n)]
xyies = [[] for _ in range(n)]
for i in range(n):
    aa = int(input())
    a[i] += aa
    xyies[i] = [list(map(int,input().split())) for _ in range(aa)]
ans = 0
for i in range(2**n):
    H_or_U = [0 for _ in range(n)]#インデックス番号の人間がHonestなら1、Unkindなら0をリストに記憶させます。
    for j in range(n):
        if (i >> j) & 1:
            H_or_U[j] += 1
    syougens = []
    for j in range(n):
        if H_or_U[j]:#j番の人間がもしも正直ならば
            syougen = xyies[j]
            for k in range(a[j]):
                if H_or_U[syougen[k][0]-1] == syougen[k][1]:#j番の人間のk番目のsyougenが正しい場合
                    syougens.append(True)
                else:
                    syougens.append(False)
    if all(syougens):
        ans = max(ans,sum(H_or_U))
print(ans)

Measured memory_bytes: 46684
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int t;
    int b;
} DATA;


int comp(const void *a, const void *b)
{
    return ((*(DATA *)a).b - (*(DATA *)b).b);
}


int main(void)
{
    int n;
    DATA t[25];
    int i;
    int sum;
    int flag;
    
    while (1){
        scanf("%d", &n);
        if (n == 0){
            break;
        }
        for (i = 0; i < n; i++){
            scanf("%d%d", &t[i].t, &t[i].b);
        }
        qsort(t, n, sizeof(DATA), comp);
        
        sum = 0;
        flag = 0;
        for (i = 0; i < n; i++){
            sum += t[i].t;
// printf("(t=%d b=%d sum=%d)\n", t[i].t, t[i].b, sum);
            if (sum > t[i].b){
                flag = 1;
            }
        }
        if (flag == 0){
            printf("Yes\n");
        }
        else {
            printf("No\n");
        }
    }
    return (0);
}



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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define SP << " " 
#define LLi long long int

using namespace std;

int imax=2147483647;
long long int llimax=9223372036854775807;

//int型vectorを出力
void PV(vector<int> pvv) {
	rep(i, pvv.size()) cout << pvv[i] SP;
	cout << endl;
}

//LLi型vectorを出力
void PVL(vector<LLi> pvv) {
	rep(i, pvv.size()) cout << pvv[i] SP;
	cout << endl;
}

int main(){

	LLi k, tmp=0;
	vector<int> md;
	vector<LLi> ten(1);

	cin>> k;
	md.resize(k);

	if(k%2==0){
		cout<< "-1" <<endl;
		return 0;
	}

    ten[0]=7;
  	rep(i, 10000000) ten.push_back((ten[i]*10)%k);

	rep(i, 10000000){
		tmp+=ten[i];
		tmp=tmp%k;
		//cout<< tmp << endl;
		if(tmp==0){
			cout<< i+1 <<endl;
			return 0;
		}
	}

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

Measured memory_bytes: 138416
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <list>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <iterator> 
#include <limits>

#define REP(i,n) for (int i=0;i<(n);i++)
#define FOR(i,a,b) for (int i=(a); i<(b); i++)
#define ALL(a) (a).begin(),(a).end()
#define RALL(A) (a).rbegin(),(a).rend()
#define PB push_back
#define MP make_pair

#define dump(x) cerr << #x << " = " << (x) << endl;

using namespace std;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const int INF = numeric_limits<int>::max() / 2;
const int NEG_INF = numeric_limits<int>::min() / 2;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

int N, M;
const int MAX_N = 1e5 + 10;

int imos[MAX_N];

int main(int argc, char const* argv[])
{
    cin >> N >> M;
    REP(i, M) {
        int a, b; cin >> a >> b;
        if (a > b) {
            swap(a, b);
        }
        a -= 1; b -= 1;
        imos[a] += 1;
        imos[b] -= 1;
    }
    /*
    REP(i, N - 1) {
        cout << imos[i] << " ";
    }
    cout << endl;
    */
    FOR(i, 1, N) {
        imos[i] += imos[i-1];
    }
    /*
    REP(i, N - 1) {
        cout << imos[i] << " ";
    }
    cout << endl;
    */
    REP(i, N - 1) {
        if (imos[i] % 2 != 0) {
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
    return 0;
}


Measured memory_bytes: 640
# Belongs to : midandfeed aka asilentvoice
while(1):
	s = str(input())
	if s == '-':
		break
	else:
		n = int(input())
		for _ in range(n):
			h = int(input())
			
			ans = s[h:] + s[:h]
			s = ans
			
		print(ans)

Measured memory_bytes: 7616
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;
 
int main(void){
	int a,b,c,d;


	cin >> a >> b >> c >> d;

	if (abs(a-c) <= d) {
		cout << "Yes";
		return 0;
	}
	else if (abs(a-b) <= d  && abs(b-c) <= d){
		cout << "Yes";
		return 0;
	}

	cout << "No";

	return 0;
}



Measured memory_bytes: 256
n, k = map(int, input().split())

a = []

for i in range(k):
    d = int(input())
    temp = [k for k in map(int, input().split())]
    for j in range(d):
        a.append(temp[j])



a = set(a)

print(len(set(range(1,n+1)) - a))


Measured memory_bytes: 9192
#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000007;
 
int main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);

  string S;
  cin >> S;
  int N = S.size();
  if(N % 2 == 0){
    N--;
  }
  for(int i = N/2;i>0;i--){
    string X = S.substr(0, i);
    string Y = S.substr(i, i);
    if(X == Y){
      cout << i*2 << endl;
      break;
    }
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <math.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rrep(i, n) for(int i = (n-1); i >= 0; i--)
using namespace std;
typedef long long ll;
const int MOD = 1000000007;
const ll INF = 1LL<<60;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
using Graph = vector<vector<int>>;

const int INFINI = 100000000;

int main(){
    
    int H, W; cin >> H >> W;

    int ch, cw;
    cin >> ch >> cw;
    ch--;
    cw--;
    int dh, dw;
    cin >> dh >> dw;
    dh--;
    dw--;

    vector<string> c(H);
    rep(i,H) cin >> c[i];

    deque<pair<int, int>> que;
    que.emplace_back(ch, cw);

    vector<vector<int>> counter(H, vector<int>(W,INFINI));
    counter[ch][cw] = 0;

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

    while(!que.empty()){
        auto vertex = que.front(); que.pop_front();
        int y = vertex.first;
        int x = vertex.second;

        rep(i,4){
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (ny < 0 || nx < 0 || ny >= H || nx >= W) continue;
            if (c[ny][nx] != '#') {
                if (counter[ny][nx] > counter[y][x]){
                    counter[ny][nx] = counter[y][x];
                    que.emplace_front(ny,nx);
                }
            }
        }

        for(int i = -2; i <= 2; i++){
            for(int j = -2; j <= 2; j++){
                if (i == 0 && j == 0) continue;
                int max_move = max(abs(i),abs(j));
                int min_move = min(abs(i),abs(j));
                if (max_move == 1 && min_move == 0) continue;
                int ny = y + i;
                int nx = x + j;
                if (ny < 0 || nx < 0 || ny >= H || nx >= W) continue;
                if (c[ny][nx] != '#'){
                    if (counter[ny][nx] > counter[y][x]+1){
                        counter[ny][nx] = counter[y][x]+1;
                        que.emplace_back(ny,nx);
                    }
                }

            }
        }

    }

    if (counter[dh][dw] == INFINI) cout << -1 << endl;
    else cout << counter[dh][dw] << endl;
} 

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

using namespace std;

typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int INF = 1000000000;
const ll LINF = (ll) 4000000000000000000;
const ll MOD = (ll) 1000000007;
const double PI = acos(1.0);
const int limit = 100010;

#define REP(i,m,n) for(ll i = m; i < (ll)(n); i++)
#define rep(i,n) REP(i, 0, n)
#define MP make_pair
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << endl
#define NP(v) next_permutation(v.begin(),v.end())
#define smaller_queue  priority_queue <ll, vector<ll>, greater<ll> >
//------------------------------------------------------

int main() {
    ll n;
    cin >> n;
    ll a[n];

    rep(i, n) {
        cin >> a[i];
        a[i] -= i + 1;
    }

    sort(a, a + n);
    ll sum = 0;

    rep(i, n) {
        sum += abs(a[i] - a[n / 2]);
    }

    cout << sum << endl;
    return 0;
}



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

namespace ALDS1_6_D {
    public static class Problem {
        public static int GetMinCost(this int[] source) {
            int n = source.Length;
            int minCost = 0;
            
            Dictionary<int, int> valueToIndex = Enumerable.Range(0, n)
                .ToDictionary(i => source[i], i => i);
            
            Array.Sort(source);

            int minValue = source[0];
            bool[] used = new bool[n];
            
            for(int i = 0; i < n; i++) {
                if (used[i])
                    continue;

                int minValueInGroup = source[i];
                int curPosition = valueToIndex[minValueInGroup];
                int sum = minValueInGroup;
                int groupCount = 1;

                while (curPosition != i) {
                    used[curPosition] = true;
                    groupCount++;
                    int nextValue = source[curPosition];
                    sum += nextValue;
                    curPosition = valueToIndex[nextValue];
                }
                minCost += Math.Min(
                    sum + (groupCount - 2) * minValueInGroup,
                    sum + minValueInGroup + (groupCount + 1) * minValue);
            }
            return minCost;
        }
    }

    class Program {
        static void Main(string[] args) {
            Console.ReadLine();
            int[] input = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            Console.WriteLine(input.GetMinCost());
        }
    }
}

Measured memory_bytes: 10356
// AOJ 0321: Investigation of Club Activities
// 2017.9.29 bal4u@uu

#include <stdio.h>

#define MAX 100003

/* UNION-FIND library */
int p[MAX], rank[MAX];

void make_set(int x) { p[x] = x, rank[x] = 0; }
void link(int x, int y) {
	if (rank[x] > rank[y]) p[y] = x;
	else { p[x] = y; if (rank[x] == rank[y]) rank[y] = rank[y] + 1;	}
}
int find_set(int x) { if (x != p[x]) p[x] = find_set(p[x]);	return p[x]; }
void union_set(int x, int y) { link(find_set(x), find_set(y)); }

int joined[MAX];

int main()
{
	int n, m, k, i, c, a, b, ga, gb, x;

	scanf("%d%d%d", &n, &m, &k);
	for (i = 1; i <= n; i++) p[i] = i;
	for (i = 1; i <= k; i++) {
		scanf("%d%d%d", &c, &a, &b);
		if (c == 1) {		// cmd: 1 a b
			a = find_set(a);
			b = find_set(b);
			ga = joined[a], gb = joined[b];
			if (ga > 0 && gb > 0 && ga != gb) break;
			union_set(a, b);
			x = find_set(a);
			if (ga == 0) ga = gb;
			if (ga > 0) {
				if (joined[x] == 0) joined[x] = ga;
				else if (joined[x] != ga) break;
			}
		}
		else if (c == 2) {  // cmd: 2 a b
			a = find_set(a);
			if (!joined[a]) joined[a] = b;
			else if (joined[a] != b) break;
		}
	}
	if (i > k) puts("0");
	else printf("%d\n", i);
	return 0;
}

Measured memory_bytes: 2856
#include <iostream>
#include<iomanip>
#include <map>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#include <queue>
#define INF 1e9+7
#define rep(i,n) for(int i=0;i<n;i++)
#define NO cout<<"NO"<<endl;
#define YES cout<< "YES"<<endl;
#define No cout<< "No"<<endl;
#define Yes cout<< "Yes"<<endl;
#define all(a) a.begin(),a.end()
#define P pair<int,int>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

//(int)'a'は97 (int)'A'は65 (int)'1'は49
//おまじない

const int maxn=200000;
ll fac[maxn];
ll rfac[maxn];
ll mod = INF;

ll pow(ll x,ll y){
    if(y==0){
        return 1;
    }else if(y==1){
        return x;
    }else if(y%2==0){
        ll a=pow(x,y/2);
        return (a*a)%mod;
    }else{
        ll a=pow(x,(y-1)/2);
        return a*a%mod*x%mod;
    }
}

int main(){
    
    ll h,w,k;
    ll ans=0;
    
    cin >> h>>w>>k;
    fac[0]=fac[1]=rfac[0]=rfac[1]=1;
    
    for(ll i=1;i<=w;i++){
        ans = (ans+(w-i)*i%mod*(h*h)%mod)%mod;
    }
    
    for(ll i=1;i<=h;i++){
        ans = (ans+(h-i)*i%mod*(w*w)%mod)%mod;
    }
    
    
    
    for(ll i=1;i<=h*w;i++){
        fac[i]=fac[i-1]*i%mod;
    }
    
    rfac[h*w]=pow(fac[h*w],INF-2);
    
    for(ll i=h*w;i>=1;i--){
        rfac[i-1]=rfac[i]*i%mod;
    }
    
    ll comb = fac[h*w-2]*rfac[h*w-k]%mod*rfac[k-2]%mod;
    ans= ans*comb%mod;
    
    cout << ans <<endl;
    
    return 0;
}


Measured memory_bytes: 3328
using System;
class ddccfinals{
  public static void Main(){
    String[] str = Console.ReadLine().Split(' ');
    int code = int.Parse(str[0]);
    int mec = int.Parse(str[1]);
    int result=0;
    if(code > 3){
      code = 4;
    }
    if(mec > 3){
      mec = 4;
    }
    result = (4-code) * 100000 + (4-mec) * 100000;
    if(code == 1 && mec == 1){
      result+=400000;
    }
    Console.WriteLine(result);
  }
}


Measured memory_bytes: 13140
s = input()
K = int(input())
Kinds = set(s)
sort_s = sorted(list(Kinds))
cand = set([]) | set(sort_s)
for h in sort_s:
    first_i = [i for i, c in enumerate(s) if c == h]
    for i in first_i:
        for j in range(1, 5):
            if i+j+1 <= len(s):
                cand.add(s[i:i+j+1])

sort_res = sorted(list(cand))

print(sort_res[K-1])

Measured memory_bytes: 5104
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using M = map<string,ll>;




int main(){
    ll N;
    cin >> N;
    string S;
    cin >> S;
    bool ans=1;
    ll T=S.size();
    if(T%2==1){ans=0;}
    else if(T%2==0){
        for(int i=0;i<T/2;i++){
            if(S.at(i)!=S.at(i+(T/2))){
                ans=0;break;
            }
        ;}
    }

    if(ans==0){cout<<"No"<<endl;}
    else cout<<"Yes"<<endl;



return 0;


}  



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define adj_list vector<vi>
#define endl "\n"
#define INF_INT 2e9
#define INF_LL 2e18
#define matmax 25
#define mod 1000000007
#define mp make_pair
#define pb push_back
#define pi pair<int, int>
#define pii pair<int, pair<int, int> >
#define pl pair<ll, ll>
#define pll pair<ll, pair<ll, ll> >
#define vi vector<int>
#define vl vector<ll>
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
typedef long long int ll;

int lsone(int n)
{
	return (n&-n);
}

ll pow1(ll a, ll b)
{
	if (b == 0)
		return 1ll;
	else if (b == 1)
		return a;
	else
	{
		ll x = pow1(a, b/2);
		x *= x;
		x %= mod;
		if (b%2)
		{
			x *= a;
			x %= mod;
		}
		return x;
	}
}

ll x;

int main()
{		
	cin>>x;

	double y = double(x)/3.00F;

	double ans = y * y * y;

	printf("%.12F\n", ans);

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define  ll  long long int

using namespace std;



ll check(ll x)
{
   ll k=sqrt(x);

   for(ll i=2;i<=k;i++)
   {
     if(x%i==0)return 0;
   }
   return 1;
}
int main()
{


  ll n,i,j,k,p,d;

  cin>>n;

  for(i=n;;i++)
  {
    if(check(i))
    {
      cout<<i<<endl;
      return 0;
    }
  }
  return 0;
}


Measured memory_bytes: 256
def main():
    R_edge, L_edge, U_edge, D_edge = [None]*3, [None]*3, [None]*3, [None]*3
    n = int(input())
    xyd = [input().split() for _ in [0]*n]
    xyd = [(int(x), int(y), d) for x, y, d in xyd]
    for x, y, d in xyd:
        if d in ["R", "L"]:
            if U_edge[1] is None:
                U_edge[1] = y
            else:
                U_edge[1] = max(U_edge[1], y)
            if D_edge[1] is None:
                D_edge[1] = y
            else:
                D_edge[1] = min(D_edge[1], y)
        else:
            if R_edge[1] is None:
                R_edge[1] = x
            else:
                R_edge[1] = max(R_edge[1], x)
            if L_edge[1] is None:
                L_edge[1] = x
            else:
                L_edge[1] = min(L_edge[1], x)
        for p, q, r in [[R_edge, "R", x], [L_edge, "L", x], [U_edge, "U", y], [D_edge, "D", y]]:
            if d == q:
                if p[0] is None:
                    p[0] = r
                    p[2] = r
                else:
                    p[0] = min(p[0], r)
                    p[2] = max(p[2], r)

    def area(t):
        RL, UD = [], []
        if R_edge[0] is not None:
            RL += [t+R_edge[0], t+R_edge[2]]
        if R_edge[1] is not None:
            RL += [R_edge[1]]
        if L_edge[0] is not None:
            RL += [-t+L_edge[0], -t+L_edge[2]]
        if L_edge[1] is not None:
            RL += [L_edge[1]]
        if U_edge[0] is not None:
            UD += [t+U_edge[0], t+U_edge[2]]
        if U_edge[1] is not None:
            UD += [U_edge[1]]
        if D_edge[0] is not None:
            UD += [-t+D_edge[0], -t+D_edge[2]]
        if D_edge[1] is not None:
            UD += [D_edge[1]]
        if len(RL)*len(UD) == 0:
            return 0
        else:
            return (max(RL)-min(RL))*(max(UD)-min(UD))

    t = [0]
    for edge in [R_edge, L_edge, U_edge, D_edge]:
        if None not in edge:
            t.append(abs(edge[1]-edge[0]))
            t.append(abs(edge[1]-edge[2]))
    for edge1, edge2 in [[R_edge, L_edge], [U_edge, D_edge]]:
        if None not in [edge1[1], edge2[0]]:
            t.append(abs(edge1[1]-edge2[0]))
            t.append(abs(edge1[1]-edge2[2]))
        if None not in [edge2[1], edge1[0]]:
            t.append(abs(edge2[1]-edge1[0]))
            t.append(abs(edge2[1]-edge1[2]))
        if None not in [edge1[0], edge2[0]]:
            for i in [0, 2]:
                for j in [0, 2]:
                    t.append(abs(edge2[i]-edge1[j])/2)

    print(min([area(i) for i in t]))


main()


Measured memory_bytes: 48804
#include <stdio.h>


int main (void){
 
 int h=-1 , w=-1 , i , j;
 
 while(1){
     
     scanf("%d %d", &h, &w);
     if(h + w == 0) break;
     
     for(i=0; i < h; i++){
         for(j=0; j < w; j++){
             printf("#");
         }
         puts("");
     }
     
     puts("");
 }
 return 0;
 
}
 

Measured memory_bytes: 588
N, M = map(int,input().split())
z = [list(map(int,input().split())) for i in range(M)]
box = [[1,1]]
for i in range(N-1):
  box.append([0,1])
for i in range(M):
  box[z[i][0]-1][1] -= 1
  box[z[i][1]-1][1] += 1
  if (box[z[i][0]-1][0] == 1):
    box[z[i][1]-1][0] = 1
  if (box[z[i][0]-1][1] == 0):
    box[z[i][0]-1][0] = 0
ans = 0
for i in range(N):
  if (box[i][0] != 0):
    ans += 1
print(ans)

Measured memory_bytes: 96588