akhauriyash/Code-Regression huggingface dataset:
require 'set'

class Hash
  def push(key, value)
    self[key] = [] if self[key] == nil
    self[key].push(value)
  end
end

class Array
  def lower_bound(value)
    left = -1;
    right = self.length;
    while left + 1 < right
      mid = left + (right - left) / 2;
      if self[mid] >= value
        right = mid
      else
        left = mid
      end
    end
    right
  end

  def unique
    res = [self.first]
    each_cons(2) do |a, b|
      if a != b
        res.push(b)
      end
    end
    res
  end
end

def get_ints
  gets.split.map(&:to_i)
end

def get_ints_minus_one
  get_ints.map { |x| x - 1 }
end

def get_int
  gets.chomp.to_i
end

N, M, Q = get_ints
A = []
B = []
C = []
D = []
Q.times do |i|
  A[i], B[i], C[i], D[i] = get_ints
  A[i] -= 1
  B[i] -= 1
end

@result = 0

def dfs(arr)
  if arr.length == N
    sum = 0
    Q.times do |q|
      if arr[B[q]] && arr[A[q]] && arr[B[q]] - arr[A[q]] == C[q]
        sum += D[q]
      end
    end
    if @result < sum
      @result = sum
    end
  elsif arr.length == 0
    [*1..M].each { |v| dfs(arr + [v]) }
  else
    [*arr.last..M].each { |v| dfs(arr + [v]) }
  end
end

dfs([])

puts @result


Measured memory_bytes: 14524
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N=I()
    ans = 0
    for i in range(N+1):
        if(i%3 and i%5):
            ans += i
    print(ans)
if __name__ == '__main__':
    main()

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

const int INF = 1000003;

string S[1003];
int SP[1003][1003], done[1003][1003];
priority_queue< pair<int, pair<int, int> >, vector< pair<int, pair<int, int> > >, greater< pair<int, pair<int, int> > > > Q;

void relax(int sx, int sy, int tx, int ty, int w)
{
    if (SP[tx][ty] > SP[sx][sy] + w)
    {
        SP[tx][ty] = SP[sx][sy] + w;
        Q.push({SP[tx][ty], {tx, ty}});
    }
}

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

    int h, w, sx, sy, tx, ty;
    cin >> h >> w >> sx >> sy >> tx >> ty;
    sx--, sy--, tx--, ty--;

    for (int i=0; i<h; i++)
        cin >> S[i];

    for (int i=0; i<h; i++)
        for (int j=0; j<w; j++)
            SP[i][j] = INF;

    SP[sx][sy] = 0;
    Q.push({0, {sx, sy}});

    while (!Q.empty())
    {
        auto f = Q.top();
        Q.pop();
        int x = f.second.first, y = f.second.second;

        if (done[x][y])
            continue;
        
        done[x][y] = 1;

        for (int i=-2; i<=2; i++)
            for (int j=-2; j<=2; j++)
            {
                int a = x + i, b = y + j;

                if (a < 0 || b < 0 || a >= h || b >= w || done[a][b] || S[a][b] == '#')
                    continue;
                
                if (i == 0 && j == 0)
                    continue;
                
                if (abs(i) + abs(j) == 1)
                    relax(x, y, a, b, 0);
                else
                    relax(x, y, a, b, 1);
            }
    }

    if (SP[tx][ty] == INF)
        cout << -1 << "\n";
    else
        cout << SP[tx][ty] << "\n";

    return 0;
}


Measured memory_bytes: 12544
#include <iostream>
#include <string>

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

using namespace std;

int main() {
	string S, T;
	cin >> S >> T;

	if ((S.length() == T.length() - 1) && (T.substr(0, S.length()) == S))
	{
		cout << "Yes";
	}
	else {
		cout << "No";
	}

	cin >> S;

	return 0;
}

Measured memory_bytes: 3628
#include <stdio.h>

int main(){

    int G, N, D;
    scanf("%d %d %d", &G, &N, &D);

    int R1, R2;

    R1 = G>=N? G-N : N-G;
    R2 = G>=D? G-D : D-G;

    if(R1<R2){
        printf("A");
    }else {
        printf("B");
    }

    return 0;
}

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

int main() {
	int k;
	cin >> k;// mod で考える。k 回 f(x)=10x+7
	int x = 7 % k;
	set<int> s;
	int i = 1;
	while(s.count(x) == 0) {
		if (x == 0) {
			cout << i << endl;
			return 0;
		}
		s.insert(x);
		x = (x * 10 + 7) % k;
		i++;
	}
	cout << -1 << endl;
	return 0;
}


Measured memory_bytes: 50492
#include<bits/stdc++.h>
using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int INF = 1061109567;
const ll LINF = 4557430888798830399ll;

/* --- */

void TestCase() {
    ll n, x;
    scanf("%lld%lld", &n, &x);
    printf("%lld\n", n + 1 - x);
}

int main() {
#ifdef KisekiPurin
    freopen("KisekiPurin.in", "r", stdin);
    //freopen("KisekiPurin.out", "w", stdout);
#endif // KisekiPurin
    //InitCase();
    int t = 1;
    //scanf("%d", &t);
    for(int i = 1; i <= t; ++i) {
        //printf("Case #%d: ", i);
        TestCase();
    }
    return 0;
}


Measured memory_bytes: 256
use proconio::{input, fastout};
use std::collections::BTreeMap;

#[fastout]
fn main() {
    input! {
        n: usize,
        k: usize,
        ab: [(usize, usize); n],
    }

    let mut map = BTreeMap::new();

    for (a, b) in ab {
        *map.entry(a).or_insert(0) += b;
    }

    let mut i = 0;

    for (key, value) in map.into_iter() {
        i += value;
        if i >= k {
            println!("{}", key);
            return;
        }
    }
}

Measured memory_bytes: 6560
#include<stdio.h>
#include<stdlib.h>
#define MAX 20000  // スタックの最大値

typedef struct{
  int top;         // スタックポインタ(一番上の位置)
  int S[MAX];
}Stack;


// スタック st の初期化
void initialize(Stack *st)
{
  st->top = 0;
  st->S[st->top] = 0;
}

// スタック st が空かどうかを確認
int isEmpty(Stack *st)
{
  return st->top == 0;
}

// スタック st が一杯かどうかを確認
int isFull(Stack *st)
{  
  return st->top >= MAX - 1;
}

// スタック st に要素 x をプッシュ(一番上に要素を追加)
void push(int x, Stack *st)
{
  if (isFull(st)) 
    exit(1);

  st->top++;
  st->S[st->top] = x;
}

// スタック st から要素をポップ(一番上の要素を取り出す)
int pop(Stack *st) {
  if (isEmpty(st)) 
    exit(1);

  st->top--;
  return st->S[st->top+1];
}


int main(void)
{
  Stack st1;     // '\' の開始位置を格納するスタック
  Stack st2_j;   // 各水たまりの最も左の'\' の位置を格納するスタック
  Stack st2_a;   // 各水たまりの水量を格納するスタック
	int asd = 0;
	int j;
  // スタック初期化
  initialize(&st1);
  initialize(&st2_j);
  initialize(&st2_a);

  char c;
  int sum = 0;  // 水たまりの総水量

  // 地形を読み込み，各水たまりの水量を計算
  for (int i = 0; (c = getchar()) != EOF; i++) {
    if (c == '\\') {                                 // '\' が出た時の処理
      // 位置 i を st1 にプッシュ(write your code)
    	push(i,&st1);
    	
       	
    }else if (!isEmpty(&st1) && c == '/') {          // '/' が出た時の処理
      // 水たまりの総水量 sum を更新(write your code)
    	j = pop(&st1);
    	sum += i-j;
      // st2_j と st2_a を用いて水たまりの水量を更新 
      int a = i - j;   // 更新する水たまりの水量を a に格納していく
      while (!isEmpty(&st2_j) && st2_j.S[st2_j.top] > j) {  // 最も左の '\' の位置が j よりも大きい場合，以下を繰り返す
        // 水たまりの水量を求めていく (write your code)
      	a += pop(&st2_a);
      	pop(&st2_j);
      	
      }
      // 更新した水たまりの「最も左の'\' の位置」および「水量」を更新 (write your code)
    	push(a,&st2_a);
    	push(j,&st2_j);
    }
  }

  printf("%d\n", sum);       // 水たまりの総水量を出力
  printf("%d", st2_a.top);   // 水たまりの個数を出力

  // 各水たまりの水量を断面図の左から出力(スタックの底から出力)
  for (int i = 1; i <= st2_a.top; i++) 
    printf(" %d", st2_a.S[i]);  
  printf("\n");

  return 0;
}



Measured memory_bytes: 2108
n,k = map(int, input().split())
p = 0
for i in range(1, n + 1):
    if i >= k:
        p += 1
    else:
        j = i
        q = 1
        while j < k:
            j *= 2
            q /= 2
        p += q
ans = p / n
print(ans)

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

int main(){
  int n,h,w;
  cin>>n>>h>>w;

  int ans=0;
  for(int i=0; i<n; i++){
    int a,b;
    cin>>a>>b;
    if(h<=a && w<=b)ans++;
  }

  cout<<ans<<endl;
}


Measured memory_bytes: 256
use std::io::Read;

fn solve(n: i32) -> Vec<i32> {
    let mut x = n;
    let mut a = 2;
    let mut r = Vec::new();
    while a * a <= x {
        if x % a == 0 {
            x /= a;
            r.push(a);
        } else {
            a += 1;
        }
    }
    if x > 1 {
        r.push(x);
    }
    r
}

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();
    let mut iter = buf.split_whitespace();
    let n: i32 = iter.next().unwrap().parse().unwrap();
    let w = solve(n);
    print!("{}:", n);
    for x in w {
        print!(" {}", x);
    }
    println!();
}



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

long long sum(long long a, long long b){
  long long an = 0 ;
  for(int i=a;i<b+1;i++){
    an += i ;
  }
  return an ;
}
 
int main(){
  long long n, k ;
  cin >> n >> k ;
  long long upper = sum(n+1-k, n) ;
  long long under = sum(0, k-1) ;
  long long base = upper - under + 1;
  long long ans = 0;
  for(int i=1;i<n+3-k;i++){
    ans += base ;
    base += (n+1-k-i) - (k-1+i) ;
  }
  cout << ans%(1000000007) ;
  return 0 ;
}

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


int main()
{
    
    int a,b,c;
    
    cin>>a>>b>>c;    
    if(a==b&&a!=c){
        cout<<"Yes";
    }else if(a==c&&a!=b){
        cout<<"Yes";
    }else if(b==c&&b!=a){
        cout<<"Yes";
    }else{
        cout<<"No";
    }
    
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(){
  int unused __attribute__((unused));
  int A, B, C, D;
  unused = scanf("%d %d %d %d", &A, &B, &C, &D);

  if((A+B)>(C+D)) printf("Left");
  else if((A+B)<(C+D)) printf("Right");
  else printf("Balanced");
  return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <cstdio>
#include <list>
#define ll long long
#define rep2(i,a,b) for(int i=a;i<=b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define rep3(i,a,b) for(int i=a;i>=b;i--)
#define REP(e,v) for(auto e:v)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define tii tuple<int,int,int>
#define pq priority_queue<int>
#define pqg priority_queue<int,vector<int>,greater<int>>
#define pb push_back
#define edge(v,a,b) v[a].pb(b);v[b].pb(a);
#define vec vector<int>
#define vecll vector<ll>
#define vecstr vector<string>
#define vecch vector<char>
#define vecpii vector<pii>
#define bs binary_search
#define All(c) (c).begin(),(c).end()
using namespace std;
int in(){int x;scanf("%d",&x);return x;}
string stin(){string s;cin>>s;return s;}
char chin(){char c;cin>>c;return c;}
ll lin(){ll x;scanf("%lld",&x);return x;}

int main(){
    int n=in();
    string s=stin();
    int k=in();
    char c=s.at(k-1);
    rep(i,n){
        if(s.at(i)!=c)cout<<"*";
        else cout<<s.at(i);
    }
}

Measured memory_bytes: 256
#include<iostream>
#include <stdio.h>
using namespace std;

int main()
{
  int a,b;
  char op;
  while(1){
  cin>>a>>op>>b;
  if(op=='?')
    return 0;
  else if(op=='+')
    cout<<a+b<<endl;
  else if(op=='-')
    cout<<a-b<<endl;
  else if(op=='*')
    cout<<a*b<<endl;
  else if(op=='/')
    cout<<a/b<<endl;
  }
  return 0;
}



Measured memory_bytes: 3100
#include<bits/stdc++.h>
using namespace std;
const int MX = 105;
#define rep(i,n) for(int i=0; i<(n); i++)
int n, m, a, pr[MX], w, b[MX][MX];
set<int> st[MX];
bool used[MX];
bool dfs(int v){
	used[v] = true;
	for(int it: st[v]) if((w = pr[it/m]) < 0 || (!used[w] && dfs(w))){
		pr[it/m] = v;
		return true;
	}
	return false;
}
int main(){
	scanf("%d%d", &n, &m);
	rep(i,n) rep(j,m){
		scanf("%d", &a);
		st[i].insert(a-1);
	}
	rep(i,m){
		fill(pr, pr+n, -1);
		rep(j,n){
			fill(used,used+n,0);
			dfs(j);
		}
		rep(j,n){
			w = pr[j];
			auto it = st[w].lower_bound(j*m);
			b[i][w] = *it;
			st[w].erase(it);
		}
	}
	rep(i,n) rep(j,m) printf("%d%c", b[j][i]+1, j<m-1?' ':'\n');
	rep(i,m) sort(b[i],b[i]+n);
	rep(i,n) rep(j,m) printf("%d%c", b[j][i]+1, j<m-1?' ':'\n');
}


Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
#define pie 3.141592653589793238462643383279
#define int long long
#define mod 1000000007
#define INF LLONG_MAX/5
#define all(v) v.begin(),v.end()
#define P pair<int,int>
#define S second
#define F first
#define f(i,n) for(int i=0;i<n;i++)
int x[50];
signed main(){
	int n,ans=0;
	cin>>n;
	f(i,n)cin>>x[i];
	f(i,n){
		for(int j=i+1;j<n;j++){
			ans+=x[i]*x[j];
		}
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 256
# 焼きなまし（1000から線形に落とす）

from time import time
from math import exp
key = 1
rnd_mod = 12345678901234567891
rnd_x = 9876543210987654321 + 1234567890123456789 * key % rnd_mod
def rnd():
    global rnd_x
    rnd_x = rnd_x**2 % rnd_mod
    return (rnd_x>>10) % (1<<40)
def randrange(a, b=-1):
    if b > 0: return randrange(b-a) + a
    return rnd() % a

def calc():
    s = 0
    last = [-1] * 26
    for i, t in enumerate(A):
        s += S[i][t]
        last[t] = i
        for j, c in enumerate(C):
            s -= c * (i - last[j])
    return s

sTime = time()
D = int(input())
C = [int(a) for a in input().split()]
S = [[int(a) for a in input().split()] for _ in range(D)]
A = [randrange(26) for _ in range(D)]
# A = [0] * D
# A = [0, 16, 12, 13, 12]
# A = [0, 16, 12, 13, 19]
ans = calc()
# print("ans =", ans)
while time() - sTime < 1.8:
    T = 1000 * max(1 - (time() - sTime) / 1.6, 0)
    d = randrange(D)
    i = A[d]
    for k in range(d)[::-1]:
        if A[k] == i:
            prev = k
            break
    else:
        prev = -1
    for k in range(d + 1, D):
        if A[k] == i:
            prev_ne = k
            break
    else:
        prev_ne = D
    for j in range(26):
        t = S[d][j] - S[d][i]
        for k in range(d)[::-1]:
            if A[k] == j:
                new = k
                break
        else:
            new = -1
        for k in range(d + 1, D):
            if A[k] == j:
                new_ne = k
                break
        else:
            new_ne = D
        t += C[j] * (d - new) * (new_ne - d) - C[i] * (d - prev) * (prev_ne - d)
        if (T < 1 and t > 0) or (T >= 1 and randrange(1 << 10) < exp(max(min(t / T, 0), -10)) * (1 << 10)):
            A[d] = j
            ans += t
            prev, prev_ne = new, new_ne
            i = j
            if 0:
                print("A =", A)
                print("ans =", ans)
                print("calc =", calc())
            
            

print(*[a + 1 for a in A], sep = "\n")
if 0:
    print(ans)
    print("A =", A)

Measured memory_bytes: 76928
#include <stdio.h>
int main(){
char oomoji[]="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
char komoji[]="abcdefghijklmnopqrstuvwxyz";
char c;
int i;
while(1){
scanf("%c",&c);
if (c=='\n')break;
for(i=0;i<26;i++){
    if(c==oomoji[i])c=komoji[i];
    else if (c==komoji[i])c=oomoji[i];
}
printf("%c",c);

}
printf("\n");
return 0;
}

Measured memory_bytes: 524
#include<map>
#include<set>
#include<bitset>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<chrono>
#include<stack>
#include<fstream>
#include<math.h>
#include<list>
#include<complex>
#define REP(i,x,y) for(ll i=x;i<=y;i++)
#define SIZE(a) ll(a.size())
#define vll vector<ll>
#define vvll vector<vector<ll>>
#define vtype(type) vector<type>
#define vvtype(type) vector<vector<type>>
#define MEMSET(a, n, m) for(ll i=0;i<=n;i++) a[i] = m
#define BIT(n) (ll(1)<<n)
#define UNIQUE(v) v.erase(unique(v.begin(),v.end()),v.end()) 
#define UNIQUE_ARRAY(a,x) unique(a + 1, a + x + 1) - a - 1
#define SORT(a,n) sort(a+1,a+n+1)
#define SORT_O(a,n,order) sort(a+1,a+n+1,order)
#define PER(i,y,x) for(ll i=y;i>=x;i--)
typedef long long ll;
using namespace std;


ll const MOD = 1e9 + 7;
ll mod_p(ll x, ll y) {
	x %= MOD;
	y %= MOD;
	return (x + y + MOD) % MOD;
}

ll mod_m(ll x, ll y) {
	x %= MOD;
	y %= MOD;
	return x * y%MOD;
}

ll mod_pow(ll x, ll t) {
	x %= MOD;
	if (t == 0) {
		return 1;
	}
	else {
		ll v = mod_pow(x, t / 2);
		if (t % 2 == 0) {
			return v * v % MOD;
		}
		else {
			return v * v%MOD * x %MOD;
		}
	}
}

ll mod_inv(ll x) {
	return mod_pow(x, MOD - 2);
}

struct edge
{
	long long to; ll name;
	bool operator<(const edge& rhs) const {
		return name > rhs.name;
	}
};

ll const MAX = 1e5 + 5;
vvtype(edge) G(MAX);
vll color(MAX);
vll parent(MAX);
vvll children(MAX);
vll times(MAX, 0);

void dfs(ll cur, ll& ans, ll k) {
	ll tmp = 0;
	for (auto next : children[cur]) {
		dfs(next, ans, k);
		tmp = max(tmp, times[next]);
	}
	tmp++;
	if (tmp == k && parent[cur] != 1) {
		tmp = 0;
		ans++;
	}
	times[cur] = tmp;
}

int main() {
	ll n, k;
	cin >> n >> k;
	ll ttt;
	cin >> ttt;
	ll ans = 0;
	parent[1] = 1;
	if (ttt != 1) {
		ans++;
	}
	REP(i, 2, n) {
		ll x;
		cin >> x;
		children[x].push_back(i);
		parent[i] = x;
	}
	dfs(1, ans, k);
	cout << ans << endl;
}

Measured memory_bytes: 19840
#include <bits/stdc++.h>
using namespace std;
 
#define MP make_pair
#define PB push_back
#define ALL(x)      (x).begin(),(x).end()
#define REP(i,n)    for(int i=0;i<(n);i++)
#define REP1(i,n)   for(int i=1;i<(n);i++)
#define REP2(i,d,n) for(int i=(d);i<(n);i++)
#define RREP(i,n)   for(int i=(n);i>=0;i--)
#define CLR(a)      memset((a),0,sizeof(a))
#define MCLR(a)     memset((a),-1,sizeof(a))
#define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))
 
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI > VVI;
typedef vector<string> VS;
typedef vector<LL> VLL;
typedef pair<int,int> PII;
 
const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;
 
const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};

int main() {
    int N, tmp;
    VI v;
    cin >> N;
    REP(i, N) {
        cin >> tmp;
        v.PB(tmp);
    }
    sort(ALL(v));
    double ans = v[0];
    REP1(i, N) {
        ans += v[i];
        ans /= 2.0;
    }

    printf("%.9f\n", ans);
}

Measured memory_bytes: 256
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <string>
#include <vector>
#include <list>
using namespace std;
#include <stdio.h>
#include <map> 
#include <algorithm>
#include <functional>
#include <algorithm>
#include <functional>
#include <array>
#include <iostream>
#include <limits>
#include <numeric>
#include <type_traits>




int main()
{
	std::vector<long int> a;
	long int N;
	std::string S;
	cin >> N >> S;

	int c = 1;
	char last = S[0];
	for (int i = 1; i < S.length(); ++i) {
		if (S[i] != last) {
			last = S[i];
			c++;
		}
	}

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

	return 0;
}




Measured memory_bytes: 512
def main():
    n,m = map(int,input().split())
    a = list(map(int,input().split()))
    h = {}
    for i in range(m):
        b,c = map(int,input().split())
        if c not in h.keys():
            h[c] = b
        else:
            h[c]+=b
    for i in range(n):
        if a[i] not in h.keys():
            h[a[i]]=1
        else:
            h[a[i]]+=1
    ans = 0
    for k in sorted(h.keys(),reverse=True):
        if n<h[k]:
            ans += n*k
            break
        ans += h[k]*k
        n = n-h[k]
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 33316
#include <stdio.h>

int main(void) {
    int total=0, ans=0;
  
    int N, M, C;
    scanf("%d %d %d", &N, &M, &C);

    int B[M];
    for (int i = 0; i < M; i++) {
        scanf("%d", &B[i]);
    }
  
    int A[N][M];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            scanf("%d", &A[i][j]);
        }
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            total += A[i][j] * B[j];
        }

        if (total+C > 0) {
            ans += 1;
        }
        total = 0;
    }

    printf("%d", ans);

    return 0;
}


Measured memory_bytes: 128
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int n,m;
ll L;
ll dist[305][305];
ll D[305][305];
int main(){
	cin>>n>>m>>L;
	rep(i,305)rep(j,305) if(i!=j)dist[i][j] = 1e18;
	rep(i,m){
		int a,b,c; cin >> a >> b >> c;
		dist[a][b] = dist[b][a] = c;
	}
	repn(k,n)repn(i,n) repn(j,n) dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);
	
	rep(i,305)rep(j,305) if(i!=j)D[i][j] = 1e18;
	repn(i,n) repn(j,n) if(dist[i][j] <= L) D[i][j] = 1;
	repn(k,n)repn(i,n) repn(j,n) D[i][j] = min(D[i][j],D[i][k]+D[k][j]);

	int q; cin >> q;
	rep(i,q){
		int s,t; cin >> s >> t;
		if(D[s][t] > INF) cout << -1 << endl;
		else cout << D[s][t]-1 << endl;
	}
}

Measured memory_bytes: 1920
#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
int main(){
	//~ #ifndef ONLINE_JUDGE
    //~ freopen("file.in", "r", stdin);
	//~ #endif	
	ll a,b,c;
	int cnt=0;
	cin>>a>>b>>c;
	while(!(a&1 or b&1 or c&1)){
		ll aa=(b+c)/2;
		ll bb=(a+c)/2;
		ll cc=(b+a)/2;
		if(a==a and b==bb and c==cc)
			return 0*puts("-1");
		a=aa;b=bb;c=cc;cnt++;
	}
	printf("%d\n",cnt);
	return 0;
}


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

string fixedNum( string s, int l )
{
    while( s.size() != l )
        s += "0";
    return s;
}

string reverse( string s )
{
    string a = "";
    for( int i = s.size() - 1; i >= 0; i-- )
        a += s[i];
    return a;
}

int stringToInt( string s )
{
    int sum = 0, d = 1;
    for( int i = s.size() - 1; i >= 0; i-- )
    {
        sum += ( s[i] - '0' ) * d;
        d *= 10;
    }
    return sum;
}

string intToString( int a )
{
    string s = "";
    while( a != 0 )
    {
        s += ( a % 10 + '0' );
        a /= 10;
    }
    return s;
}

string bubbleSort( string s )
{
    for( int i = 0; i < s.size(); i++ )
        for( int j = s.size() - 1; j >= i + 1; j-- )
            if( s[j] > s[j-1] )
            {
                char t = s[j];
                s[j] = s[j-1];
                s[j-1] = t;
            }
    return s;
}

int main()
{
    string a, s;
    int b, c[22];

    while( cin >> a >> b )
    {
        if( a == "0" &&  b == 0 )
            break;
        s = "";

        a = fixedNum( a, b );
        c[0] = stringToInt( a );
        a = bubbleSort( a );
        for( int i = 1; i < 21; i++ )
        {
            c[i] = stringToInt( a ) - stringToInt( reverse( a ) );
            a = intToString( c[i] );
            a = fixedNum( a, b );
            a = bubbleSort( a );
        }

        bool judge = false;
        for( int i = 0; i < 21; i++ )
        {
            for( int j = i + 1; j < 22; j++ )
                if( c[i] == c[j] )
                {
                    cout << i << " " << c[i] << " " << j - i << endl;
                    judge = true;
                    break;
                }
            if( judge )
                break;
        }
    }
    return 0;
}


Measured memory_bytes: 3156
# -*- coding: utf-8 -*-
"""
Created on Sun Jan  6 20:37:21 2019

@author: Yamazaki Kenichi
"""

N = int(input())
act = [list(map(int,input().split())) for i in range(N)]
act = [0]+act
u = [0]

for i in range(1,N+1):
    if i == 1:
        u.append(act[1])
    else:
        ui = []
        ui.append(max(u[i-1][1],u[i-1][2])+act[i][0])
        ui.append(max(u[i-1][0],u[i-1][2])+act[i][1])
        ui.append(max(u[i-1][0],u[i-1][1])+act[i][2])
        u.append(ui)
    
ans= max(u[N])
print(ans)

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

kouho = [1 for i in range(N)]

for i in range(M):
  A, B = map(int, input().split())
  if H[A-1] < H[B-1]:
    kouho[A-1] = 0
  elif H[A-1] > H[B-1]:
    kouho[B-1] = 0
  else:
    kouho[A-1] = 0
    kouho[B-1] = 0
ans = sum(kouho)
print(ans)

Measured memory_bytes: 20140
#from bisect import bisect_left as bl                #c++ lowerbound bl(array,element)
#from bisect import bisect_right as br               #c++ upperbound br(array,element)
#from __future__ import print_function, division    #while using python2


def modinv(n,p):
    return pow(n,p-2,p)

def main():
    #sys.stdin = open('input.txt', 'r')
    #sys.stdout = open('output.txt', 'w')

    n = int(input())
    s = input()
    c1 = s.count('W')
    c2 = s.count('R')

    c3 = s[:c2].count('W')
    print(min(c1, c3))

#------------------ Python 2 and 3 footer by Pajenegod and c1729-----------------------------------------
py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange

import os, sys
from io import IOBase, BytesIO

BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0
    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s
    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)

class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s:self.buffer.write(s.encode('ascii'))
            self.read = lambda:self.buffer.read().decode('ascii')
            self.readline = lambda:self.buffer.readline().decode('ascii')

sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')

if __name__ == '__main__':
   main()


Measured memory_bytes: 64120
//jinhaonan
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
template<class T>inline void read(T &x){
	x=0;char c=getchar();bool f=0;
	for(;c>'9'||c<'0';f=c=='-',c=getchar());
	for(;c>='0'&&c<='9';x=(x<<1)+(x<<3)+c-'0',c=getchar());
	x=f?-x:x;
}
template<class T>inline void write(T x){
	if(x<0)putchar('-'),x=-x;
	if(x>=10)write(x/10);
	putchar(x%10+48);
}
template<class T>inline bool chkmax(T &a,T const &b){
	return a<b?a=b,1:0;
}
template<class T>inline bool chkmin(T &a,T const &b){
	return a>b?a=b,1:0;
}
const int N=700+10;
int c[N],cnt[2],n;
bool g[N][N],f[2][N];
void dfs(int u,int col){
	c[u]=col;
	++cnt[col==1];
	for(int i=1;i<=n;++i){
		if(i==u||g[i][u])
			continue;
		if(!c[i]){
			dfs(i,-col);
		}else if(c[i]==col){
			puts("-1");
			exit(0);
		}
	}
}
int main(){
	// freopen("in.txt","r",stdin);
	int m;read(n),read(m);
	for(int i=1;i<=m;++i){
		int u,v;read(u),read(v);
		g[u][v]=g[v][u]=1;
	}
	f[0][0]=1;
	int p=1,q=0;
	for(int i=1;i<=n;++i){
		if(c[i])
			continue;
		cnt[0]=cnt[1]=0;
		dfs(i,1);
		p^=1,q^=1;
		memset(f[q],0,sizeof f[q]);
		for(int j=0;j<=n;++j){
			f[q][j+cnt[0]]|=f[p][j];
			f[q][j+cnt[1]]|=f[p][j];
		}
	}
	for(int i=n/2;i;--i){
		if(f[q][i]){
			write(i*(i-1)/2+(n-i)*(n-i-1)/2),putchar('\n');
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 768
import sys
sys.setrecursionlimit(10 ** 6)

n, m = list(map(int, input().split()))
data = [[] for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    data[a-1].append(b-1)
    data[b-1].append(a-1)

ans = 0


def dfs(pos, cnt, his):
    global ans
    his[pos] = 1
    if cnt == n:
        if sum(his) == n:
            ans += 1
        return

    for next in data[pos]:
        dfs(next, cnt+1, his[:])


dfs(0, 1, [0]*n)
print(ans)


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

int main()
{
    ll n ;
    cin >> n ;
    for(ll i = 1 ; i <= n ; i++)
    {
        if(i%3 == 0) cout << " " << i ;
        else
        {
            ll X = i ;
            while(X)
            {
                if(X%10 == 3)
                {
                    cout << " " << i ;
                    break ;
                }
                X /= 10 ;
            }
        }
    }
    cout << endl ;
}


Measured memory_bytes: 3116
#include <iostream>
#include <queue>
#include <cmath>
#define REP(i, a, n) for(int i = ((int) a); i < ((int) n); i++)
using namespace std;

struct state {
  int y, x, d, hy, hx, n;
  bool operator<(const state &s) const {
    return n > s.n;
  }
};

int N, M, D, SY, SX, GY, GX;
char S[52][52];
int dd[5] = { 0, 1, 0, -1, 0 };
bool visited[52][52][52][52][4];
bool step[52][52];

bool isin(int y, int x) {
  return 0 <= y && y < N + 2 && 0 <= x && x < M + 2;
}

bool ok(int y, int x, int d, int hy, int hx) {
  if(S[y][x] == '#') return false;
  if(S[hy][hx] != '#') return false;
  bool f = false;
  if(y + dd[d] == hy && x + dd[d + 1] == hx) f = true;
  if(y + dd[d] + dd[(d + 1) % 4] == hy && x + dd[d + 1] + dd[(d + 1) % 4 + 1] == hx) f = true;
  if(y + dd[(d + 1) % 4] == hy && x + dd[(d + 1) % 4 + 1] == hx) f = true;
  if(y + dd[(d + 1) % 4] + dd[(d + 2) % 4] == hy && x + dd[(d + 1) % 4 + 1] + dd[(d + 2) % 4 + 1] == hx) f = true;
  return f;
}

int main(void) {
  cin >> N >> M;
  REP(i, 0, N + 2) REP(j, 0, M + 2) S[i][j] = '#';
  REP(i, 1, N + 1) REP(j, 1, M + 1) {
    cin >> S[i][j];
    if(S[i][j] == '>') SY = i, SX = j, D = 0;
    if(S[i][j] == 'v') SY = i, SX = j, D = 1;
    if(S[i][j] == '<') SY = i, SX = j, D = 2;
    if(S[i][j] == '^') SY = i, SX = j, D = 3;
    if(S[i][j] == 'G') GY = i, GX = j;
  }

  REP(i, 0, 52) REP(j, 0, 52) REP(k, 0, 52) REP(l, 0, 52) REP(m, 0, 4) visited[i][j][k][l][m] = false;
  REP(i, 0, 52) REP(j, 0, 52) step[i][j] = false;
  priority_queue<state> q;
  q.push((state) { SY, SX, D, SY + dd[(D + 1) % 4], SX + dd[(D + 1) % 4 + 1], 1 });

  int ans = -1;
  while(q.size()) {
    state s = q.top();
    q.pop();

    if(visited[s.y][s.x][s.hy][s.hx][s.d]) continue;
    visited[s.y][s.x][s.hy][s.hx][s.d] = true;
    step[s.y][s.x] = true;

    if(s.y == GY && s.x == GX) {
      ans = s.n;
      break;
    }

    REP(i, -1, 2) {
      int nd = (s.d + i + 4) % 4;
      int ny = s.y + (i == 0 ? dd[nd] : 0);
      int nx = s.x + (i == 0 ? dd[nd + 1] : 0);
      int nhy = s.hy;
      int nhx = s.hx;
      int nn = s.n + (i == 0 && !step[ny][nx] ? 1 : 0);
      if(ok(ny, nx, nd, nhy, nhx)) {
        q.push((state) { ny, nx, nd, nhy, nhx, nn });
      }
    }

    REP(i, -1, 2) REP(j, -1, 2) {
      if(i == 0 && j == 0) continue;
      int nd = s.d;
      int ny = s.y;
      int nx = s.x;
      int nhy = s.hy + i;
      int nhx = s.hx + j;
      int nn = s.n;
      if(isin(nhy, nhx) && ok(ny, nx, nd, nhy, nhx)) {
        q.push((state) { ny, nx, nd, nhy, nhx, nn });
      }
    }
  }
  cout << ans << endl;

  return 0;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const ld EPS = 1e-11;
const ld PI = acos(-1.0);
const int INF = (int)1e9 + 5;
const ll LINF = (ll)1e18 + 5;

template<class T> 
ll abs(const T & x) { return x < 0 ? -x : x; }

template<class T> 
ll round(const T & x) { return x < 0 ? x - 0.5 : x + 0.5; }

template<class T> 
bool chmin(T & x, const T & y) {
	if (y < x) {
		x = y;
		return true;
	}
	return false;
}

template<class T> 
bool chmax(T & x, const T & y) {
	if (x < y) {
		x = y;
		return true;
	}
	return false;
}

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

ll foo(ll w, ll h) {
	if (w == 0) return 0;
	if (h == 0) return 0;
	cerr << w << " " << h << endl;
	if (h < w) {
		ll k = w / h;
		if (w - k * h == 0) return k * h * 2 + foo(w - k * h, h) - h;
		return k * h * 2 + foo(w - k * h, h);
	}
	
	ll k = h / w;
	if (h - k * w == 0) return k * w * 2 + foo(w, h - k * w) - w;
	return k * w * 2 + foo(w, h - k * w);
}

ll triangle(ll n, ll x) {
	return n + foo(x, n - x);
}

int main() {
#ifdef LOCAL 
	freopen("input.txt", "r", stdin);
#else
#endif


	ll n, k;

	cin >> n >> k;

	cout << triangle(n, k) << endl;

}

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

#define whole(f, x, ...)                                 \
  ([&](decltype((x)) whole) {                            \
    return (f)(begin(whole), end(whole), ##__VA_ARGS__); \
  })(x)

using namespace std;
using ll = long long;

void solve() {
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  while (a > 0 && c > 0) {
    c -= b;
    if (c <= 0) {
      cout << "Yes\n";
      return;
    }
    a -= d;
    if (a <= 0) {
      cout << "No\n";
      return;
    }
  }
}

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);

  solve();
  return 0;
}


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

int main(){
	
	int a,b,t;
	char c[2];

	scanf("%d %s %d", &a, &c[0], &b);

	if (c[0] == '+'){
	 t = a + b;
	} else if (c[0] == '-'){
		t = a - b;
	}

	printf("%d\n", t);
	
	return 0;
}	

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

int main()
{
    int i,n;
  	cin>>n;
  	int s[4]={0,0,0,0};
  	string si[n];
    
	for(i=0;i<n;i++)
      cin>>si[i];
  	for(i=0;i<n;i++)
    {
      if(si[i]=="AC")
         s[0]++;
      else if(si[i]=="WA")
         s[1]++;
      else if(si[i]=="TLE")
         s[2]++;
      else
         s[3]++;
     }
     cout<<"AC x "<<s[0]<<endl;
     cout<<"WA x "<<s[1]<<endl;
     cout<<"TLE x "<<s[2]<<endl;
     cout<<"RE x "<<s[3]<<endl;
         
	return 0;
}






Measured memory_bytes: 6580
S = input()
T = input()
s = len(S)
t = len(T)
for i in range(s - t, -1, -1):
    SS = S[i : i + t]
    for j in range(t):
        if SS[j] != '?' and SS[j] != T[j]:
            break
    else:   # 見つかった
        ans = S.replace('?', 'a')
        ans = ans[0 : i] + T + ans[i + t :]
        break
else:   # なかった
    ans = 'UNRESTORABLE'

print(ans)

Measured memory_bytes: 8992
#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    long long sum = 0;
    for(long long i = 1; i <= n; i++)
        if(!(i % 3 == 0 || i % 5 == 0))
            sum += i;
    cout << sum << endl;
  	return 0;
}


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

public class Hello
{
    public static void Main()
    {
        var n = int.Parse(Console.ReadLine().Trim());
        string[] line = ("0 " + Console.ReadLine().Trim()).Split(' ');
        var a = Array.ConvertAll(line, int.Parse);
        getAns(a, n);

    }
    static void getAns(int[] a, int n)
    {
        var b = new int[n + 1];
        var ans = new List<int>();
        for (int i = n; i >= 1; i--)
        {
            if (a[i] != getSum(b, n, i) % 2) { b[i] = 1; ans.Add(i); }
        }
        var ansc = ans.Count();
        Console.WriteLine(ansc);
        if (ansc != 0)
        {
            var ans2 = ans.ToArray();
            Array.Reverse(ans2);
            Console.WriteLine(string.Join(" ", ans2));
        }
    }
    static int getSum(int[] b, int n, int t)
    {
        var p = 1;
        var sum = 0;
        var t2 = t;
        while (true)
        {
            t2 = t * p++;
            if (t2 > n) break;
            sum += b[t2];
        }
        return sum;
    }
}


Measured memory_bytes: 35672
import java.io.PrintWriter

fun main(args: Array<String>) {
    PrintWriter(System.out).use { out ->
        solve(out)
        out.flush()
    }
}

fun solve(out: PrintWriter) {
    val n = readInteger()
    val aList = readLongList().sortedDescending()
    var a = 0L
    var b = 0L
    var i = 0
    while (i < n - 1) {
        if (aList[i] == aList[i + 1]) {
            if (a == 0L) {
                a = aList[i]
            } else {
                b = aList[i]
                break
            }
            i++
        }
        i++
    }
    println(a * b)
}

fun readInteger() = readLine()!!.toInt()
fun readLong() = readLine()!!.toLong()
fun readStringList() = readLine()!!.split(" ")
fun readIntegerList() = readStringList().map(String::toInt)
fun readLongList() = readStringList().map(String::toLong)
fun readDoubleList() = readStringList().map(String::toDouble)


Measured memory_bytes: 60260
#include "iostream"
#include "vector"
#include "iomanip"
#include "algorithm"

long long sqrtL(long long n) {
	long long i;
	for (i = 1; i * i <= n; ++i);
	return i - 1;
}

long long div(long long n) {
	for (long long i = sqrtL(n); i > 1; --i)
		if (n % i == 0)
			return i;
	return 1;
}

int main() {
	long long n, tmp, ans;
	std::cin >> n;

	tmp = div(n);
	ans = tmp + n / tmp - 2;

	std::cout << ans;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
#define vii vector<int>
#define task "ABC"
#define pll pair<ll, ll>
#define pii pair< ll, pair< ll, ll > >
#define fi first
#define se second

using ll = long long;
using ld = long double;
using ull = unsigned long long;
const ll mod = 1e9 + 7;
using namespace std;
const int N = 2e5+5;
ll tong, m, n, k, t, T, ntest, ans, u, v, b[N], P[N][20], lab[N], sum[N];
string s;
ll a[N], d[N][53];
vector<pii> kq;
vector<pll> adj[N], adt[N];
bool check;
ll findp(ll u)
{
    return lab[u] < 0 ? u : lab[u] = findp(lab[u]);
}
void hop(ll u, ll v)
{
    if(lab[u] > lab[v])swap(u, v);
    lab[u] += lab[v];
    lab[v] = u;
    ans = max(ans, -lab[u]);
}
inline void sol()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
        lab[i] = -1;
    }
    ans = 1;
    while(m -- > 0)
    {
        ll x, y;
        cin >> x >> y;
        u = findp(x), v= findp(y);
        if(u != v)
            hop(u, v);
    }
    cout << ans;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    sol();

}





Measured memory_bytes: 14540
A, B, M = map(int, input().split())
lis_a = list(map(int, input().split()))
lis_b = list(map(int, input().split()))
lis_m = [list(map(int, input().split())) for m in range(M)]


dp_min = [2*10**5]*len(lis_m)
dp_min[0] = lis_a[(lis_m[0][0]-1)] + lis_b[(lis_m[0][1]-1)] - lis_m[0][2]
for m in range(1, len(lis_m)):
    ind_a = lis_m[m][0]-1
    ind_b = lis_m[m][1]-1
    c = lis_m[m][2]
    dp_min[m] = min(dp_min[m-1], (lis_a[ind_a] + lis_b[ind_b] - c))

p_not_coupon = min(lis_a)+min(lis_b)
ans = min(dp_min[-1], p_not_coupon)
print(ans)


Measured memory_bytes: 39332
n,k=map(int,input().split())
p=list(map(int,input().split()))
for i in range(n):
    p[i]=(p[i]+1)/2
ans=sum(p[:k])
x=ans
for i in range(1,n-k+1):
    x+=p[i+k-1]-p[i-1]
    ans=max(x,ans)
print(ans)


Measured memory_bytes: 25060
#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
 
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("-ffloat-store")
 
#define int  long long
#define rep(i,begin,end) for(__typeof(end)i=(begin)-((begin)>(end));i!=(end)-((begin)>(end));i+=1-2*((begin)>(end)))
#define F first
#define S second
#define sz(x) ((int)x.size())
#define pb push_back
#define pf push_front
#define eb emplace_back
#define all(v) (v).begin(), (v).end()
#define mod 1000000007
#define what_is(x) cerr << #x << " is " << x <<"\n";
#define sortA(v) sort(v.begin(), v.end())
#define sortD(v) sort(v.rbegin(), v.rend())
#define PI 3.14159265358979323846
#define vout(a) for(auto x:a) cout<<x<<" ";
#define INF 10000000000000000 //1e16
 
// #define ordered_set tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
 
 
// using namespace __gnu_pbds;
using namespace std;
 
using ll  = long long;
using vi  = vector<int>;
using pii = pair<int,int>;
using vii = vector<pii>;
using mi  = multiset<int>;
using mii = multiset<pii>;
 
int lcm(int a,int b) {return (a*(b/__gcd(a,b)));}



void solve()
{
    int t,n,m,i,k,r,l,u,v,w,j,s,sum=0,pos,flag=0,count=0;
    string S,T,U; 
    // int x,y;
    cin>>l>>r>>n;
    rep(i,l,r+1)
    {
        if(i%n==0) count++;
    }
    cout<<count;
    
}
 
 
signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--)
    {
        solve();
        if(t)cout<<"\n";
    }
    return 0;
}


Measured memory_bytes: 3616
#include <iostream>
#include <algorithm>
#include <string.h>
#include <cstdio>
#include <string>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
//#include <unordered_map>
#define Fbo friend bool operator < (node a, node b)
#define mem(a, b) memset(a, b, sizeof(a))
#define FOR(a, b, c) for (int a = b; a <= c; a++)
#define RFOR(a, b, c) for (int a = b; a >= c; a--)
#define off ios::sync_with_stdio(0)
#define sc(a) scanf("%d",&a)
#define pr(a) printf("%d\n",a);
#define SC(n,m) scanf("%d%d",&n,&m)
bool check1(int a) { return (a & (a - 1)) == 0 ? true : false; }

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int INF = 0x3f3f3f3f;//1e10
const int mod = 1e9 + 7;
const int Maxn = 1e5 + 5;
const int M = Maxn * 20;
const double pi = acos(-1.0);
const double eps = 1e-8;

int a[Maxn], k = 1;

bool is_prime(int x) {
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) {
            return 0;
        }
    }
    return 1;
}

int main() {
    ll n;
    cin >> n;
    cout << 3;
    for (int i = 11;i <= 55555 ; i++) {
        if (is_prime(i)&&i%10==3) {
            cout << " " << i;
            k++;
        }
        if (k == n)break;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using P = pair<int, int>;
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(x) (x).begin(),(x).end()
#define MAX(x) *max_element(ALL(x))
#define SIZE(x) ((ll)(x).size())
#define INF 1000000000000

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

int main() {
    int ans,cnt=1;
    while(1){
    cin >> ans;
    if (ans == 0) break;
    cout << "Case " << cnt << ": " << ans << endl;
    cnt++;
    }
}


Measured memory_bytes: 3000
#include <iostream>

int main()
{
	unsigned long long A, B, K;
	std::cin >> A >> B >> K;




	if (A < K) {
		// K回やってA枚がゼロになった
		K -= A;

		if (B < K) {
			// 残りK'回やってB枚がゼロになった
			std::cout << 0 << " " << 0 << std::endl;
		}
		else {
			// 残りK'回やってB枚に足りなかった
			std::cout << 0 << " " << B - K << std::endl;
		}
	}
	else {
		// K回やってA枚に足りなかった
		std::cout << A - K << " " << B << std::endl;
	}

	return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main ()
{
    int a[105][2],b[105][2],s1=0,s2=0,m=0,t,c=0,i,z;
    cin >> t;
    for(i=0;i<t;i++)
    {
        cin >> a[i][0];
        s1=s1+a[i][0];
        a[i][1]=s1;
    }
    for(i=0;i<t;i++)
    {
        cin >> b[i][0];
        s2=s2+b[i][0];
        b[i][1]=s2;
    }
    for(i=0;i<t;i++)
    {
        if(i==0)
        {
            c=a[i][0]+s2;
        }
        else if(i==t-1)
        {
            c=b[t-1][0]+s1;
        }
        else{
            c=a[i][1]+(s2-b[i-1][1]);
        }
        m=max(m,c);
    }
    cout << m; return 0;
}

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


int main(){

int n,a[111];
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
int ans=0;
for(int i=2;i<=n;i++){
    if( a[i]==a[i-1] ){
        ans++;
        a[i]=-1;
    }
}
cout<<ans<<endl;

return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
//#define mp make_pair
#define pii pair<int,int>
#define in freopen("input.txt", "r", stdin)
#define out freopen("output.txt", "w", stdout)  
#define rep(i,n) for(long long int (i)=0;(i)<(n);++(i))
#define ref(i,a,b) for (long long int (i)=(a); (i)<=(b); ++(i))
#define INF 0xFFFFFF
#define endl '\n'
const unsigned int mod = 1e9+7;
const int maxInt = 2147483647;
const int mx=21;
int mp[25][25];
int dp[1<<22];
int n;
int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    cin>>n;
	rep(i,n)rep(j,n)cin >> mp[i][j];
	dp[0]=1;
	for(int i=1;i<(1<<n);++i){
		int now=__builtin_popcount(i)-1;
		for(int j=0;j<n;++j){
			if(i&(1<<j)&&mp[now][j]){
				dp[i]=(dp[i]+dp[i^(1<<j)])%mod;
			}
		}
	}
	cout << dp[(1<<n)-1] << endl;
	//cout << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;
    return 0;
}


Measured memory_bytes: 10496
#include "bits/stdc++.h"
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(a)-1;i>=b;i--)
#define chmin(a,b) (a)=min((a),(b));
#define chmax(a,b) (a)=max((a),(b));
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define printV(v) cerr<<(#v)<<":";for(auto(x):(v)){cerr<<" "<<(x);}cerr<<endl;
#define printVS(vs) cerr<<(#vs)<<":"<<endl;for(auto(s):(vs)){cerr<<(s)<< endl;}
#define printVV(vv) cerr<<(#vv)<<":"<<endl;for(auto(v):(vv)){for(auto(x):(v)){cerr<<" "<<(x);}cerr<<endl;}
#define printP(p) cerr<<(#p)<<(p).first<<" "<<(p).second<<endl;
#define printVP(vp) cerr<<(#vp)<<":"<<endl;for(auto(p):(vp)){cerr<<(p).first<<" "<<(p).second<<endl;}

inline void output(){ cerr << endl; }
template<typename First, typename... Rest>
inline void output(const First& first, const Rest&... rest) {
    cerr << first << " "; output(rest...);
}

using ll = long long;
using Pii = pair<int, int>;
using TUPLE = tuple<int, int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
const int inf = 1ll << 60;
const int mod = 1e9 + 7;
using Graph = vector<vector<int>>;

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

  int a, b;
  cin >> a >> b;
  a--;
  b--;

  vector<string> s(100);
  rep(i, 100) {
    rep(j, 100) {
      if (i < 50) {
        if (i % 2 == 0 && j % 2 == 0 && a > 0) {
          s[i] += ".";
          a--;
        }
        else {
          s[i] += "#";
        }
      }
      else {
        if (i % 2 != 0 && j % 2 == 0 && b > 0) {
          s[i] += "#";
          b--;
        }
        else {
          s[i] += ".";
        }
      }
    }
  }

  cout << 100 << " " << 100 << endl;
  rep(i, 100) {
    cout << s[i] << endl;
  }
}


Measured memory_bytes: 256