akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define PI 3.141592653589
using namespace std;
using ll = long long;

template<typename T_char>
T_char ToUpper(T_char cX){return toupper(cX);}

int main(){
  int n;cin >> n;
  vector<int> v(n), c(n);
  for(int i=0; i<n; ++i) cin >> v[i];
  for(int i=0; i<n; ++i) cin >> c[i];
  int X=0, Y=0;
  for(int i=0; i<n; ++i){
    if(v[i]>c[i]){
      X += v[i];
      Y += c[i];
    }
  }
  cout << X-Y << endl;
}


Measured memory_bytes: 3600
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>
#include <utility>
#include <tuple>

#define REP(i, a, b) for (int i = int(a); i < int(b); i++)
using namespace std;
using ll = long long int;
using P = pair<ll, ll>;

// clang-format off
#ifdef _DEBUG_
#define dump(...) do{ cerr << __LINE__ << ":\t" << #__VA_ARGS__ << " = "; PPPPP(__VA_ARGS__); cerr << endl; } while(false)
template<typename T> void PPPPP(T t) { cerr << t; }
template<typename T, typename... S> void PPPPP(T t, S... s) { cerr << t << ", "; PPPPP(s...); }
#else
#define dump(...) do{ } while(false)
#endif
template<typename T> vector<T> make_v(size_t a, T b) { return vector<T>(a, b); }
template<typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v(ts...))>(a, make_v(ts...)); }
template<typename T> bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false; }
template<typename T> bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false; }
template<typename T> void print(T a) { cout << a << endl; }
template<typename T, typename... Ts> void print(T a, Ts... ts) { cout << a << ' '; print(ts...); }
template<typename T> istream &operator,(istream &in, T &t) { return in >> t; }
// clang-format on

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll n;
    cin, n;
    ll ans = n * (n + 1) * (n + 2) / 6;
    REP(i, 0, n - 1) {
        int a, b;
        cin, a, b;
        if (a > b) swap(a, b);
        ans -= a * (n - b + 1);
    }
    print(ans);
    return 0;
}


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

int gcd(int x,int y){

	if((x%y)==0){
		return y;
	}
	else{
		return gcd(y,x%y);
	}
}

int main(){

int n,i,j,k,ans,A;
ans = 0;
cin >> n;

  for(i=1;i<=n;i++){
	for(j=1;j<=n;j++){
		for(k=1;k<=n;k++){
		A=gcd(i,j);
		ans += gcd(A,k);
		}
	}
  }

	cout << ans << endl;

  return 0;
}

Measured memory_bytes: 3628
import java.io.BufferedReader
import java.io.InputStreamReader
import java.io.PrintWriter
import kotlin.math.max
import kotlin.math.min

val br = BufferedReader(InputStreamReader(System.`in`))
val out = PrintWriter(System.out)

fun main() {
    br.use { out.use {
        solve()
        out.flush()
    } }
}

fun solve() {
    val (n, m) = readIntegerList()
    val dp = LongArray(n + 5)
    dp[0] = 1
    val breakSet = mutableSetOf<Int>()
    repeat(m) { breakSet.add(readInteger()) }
    val mod = 1000000007
    for (i in 0 until n) {
        dp[i + 1] = if (breakSet.contains(i + 1)) dp[i + 1] else (dp[i + 1] + dp[i]) % mod
        dp[i + 2] = if (breakSet.contains(i + 2)) dp[i + 2] else(dp[i + 2] + dp[i]) % mod
    }
    out.println(dp[n])
}

fun readInteger() = Integer.parseInt(br.readLine())
fun readLong() = java.lang.Long.parseLong(br.readLine())
fun readStringList() = br.readLine()!!.split(' ')
fun readIntegerList() = readStringList().map(Integer::parseInt)
fun readLongList() = readStringList().map(java.lang.Long::parseLong)
fun readDoubleList() = readStringList().map(java.lang.Double::parseDouble)


Measured memory_bytes: 62552
w, h, n = [int(x) for x in input().split()]
xm, xM, ym, yM = 0, w, 0, h
for _ in range(n):
	x, y, a = [int(x) for x in input().split()]
	if a == 1: xm = max(xm, x)
	elif a == 2: xM = min(xM, x)
	elif a == 3: ym = max(ym, y)
	else: yM = min(yM, y)
if yM > ym and xM > xm: print((xM - xm) * (yM - ym))
else: print(0)


Measured memory_bytes: 3064
#include<stdio.h>

#define MAX 2000100

int A[2000100], B[2000100], C[2000100];
int n;

void countingSort()
{
	for (int i = 0; i < n; i++)
		C[A[i]]++;
	for (int i = 1; i <= MAX; i++)
		C[i] = C[i] + C[i - 1];
	for (int i = n - 1; i >= 0; i--)
	{
		B[C[A[i]] - 1] = A[i];
		C[A[i]]--;
	}

}

int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d", &A[i]);
	countingSort();
	for (int i = 0; i < n; i++)
	{
		if (i)
			printf(" ");
		printf("%d", B[i]);
	}
	printf("\n");
}


Measured memory_bytes: 25272
#include <stdio.h>
#include <string.h>

int main()
{
    int n, i;
    int Tp = 0, Hp = 0;
    scanf("%d", &n);
    
    for(i=0; i<n; i++){
        char Tw[1001] = {0};
        char Hw[1001] = {0};
        
        scanf("%s%s", Tw, Hw);
        if(strcmp(Tw, Hw)==0){
            Tp++; Hp++;
        } else if(strcmp(Tw, Hw) > 0){
            Tp+=3;
        } else Hp+=3;
    }
    printf("%d %d\n", Tp, Hp);
    return 0;
}

Measured memory_bytes: 604
//#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
 
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl '\n'
#define ll long long int
#define ld long double
#define vec vector
#define forn(a) for(ll a=0; a<n; a++)
#define all(x) x.begin(), x.end()
#define deb(x) cerr<<#x<<" = "<<x<<endl
 
using namespace std;
 
int main() {
    IOS;    

    string s, t; cin>>s>>t;
    int ans = 0;
    for(int i=0; i<3; i++){
        ans += s[i]==t[i];
    }
    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 256
from bisect import bisect_right
import sys
input=sys.stdin.readline


class LazySegTree():
    def __init__(self, N):
        self.INF = 2**31-1
        self.LV = (N-1).bit_length()
        self.N0 = 2**self.LV
        self.data = [0]*(2*self.N0)
        self.lazy = [0]*(2*self.N0)

    def gindex(self, l, r):
        L = (l + self.N0) >> 1; R = (r + self.N0) >> 1
        lc = 0 if l & 1 else (L & -L).bit_length()
        rc = 0 if r & 1 else (R & -R).bit_length()

        m = []
        for i in range(self.LV):
            if rc <= i:
                m.append(R)
            if L < R and lc <= i:
                m.append(L)
            L >>= 1; R >>= 1
        
        return m
    
    # 遅延伝搬処理
    def propagates(self, *ids):
        for i in reversed(ids):
            v = self.lazy[i-1]
            if not v:
                continue
            self.lazy[2*i-1] += v; self.lazy[2*i] += v
            self.data[2*i-1] += v; self.data[2*i] += v
            self.lazy[i-1] = 0

    # 区間[l, r)にxを加算
    def update(self, l, r, x):
        ids = self.gindex(l, r)
        self.propagates(*ids)

        L = self.N0 + l; R = self.N0 + r
        while L < R:
            if R & 1:
                R -= 1
                self.lazy[R-1] += x; self.data[R-1] += x
            if L & 1:
                self.lazy[L-1] += x; self.data[L-1] += x
                L += 1
            L >>= 1; R >>= 1
        for i in ids:
            self.data[i-1] = max(self.data[2*i-1], self.data[2*i])
    
    # 区間[l, r)内の最小値を求める
    def query(self, l, r):
        self.propagates(*self.gindex(l, r))
        L = self.N0 + l; R = self.N0 + r

        s = -self.INF
        while L < R:
            if R & 1:
                R -= 1
                s = max(s, self.data[R-1])
            if L & 1:
                s = max(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

    def set_list(self, l, N):
        for i in range(N):
            self.data[i+self.N0-1] = l[i]
        for i in range(self.N0-1)[::-1]:
            self.data[i] = max(self.data[2*i+1], self.data[2*i+2])


def solve():
    N, D, A = map(int, input().split())
    tree = LazySegTree(N)

    m, l = zip(*sorted(tuple(map(int, input().split())) for _ in range(N)))
    tree.set_list(l, N)

    ans = 0
    for i, j in enumerate(m):
        v = tree.query(i, i+1)
        if v>0:
            c = (v+A-1)//A
            ans += c
            pos = bisect_right(m, j+2*D)
            tree.update(i, pos, -c*A)

    print(ans)


if __name__ == "__main__":
    solve()

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

const int INF = 1 << 30;
int eval_exp(int x, int y, char op) {
    if(op == '/' && y == 0) return INF;

    if(op == '+') return x + y;
    if(op == '-') return x - y;
    if(op == '*') return x * y;
    if(op == '/') return x / y;
    return INF;
}

string ops = "+-/*";
set<int> parse(string s, int l, int r) {
    int level = 0;
    vector<int> op_idx;

    for(int i=l; i<r; i++) {
        if     (s[i] == '(') level++;
        else if(s[i] == ')') level--;
        else {
            if(level == 0 && ops.find(s[i]) != string::npos) {
                op_idx.push_back(i);
            }
        }
    }

    if(op_idx.size()) {
        set<int> ret;
        for(auto piv : op_idx) {
            set<int> lhs = parse(s, l, piv);
            set<int> rhs = parse(s, piv+1, r);

            for(auto x : lhs) {
                for(auto y : rhs) {
                    int num = eval_exp(x, y, s[piv]);
                    if(num == INF) continue;
                    ret.insert(num);
                }
            }
        }
        return ret;
    }
    else {
        if(s[l] == '(') return parse(s, l+1, r-1);
        int value = 0;
        for(int i=l; i<r; i++) {
            value = (value * 10 + (s[i] - '0'));
        }
        return set<int>{value};
    }
}

int main() {
    string s;
    while(cin >> s, s != "#") {
        int len = s.length();
        cout << parse(s, 0, len).size() << endl;
    }
    return 0;
}


Measured memory_bytes: 3228
#include<bits/stdc++.h>
using namespace std;
typedef long long int LL;
int main()
{
  LL n,k;
  cin>>n>>k;
  LL f=0;
 n=n-(n/k)*k;
 if(abs(n-k)<n)
 n=abs(n-k);
 cout<<n<<endl;
 return 0;
}

Measured memory_bytes: 384
require 'tsort'
require 'set'

class Hash
    include TSort
    alias tsort_each_node each_key
    def tsort_each_child(u)
        self[u].each do |v|
            yield(v)
        end
    end
end

loop do
    n = gets.to_i
    break if n == 0
    g = {}
    sleep_prob = []
    n.times do |i|
        g[i] = Set.new
        q, _, *neighbours = gets.split.map(&:to_f)
        sleep_prob[i] = q
        neighbours.each do |j|
            g[i] << j.to_i - 1
        end
    end
    scc = g.strongly_connected_components
    dict = {}
    scc.each.with_index do |a, i|
        a.each do |j|
            dict[j] = i
        end
    end

    roots = Set[*(0..scc.size-1).to_a]
    g.each_key do |i|
        g[i].each do |j|
            next if dict[i] == dict[j]
            roots.delete(dict[j])
        end
    end

    ans = roots.map {|i| 1 - scc[i].map {|j| sleep_prob[j]}.inject(:*)}.inject(:*)
    printf("%.9f\n", ans)
end

Measured memory_bytes: 11540
H, W = map(int, input().split())
T = [[] for i in range(H)]
b = 0
for i in range(H):
    T[i] = list(input())
    for j in range(W):
        if T[i][j] == '#':
            b += 1

que = [(0, 0, 1)]
while que:
    x, y, k = que.pop(0)
    if x == H - 1 and y == W - 1:
        print(H * W - b - k)
        exit()

    for dx, dy in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
        nx, ny = x + dx, y + dy
        if 0 <= nx < H and 0 <= ny < W and T[nx][ny] == '.':
            T[nx][ny] = '#'
            que.append((nx, ny, k + 1))
print(-1)

Measured memory_bytes: 3064
/**So..a**/
#include<bits/stdc++.h>
//#include <chrono>
// Success after trying 5 hour 11 minute :(


using namespace std;
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

#define PB(x, v) x.push_back(v);
#define M_P(a, b) make_pair(a, b)
#define pll pair<ll, ll>
#define ll long long
#define mll map<ll, ll>
#define vl vector<ll>
#define fa(x, v) for(auto x: v)
#define fr(i, a, b) for(ll i= a;i <=b; i++)
#define TEST  int test; cin >> test; while(test--)
#define FTEST int TesT; cin >> TesT; for(int test = 1; test<=TesT; test++)

#define B_ begin()
#define E_ end()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define NL_ "\n"
#define F first
#define S second
#define FF first.first
#define FS first.second
#define SF second.first
#define SS second.second

#define MOD 1000000000+7
#define  ull unsigned long long



int main()
{

    string s;
    cin >> s;
    cout << s;
    if(s.back()=='s')   cout<<"es";
    else cout << "s";


    return 0;
}


Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
#define int long
using pi=pair<int,int>;
signed main(){
    int n;
    cin >> n;
    while(n){
        if (n % 10 == 7) return cout << "Yes", 0;
        n /= 10;
    }
    cout << "No";
}

Measured memory_bytes: 3636
s = input()
sum = 0
R = 0
L = 0
flag = 0
for i in range(len(s)):
  if s[i] == "<" and L != 0:
    if L >= R:
      sum += L*(L+1)//2 + R*(R-1)//2
    else:
       sum += L*(L-1)//2 + R*(R+1)//2
    R = 0
    L = 0
  if s[i] == "<":
    R += 1 
  else:
    L += 1
    flag += 1
if L >= R:
  sum += L*(L+1)//2 + R*(R-1)//2
else:
  sum += L*(L-1)//2 + R*(R+1)//2

print(sum)
    
    

Measured memory_bytes: 4116
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <cassert>
#include <utility>
#include <iomanip>
#include <chrono>
#include <random>
#include <bitset>

using namespace std;

#define sz(x) (int) x.size()
#define unique(x) x.erase(unique(x.begin(), x.end()), x.end())
#define all(a) a.begin(), a.end()
#define sqr(x) ((x) * (x)) 
#define y1 aksjdaskdjksjfksdjf
#define left kdnvldvoiwejifejg
#define right lkdsjflksdjfdjfk
#define prev asdasfsadjkjsdfjs
#define tm aklsjdasjdasjdkdjjf
#define lcm hddalkwjeidjjhasda
#define random_shuffle asdasdd

const int MAXN = 1000500;

string s;
int dp[MAXN][2];
int carry[MAXN];
long long ans = 0;

int main() { 

  getline(cin, s);
  s = "0" + s;

  for (int i = sz(s) - 1; i >= 0; i--) {
    for (int j = 0; j < 2; j++) {
      int cur = s[i] - '0';
      if (i == sz(s) - 1) {
        if (j == 0) {
          dp[i][j] = min(cur, 1 + 10 - cur);
        } else {
          dp[i][j] = min(10 - cur, 1 + cur);
        }
        continue;
      }
      if (j == 0) {
        int a = min(cur, 1 + 10 - cur) + dp[i + 1][0];
        int b = 1 + (10 - (cur + 1)) + dp[i + 1][1];
        dp[i][j] = min(a, b);
      } else {
        int a = (10 - cur) + dp[i + 1][0];
        int b = (10 - (cur + 1)) + dp[i + 1][1];
        dp[i][j] = min(a, b);
      }
    }
  }

  /* for (int i = 0; i < sz(s); i++) {
    cerr << dp[i][0] << " " << dp[i][1] << endl;
  } */

  cout << min(dp[0][0], 1 + dp[0][1]) << endl;

  return 0;
}


Measured memory_bytes: 11056
import std.algorithm, std.container, std.conv, std.math, std.range, std.typecons, std.stdio, std.string;

auto rdsp(){return readln.splitter;}
void pick(R,T)(ref R r,ref T t){t=r.front.to!T;r.popFront;}
void readV(T...)(ref T t){auto r=rdsp;foreach(ref v;t)pick(r,v);}
void readA(T)(size_t n,ref T[]t){t=new T[](n);auto r=rdsp;foreach(ref v;t)pick(r,v);}

void main()
{
  int n, k; readV(n, k);
  int[] v; readA(n, v);

  auto r = 0;
  foreach (a; 0..n+1)
    foreach (b; 0..n+1) {
      if (a+b > n || a+b > k) continue;
      auto w = (v[0..a] ~ v[$-b..$]).dup;
      w.sort();
      foreach (i; 0..min(w.length, k-a-b))
        if (w[0] < 0) w = w[1..$];
        else break;
      r = max(r, w.sum);
    }

  writeln(r);
}


Measured memory_bytes: 764
N, A, B = map( int, input().split())
H = [0]*N
hmax = 0
for i in range(N):
    h = int( input())
    H[i] = h
hmax = max(H)
L = 0
R = hmax//B + 1
add = A-B
while L != R:
    now = (L+R)//2
    need = 0
    for i in range(N):
        r = H[i] - now*B
        if r > 0:
            need += (r-1)//add+1
    if need <= now:#うまくいくとき
        R = now
    else:#うまくいかないとき
        L = now+1#うまく行かないので+1している．これがないと無限ループが発生する。
print(L)

Measured memory_bytes: 6900
fun main(arg: Array<String>) {
    val (N, K) = listOfInt()
    val XY = Array(N) { listOfLong().toLongArray() }.sortedBy { it[0] }.toTypedArray()
    var ans = Long.MAX_VALUE
    for (xi in 0 until N) for (xj in xi + 1 until N)
        for (yi in 0 until N) for (yj in yi + 1 until N) {
            var count = 0
            val (x0, x1) = listOf(XY[xi][0], XY[xj][0])
            val (y0, y1) = listOf(XY[yi][1], XY[yj][1]).sorted()
            for (n in 0 until N)
                if (XY[n][0] in x0 .. x1 && XY[n][1] in y0 .. y1) count += 1
            if (count >= K) ans = Math.min(ans, (x1 - x0) * (y1 - y0))
        }
    println(ans)
}
//50^4=6250000

fun next() = readLine()!!
fun nextInt(delta: Int = 0) = Integer.parseInt(next()) + delta
fun listOfString() = next().split(" ")
fun listOfInt(d: Int = 0) = listOfString().map { Integer.parseInt(it) + d }
fun listOfLong() = listOfString().map(String::toLong)
fun listOfDouble() = listOfString().map { it.toDouble() }


Measured memory_bytes: 117688
using System;
class Program{
	static void Main(){
		int n=int.Parse(Console.ReadLine());
		int[] t=Array.ConvertAll(Console.ReadLine().Split(),int.Parse);
		int[] v=Array.ConvertAll(Console.ReadLine().Split(),int.Parse);
		int a=0,b=0,c=t[0]*2;
		for(int i=0;i<n;i++){b+=t[i];}
		b*=2;
		double[] h=new double[b+1];
		double ans=0;
		for(int i=1;i<b;i++){
			if(i>c){a++;c+=t[a]*2;}
			h[i]=Math.Min(h[i-1]+0.5,v[a]);
		}
		c-=t[n-1]*2;
		for(int i=b-1;i>=0;i--){
			if(i<c){a--;c-=t[a]*2;}
			h[i]=Math.Min(Math.Min(h[i+1]+0.5,v[a]),h[i]);
			ans+=Math.Abs(h[i]-h[i+1])*0.25+Math.Min(h[i],h[i+1])*0.5;
		}
		Console.WriteLine("{0}",ans);
	}
}

Measured memory_bytes: 13268
#include"bits/stdc++.h"
using namespace std;
#define REP(k,m,n) for(int (k)=(m);(k)<(n);(k)++)
#define rep(i,n) REP((i),0,(n))
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using tp3 = tuple<int, int, int>;
using Mat = vector<vector<ll>>;
constexpr int INF = 1 << 28;
constexpr ll INFL = 1ll << 60;
constexpr int dh[4] = { 0,1,0,-1 };
constexpr int dw[4] = { -1,0,1,0 };
bool isin(const int H, const int W, const int h, const int w) {
    return 0 <= h && h < H && 0 <= w && w < W;
}
// ============ template finished ============

int main()
{
    int N;
    cin >> N;
    map<int, int> f;
    REP(x, 1, 101)REP(y, 1, 101)REP(z, 1, 101) {
        f[x*x + y * y + z * z + x * y + y * z + z * x]++;
    }
    REP(i, 1, N + 1)cout << f[i] << endl;
    return 0;
}


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

int cmp(const void *a, const void *b){
// qsort

return *(int*)b - *(int*)a;
}

int main(void){

int n;cin>>n;
int mat[n][2];

int col = n;
int row = 2;

for(int i=0;i<n;++i){
    for(int j=0;j<2;++j){
        cin>>mat[i][1-j];
    }
}

qsort(mat, col, sizeof(mat[0]), cmp);

int sum = 0;
int ans = 0;

for(int i=0;i<n;++i){
    sum+=mat[n-1-i][1];
    if(sum>mat[n-1-i][0])ans=1;
//  cout<<sum<<" "<<ans<<endl;
}

if(ans==1)cout<<"No"<<endl;
else cout<<"Yes"<<endl;

return 0;
}

Measured memory_bytes: 3324
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		main : for (int i = 0; i < n; i++) {
			int a = 0, b = 0;
			int[] nums = {sc.nextInt(),sc.nextInt(),sc.nextInt(),sc.nextInt(),sc.nextInt(),sc.nextInt(),sc.nextInt(),sc.nextInt(),sc.nextInt(),sc.nextInt()};
			for (int p : nums) {
				if (p < Math.min(a, b)) {
					System.out.println("NO");
					continue main;
				}
				if (a > b && a < p || a == 0)
					a = p;
				else
					b = p;
			}
			System.out.println("YES");
		}

	}

}

Measured memory_bytes: 18096
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
typedef long long lng;
#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORD(i,b,a) for(int i=(b); i>=(a); --i)
#define REP(i,n) FOR(i,0,n-1)
#define ALL(a) (a).begin(), (a).end()
#define UNIQUE(a) a.erase(unique(ALL(a)), a.end()) //NOTE: <a> must be sorted in advance

lng power(lng b, lng n) {lng sol=1; while(n>0) {if(n&1) {sol=sol*b;} n>>=1; b*= b;} return sol;} //calculate b^n

const int MOD = 1000000007; //10^9+7


/*********** variables ************/
int a, b, c;
/**********************************/

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> a >> b >> c;

    cout << ((a-b==b-c) ? "YES" : "NO") << endl;
}


Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
)

var trainUF []int
var roadUF []int
var trainRank []int
var roadRank []int

func main() {
	r := bufio.NewReader(os.Stdin)
	w := bufio.NewWriter(os.Stdout)
	defer w.Flush()

	var n, k, l int
	fmt.Fscan(r, &n, &k, &l)

	trainUF = make([]int, n)
	roadUF = make([]int, n)
	trainRank = make([]int, n)
	roadRank = make([]int, n)
	for i := 0; i < n; i++ {
		trainUF[i] = -1
		roadUF[i] = -1
	}

	for i := 0; i < k; i++ {
		var p, q int
		fmt.Fscan(r, &p, &q)
		roadJoin(p-1, q-1)
	}
	for i := 0; i < l; i++ {
		var p, q int
		fmt.Fscan(r, &p, &q)
		trainJoin(p-1, q-1)
	}

	// for i := 0; i < n; i++ {
	// 	var count int
	// 	for j := 0; j < n; j++ {
	// 		if trainSame(i, j) && roadSame(i, j) {
	// 			count++
	// 		}
	// 	}

	// 	fmt.Fprintf(w, "%d ", count)
	// }

	trainRoots := make([]int, n)
	roadRoots := make([]int, n)
	rootSetMap := map[string]int{}
	for i := 0; i < n; i++ {
		tRoot := trainRoot(i)
		rRoot := roadRoot(i)
		trainRoots[i] = tRoot
		roadRoots[i] = rRoot
		key := fmt.Sprintf("%d#%d", tRoot, rRoot)
		v, _ := rootSetMap[key]
		v++
		rootSetMap[key] = v
	}

	for i := 0; i < n; i++ {
		key := fmt.Sprintf("%d#%d", trainRoots[i], roadRoots[i])
		v, _ := rootSetMap[key]
		fmt.Fprintf(w, "%d ", v)
	}

	fmt.Fprint(w, "\n")
}

func trainRoot(a int) int {
	if trainUF[a] == -1 {
		return a
	}
	return trainRoot(trainUF[a])
}

func trainJoin(a int, b int) {
	aRoot := trainRoot(a)
	bRoot := trainRoot(b)
	if aRoot == bRoot {
		return
	}

	if trainRank[aRoot] < trainRank[bRoot] {
		trainUF[aRoot] = bRoot
	} else {
		trainUF[bRoot] = aRoot
		if trainRank[aRoot] == trainRank[bRoot] {
			trainRank[aRoot]++
		}
	}

}

func trainSame(a int, b int) bool {
	return trainRoot(a) == trainRoot(b)
}

func roadRoot(a int) int {
	if roadUF[a] == -1 {
		return a
	}
	return roadRoot(roadUF[a])
}

func roadJoin(a int, b int) {
	aRoot := roadRoot(a)
	bRoot := roadRoot(b)
	if aRoot == bRoot {
		return
	}

	if roadRank[aRoot] < roadRank[bRoot] {
		roadUF[aRoot] = bRoot
	} else {
		roadUF[bRoot] = aRoot
		if roadRank[aRoot] == roadRank[bRoot] {
			roadRank[aRoot]++
		}
	}
}

func roadSame(a int, b int) bool {
	return roadRoot(a) == roadRoot(b)
}


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

#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define dump(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define dump(x)
#endif

typedef long long int ll;
typedef pair<int,int> pii;
//template<typename T> using vec=std::vector<T>;

const int inf=1<<30;
const long long int infll=1LL<<58;
const double eps=1e-9;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
    	os << v << ",";
    }
    os << "]";
    return os;
}

void solve(){
    const int dx[]={1,0,-1,-1,0,1};
    const int dy[]={0,-1,-1,0,1,1};
    auto calc=[&](const int n,const vector<vector<int>> s,const int self){
        int res=0;
        vector<vector<bool>> done(n);
        rep(i,0,n) done[i].resize(i+1);
        rep(i,0,n) rep(j,0,i+1) if(s[i][j] and !done[i][j]){
            int id=s[i][j];
            queue<pii> que;
            bool flag=true;
            done[i][j]=true;
            que.push(make_pair(j,i));
            int cnt=1;
            while(!que.empty()){
                pii p=que.front(); que.pop();
                rep(k,0,6){
                    int nx=p.first+dx[k];
                    int ny=p.second+dy[k];
                    if(nx<0 or ny<nx or ny<0 or n<=ny or done[ny][nx]) continue;
                    if(!s[ny][nx]) flag=false;
                    if(s[ny][nx]!=id) continue;
                    que.push(make_pair(nx,ny));
                    done[ny][nx]=true;
                    ++cnt;
                }
            }
            if(flag) res+=(s[i][j]==self?-cnt:cnt);
        }
        return res;
    };
    while(true){
        int n,c;
        cin >> n >> c;
        if(n==0 and c==0) break;
        vector<vector<int>> s(n);
        rep(i,0,n) s[i].resize(i+1);
        rep(i,0,n) rep(j,0,i+1) cin >> s[i][j];

        int ans=-inf;
        rep(i,0,n) rep(j,0,i+1) if(!s[i][j]){
            s[i][j]=c;
            ans=max(ans,calc(n,s,c));
            s[i][j]=0;
        }
        cout << ans << endl;
    }
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    cout << fixed << setprecision(8);
    solve();
    return 0;
}

Measured memory_bytes: 3160
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N, num;
  cin >> N;
  num = 1000000000;
  for (int i = 0; i < N; i++) {
    int A, n;
    cin >> A;
    n = 0;
    while ((A % 2) == 0) {
      A /= 2;
      n++;
    }
    if (num > n) {
      num = n;
    }
  }
  cout << num << endl;
}


Measured memory_bytes: 256
//#include "bits/stdc++.h"
#include <iostream>
#include <vector>
#include <map>
#include <utility>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <stack>
#include <queue>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <complex>
#include <bitset>
#include <functional>
#include <stack>
#include <regex>
#include <tuple>
#include <iomanip>

#define int long long
#define REP(i,l,r) REPEAT(i,l,r,true) // [l, r)
#define rep(i,n) REP(i,0,n)           // [0, n)
#define REPEAT(i,l,r,condition) for(int i=(condition)?l:r-1;(condition)?i<r:i>=l;(condition)?++i:--i) // false<-[l, r)->true
#define all(e) e.begin(),e.end()
#define rall(e) e.rbegin(),e.rend()
#define pb push_back
#define fs first
#define sc second
#define show(...) cerr<<#__VA_ARGS__<<" = ";_DEBUG(__VA_ARGS__)
#define showlr(n,l,r) cerr<<#n<<" = ";for(int i=l;i<r;i++){cerr<<n[i]<<", ";}cerr<<endl // [l, r)

#define YN(condition) puts((condition)?"YES":"NO")
#define Yn(condition) puts((condition)?"Yes":"No")
#define yn(condition) puts((condition)?"yes":"no")
#define YES puts("YES")
#define Yes puts("Yes")
#define yes puts("yes")
#define NO  puts("NO")
#define No  puts("No")
#define no  puts("no")

#define case(i) printf("Case #%lld: ",i)

using namespace std;

using vi=vector<int>;
using pint=pair<int,int>;

struct io{io(){cin.tie(0);ios::sync_with_stdio(false);cout.tie(0);cout<<fixed<<setprecision(20);}}io;

template<class T> istream& operator >>(istream &is, vector<T> &v){for(T &e:v)is>>e;return is;}
template<class T> ostream& operator <<(ostream &os, vector<T> v){os<<"{";for(T &e:v)os<<e<<(v.size()-(int)(&e-&v[0])>1?", ":"");os<<"}";return os;}

void _DEBUG(){}
template<typename H,typename... T> void _DEBUG(H a,T...b){cerr<<a<<(sizeof...(b)?",":"\n");_DEBUG(b...);}

inline void in(){}
template<typename H,typename... T>void in(H &a, T&... b){cin>>a;in(b...);}
inline void out(){}
template<typename H,typename... T> void out(H a, T... b){cout<<a<<(sizeof...(b)?" ":"\n");out(b...);}

template<class T> void resz(int n,T& v){v.resize(n);}
template<class H,class... T> void resz(int n,H& a,T&... b){a.resize(n);resz(n,b...);}

template<typename V,typename H> void resize(vector<V>& v,const H a){v.resize(a);}
template<typename V,typename H,typename... T> void resize(vector<V>& v,const H& a,const T... b){v.resize(a);for(auto &v:v) resize(v,b...);}

const int INF=1LL<<55;
const int MOD=1000000007;
const double EPS=1e-8;

int N,M;
vector<pint> vp;
int ans,cur;

signed main(){

    in(N,M);
    vp.resize(N);
    rep(i,N){
        in(vp[i].fs,vp[i].sc);
    }
    sort(all(vp));
    for(auto e:vp){
        if(cur+e.sc>=M){
            ans+=e.fs*(M-cur);
            break;
        }else{
            cur+=e.sc;
            ans+=e.fs*e.sc;
        }
    }

    out(ans);

    return 0;
}


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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<ll, pair<ll, ll> > P3;

const ll MOD = ll(1e9 + 7);
const ll LLINF = LLONG_MAX;
const int IINF = INT_MAX;
const int MAX_N = int(1e8) + 5;
const int MAX_A = int(15e6);
const double EPS = 1e-8;
const int di[] = {0, 1, 0, -1}, dj[] = {1, 0, -1, 0};
string dir = "RDLU";
#define REP(i, n) for (ll i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define SORT(v) sort((v).begin(), (v).end())
#define SORTR(v) sort((v).rbegin(), (v).rend())
#define ALL(v) (v).begin(), (v).end()

vector<bool> IsPrime;

void sieve(int max) {
    IsPrime.resize(max + 1, true);
    IsPrime[0] = IsPrime[1] = false;
    for (int i = 2; i * i <= max; ++i){
        if (IsPrime[i]){
            for (int j = i * i; j <= max; j += i) IsPrime[j] = false;
        }
    }
}

int main() {
    sieve(1000005);
    while(1){
        ll a, d, n;
        cin >> a >> d >> n;
        if(a == 0)break;
        int c = 1;
        while(1){
            if(IsPrime[a]){
                if(c == n){
                    cout << a << endl;
                    break;
                }
                else c++;
            }
            a += d;
        }
    }
    return 0;
}



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

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

    int H, A;
    cin >> H >> A;

    if(H%A >0)
    {
        cout << (H/A +1);
    }
    else
    {
        cout<<H/A;
    }

    return 0;
}

Measured memory_bytes: 256
mod=10**9+7
n,k=map(int,input().split())
A=list(map(int,input().split()))
K=k

B,C=[],[]
for i in A:
    if i>=0:B.append(i)
    else:C.append(i)

B.sort()
C.sort(key=lambda x:abs(x))

ans,flag=1,1
while k!=0:
    if k>=2:
        if len(B)>=2 and len(C)>=2:
            if B[-1]*B[-2]>C[-1]*C[-2]:
                ans *=B.pop()
                k -=1
            else:
                ans *=C.pop()*C.pop()
                k -=2
        elif len(B)>=2:
            ans *=B.pop()*B.pop()
            k -=2
        elif len(C)>=2:
            ans *=C.pop()*C.pop()
            k -=2
        else:
            k -=k
            flag=0
    else:
        if len(B)>=1:ans *=B.pop()
        else:flag=0
        k -=1

    ans %=mod

if flag:print(ans)
else:
    ans=1
    A=sorted(A,key=lambda x:abs(x))
    for i in range(K):
        ans *=A[i]
        ans %=mod
    print(ans)

Measured memory_bytes: 112564
def main():
    n = int(input())
    s = input().rstrip()
    ans = 0
    a = [[0]*3 for _ in range(n)]
    rgb = [None]*n
    for i in range(n):
        if s[i] == "R":
            rgb[i] = 0
        elif s[i] == "G":
            rgb[i] = 1
        else:
            rgb[i] = 2
    a[n-1][rgb[n-1]] += 1
    for i in reversed(range(n-1)):
        a[i][rgb[i]] += 1
        for j in range(3):
            a[i][j] += a[i+1][j]
    for i in range(n-2):
        for j in range(i+1, n-1):
            if rgb[i] == rgb[j]:
                continue
            x = 3 - rgb[i] - rgb[j]
            L = j + (j - i)
            ans += a[j+1][x]
            if L < n and rgb[L] == x:
                ans -= 1
    print(ans)

if __name__ == "__main__":
    main()

Measured memory_bytes: 9664
from collections import deque
n = int(input())
edge = [[] for i in range(n)]
for i in range(n-1):
    u,v,w = list(map(int, input().split()))
    edge[u-1].append((v-1, w%2))
    edge[v-1].append((u-1, w%2))

q =deque()
# start, iro
q.append((0,0))

ans = [-1]*n
while q:
    now, color = q.popleft()
    if ans[now] != -1:
        continue
    ans[now] = color
    for to_, w in edge[now]:
        if ans[to_] == -1:
            if w%2==0:
                q.append((to_, color))
            else:
                q.append((to_, (color+1)%2))
print(*ans, sep="\n")

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

int main(){
  int N,M;
  int ans=0;
  cin >> N >> M;
  vector<int> vec(N+2,0);
  for(int i=0;i<M;i++){
    int L,R;
    cin >> L >> R;
    vec[L]+=1;
    vec[R+1]-=1;
  }
  for(int i=0;i<N+1;i++){
    vec[i+1]+=vec[i];
  }
  for(int i=1;i<N+1;i++){
    if(vec[i]==M) ans++;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 768
fun main(array: Array<String>) {
    val n = readLine()!!.toInt()
    var list = mutableListOf<Int>()
    repeat(n) {
        var num = readLine()!!.toInt()
        list.add(num)
    }
    val copyList = list.toList().sorted()
    val max = copyList.max()
    val second = copyList[n-2]
    repeat(n) {
        if(list[it] == max) println(second)
        else println(max)
    }
}

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

using namespace std;

using ll = long long;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n, a, b;
  cin >> n >> a >> b;
  cout << n / (a + b) * a + min(a, n % (a + b)) << '\n';
  return 0;
}


Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
constexpr long long MOD = 1000000007;
using ll = long long;
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
int main() {
ll l,r;
cin >> l >> r;
ll ans=2020*2020;
if(r-l>=2019){cout << "0" << "\n";}
else{
    for(ll i=l;i<=r;i++){
        for(ll j=l;j<=r;j++){
            if(i==j)continue;
            chmin(ans,((i%2019)*(j%2019))%2019);
        }
    }
    cout << ans << "\n";
}

}


Measured memory_bytes: 256
n = gets.to_i
vs = gets.split.map(&:to_i)
even = {}
odd = {}
ev = []
ov = []
vs.each_with_index{|v, i|
  if i % 2 == 0
    t = even
    tv = ev
  else
    t = odd
    tv = ov
  end
  if t[v] == nil
    o = {:v => v, :c => 0}
    t[v] = o
    tv << o
  end
  t[v][:c] += 1
}
ev.sort!{|a, b|
  v = 0 if a[:c] == b[:c]
  v = -1 if a[:c] > b[:c]
  v = 1 if a[:c] < b[:c]
  v
}
ov.sort!{|a, b|
  v = 0 if a[:c] == b[:c]
  v = -1 if a[:c] > b[:c]
  v = 1 if a[:c] < b[:c]
  v
}

ei = 0
oi = 0
while(true)
  te = ev[ei]
  to = ov[oi]
  break if te[:v] != to[:v]
  break if ei == ev.length - 1 && oi == ov.length - 1
  if ei == ev.length - 1
    oi += 1
  elsif oi == ov.length - 1
    ei += 1
  else
    if ev[ei + 1][:c] > ov[oi + 1][:c]
      ei += 1
    else
      oi += 1
    end
  end
end
ans = n - ev[ei][:c] - ov[oi][:c] 
if vs[0] == vs[1] && ans == 0
  ans = n / 2
end
puts ans


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

int main()
{
    int n,count=0;
    cin>>n;

    string s;
    cin>>s;

    for(int i=0;i<s.size();i++)
    {
        if(s[i]!=s[i+1])
        {
            count++;
            //cout<<s[i]<<" ";
        }
    }
    cout<<count<<endl;
    
    return 0;

}


Measured memory_bytes: 512
#include<iostream>
#include<math.h>
#include<algorithm>
#include<stdint.h>
#include<vector>
#include<string>
#include<time.h>
#include<random>
#include<bitset>
using namespace std;


using ll = long long;

struct da {
	ll x;
	ll y;
};

int main() {

	ll n;
	cin >> n;
	vector<ll> a(n);
	vector<vector<da>> d(n);

	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		for (int j = 0; j < a[i]; ++j) {
			int x, y;
			cin >> x >> y;
			d[i].push_back(da{ x,y });
		}
	}
	ll loop = pow(2, n);
	ll max_sho = 0;
	for (ll katei = 0; katei < loop; ++katei) {
		bitset<15>kbit((unsigned long long)(katei));

		bool mujun = false;

		for (ll i = 0; i < n && !mujun; ++i) {
			if (!kbit[i]) continue;

			for (ll j = 0; j < a[i]; ++j) {
				if (kbit[d[i][j].x - 1] != (d[i][j].y == 1)) {
					mujun = true;
					break;
				}
			}
		}


		if (!mujun) {
			ll c = 0;
			for (ll i = 0; i < n; ++i) {
				if (kbit[i])++c;
			}
			max_sho = max(max_sho, c);
		}
	}

	cout << max_sho << endl;
	return 0;
}

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

bool is753(int n) {
    bool c3, c5, c7;
    c3 = c5 = c7 = false;

    do {
        int num = n % 10;
        switch (num) {
            case 3:
                c3 = true;
                break;
            case 5:
                c5 = true;
                break;
            case 7:
                c7 = true;
                break;
            default:
                return false;
        }

    } while (n /= 10);

    return (c3 && c5 && c7);
}

int main() {
    int n;
    cin >> n;

    n = min(n, 777777777);

    int ans = 0;

    for (int i = 357; i <= n; i += 2) {
        if (is753(i)) ans++;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl '\n'
#define pb push_back
#define ll long long
#define ull unsigned long long
#define vi vector<int>
using namespace std;
constexpr int MOD=1e9+7;
constexpr int mod=998244353;

int prime(int n){
    //int cnt = 0 ;
    for(int i = 2 ; i <= sqrt(n) ; ++i){
        if(n % i == 0) {
           return 1 ;   
        }
    }

    return 0  ; 
}


int fastpower(int n , int m , int tmp = 1e9+7) {
    ll ans = 1 ; 
    while(m > 0) {
        if(m % 2 != 0 ){
            ans = (ans * n) % tmp  ; 
            m--;
        }
        else {
            n = (n * n) % tmp  ; 
            m = m /2 ;
        }
    }
    return ans % tmp ; 
}

void primeFactorization(int n) {
    map<int,int> factors ; 
    while(n % 2 == 0) {
        factors[2]++;
        n = n / 2 ; 
    }

    for(int i = 3 ; n > 1 ; ++i) {
        while(n % i == 0) {
            factors[i]++;
        }
    }
}

void solve() {
    int k , n ; 
    cin >> k >> n ;
    int a[n+1] ; 
    for(int i =0 ; i <n ; ++i) {
        cin >> a[i] ;  
    }
    
    int ma=0; ll sum=0;
    for(int i=1 ; i < n ; ++i) {
        ma = max(ma, a[i]-a[i-1]) ; 
        sum += (ll)a[i]-a[i-1] ; 
    }
    ma = max(ma, k - a[n-1] + a[0]) ; 
    sum += k - a[n-1] + a[0] ;

    cout <<sum - ma ; 


    

    //cout << ans << endl; 


}


int main() {
   int t=1; 
   //cin >> t;
   while(t--){
    solve() ; 

   }



    return 0; 
}

Measured memory_bytes: 4468
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
using namespace std;


#define rep(i,s,e) for(i64 i = (s);i <= (e);i++)
typedef long long i64;

int index[200010];
int n;

set<i64> st;



int main()
{
	cin >> n;
	rep(i,1,n)
	{
		int a;
		cin >> a;
		index[a] = i;
	}

	st.insert(0);
	st.insert(n + 1);

	i64 sum = 0;
	
	rep(c,1,n)
	{
		i64 i = index[c];
		auto r_ite = st.upper_bound(i);
		auto l_ite = r_ite;
		l_ite--;
		i64 l = *l_ite;
		i64 r = *r_ite;

		sum += c * (i - l) * (r - i);
		st.insert(i);
	}

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


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

int main() {
  long long N;
  cin >> N;
  if(N<3){
    cout << 0 << endl;
    return 0;
  }
  vector<int>vec(N);
  for(int i=0; i<N; i++){
    cin >> vec[i];
  }
  int ans = 0;
  sort(vec.begin(),vec.end());
  for(int i=0; i<N-2; i++){
    for(int j=i+1; j<N-1; j++){
      for(int k=j+1; k<N; k++){
        if(vec[i]!=vec[j] && vec[i]!=vec[k] && vec[j]!=vec[k] && vec[i]+vec[j] > vec[k]){
          ans++;
        }
      }
    }
  }
  cout << ans << endl;
  return 0;
}
  


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

using namespace std;

int main() {
  int a, b;
  cin >> a >> b;

  int target = a * pow(10, floor(log10(b)) + 1) + b;
  string result = pow(floor(sqrt(target)), 2) == target ? "Yes" : "No";

  cout << result << endl;
}

Measured memory_bytes: 512
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
bool vis[107];
int G[107][107], dist[107];
queue<int> q;
int main() {
    int n;
    scanf("%d", &n);
    memset(dist, -1, sizeof(dist));
    for (int i = 1; i <= n; i++) {
    	int u, k;
    	scanf("%d%d", &u, &k);
    	for (int j = 0; j < k; j++) {
    		scanf("%d", &G[u][j]);
		}
	}
	dist[1] = 0;
	q.push(1);
	vis[1] = true;
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		for (int i = 0; G[cur][i]; i++) {
			if (dist[G[cur][i]] == -1) dist[G[cur][i]] = dist[cur] + 1;
			else dist[G[cur][i]] = min(dist[G[cur][i]], dist[cur] + 1);
			if (!vis[G[cur][i]]) {
				q.push(G[cur][i]);
				vis[G[cur][i]] = true;
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		printf("%d %d\n", i, dist[i]);
	}
    return 0;
}


Measured memory_bytes: 2784
H, W, K = map(int, input().split())
MOD = 10 ** 9 + 7
rec = []
for i in range(1 << (W - 1)):
    for j in range(W - 1):
        if i & 1 << j and i & 1 << (j + 1):
            break
    else:
        rec.append(i)

dp = [[0] * W for i in range(H + 1)]
dp[0][0] = 1
for i in range(1, H + 1):
    for k in range(W):
        for j in range(len(rec)):
            if k > 0 and (rec[j] & 1 << (k - 1)):
                dp[i][k - 1] += dp[i - 1][k]
                dp[i][k - 1] %= MOD
            elif k <= W - 2 and rec[j] & 1 << k:
                dp[i][k + 1] += dp[i - 1][k]
                dp[i][k + 1] %= MOD
            else:
                dp[i][k] += dp[i - 1][k]
                dp[i][k] %= MOD

print(dp[H][K - 1] % MOD)



Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <cmath>
#include <iomanip>
#include <bitset>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);++i)
#define rep(i,a,b) for(int i=a;i<(b);++i)
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;}
using ll = long long;
constexpr ll INF = 1LL << 60;
constexpr ll MOD = 1e9 + 7;

constexpr int MAX = 100010;
long fac[MAX], inv[MAX], finv[MAX];
void CombInit(){
  fac[0] = inv[0] = finv[0] = 1;
  fac[1] = inv[1] = finv[1] = 1;
  for(int i=2; i<MAX; ++i){
    fac[i] = fac[i-1] * i % MOD;
    inv[i] = MOD - inv[MOD%i] * (MOD/i) % MOD;
    finv[i] = finv[i-1] * inv[i] % MOD;
  }
}

long Comb(int n,int k){
  if(n < 0 || k < 0 || n < k) return 0;
  return (fac[n] * finv[n-k] % MOD) * finv[k] % MOD;
}

ll n, k, a[100010];

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> n >> k;
  for(int i = 0; i < n; ++i) cin >> a[i];

  CombInit();

  sort(a, a + n);
  ll ans = 0;
  for(int i = k-1; i < n; ++i) {
    ans = (ans + Comb(i, k - 1) * a[i] % MOD) % MOD;
  }

  sort(a, a + n, greater<ll>());
  for(int i = k-1; i < n; ++i) {
    ans = (ans - Comb(i, k - 1) * a[i] % MOD + MOD) % MOD;
  }

  cout << ans;

  return 0;
}


Measured memory_bytes: 3328
# -*- coding: utf-8 -*-
import queue
K = int(input())
q = queue.Queue()

count = 0
for i in range(1, 10):
  q.put(i)

a = 0
while count < K:
  
  a = q.get()
  fp = int(str(a)[-1])
  if fp == 0:
    q.put(a*10)
    q.put(a*10 + 1)
  elif fp == 9:
    q.put(a*10 + 8)
    q.put(a*10 + 9)
  else:
    q.put(a*10 + fp - 1)
    q.put(a*10 + fp)
    q.put(a*10 + fp + 1)
  count += 1

print(a)

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

ans = X
x = X

C = [0, x]
Xd = [-1] * (M+1)
Xd[x] = 0
i = 1

for i in range(1, N):
    x = x**2 % M

    if Xd[x] > -1:
        break
    Xd[x] = i
    ans += x
    C.append(ans)

loop_len = i - Xd[x]
if loop_len > 0:
    S = C[i] - C[Xd[x]]
    loop_num = (N - i) // loop_len
    ans += loop_num * S
    m = N - loop_num * loop_len - i
    ans += C[Xd[x]+m] - C[Xd[x]]

print(ans)

Measured memory_bytes: 13604
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); ++i)
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define fi first
#define se second
#define INF 1000000009
#define LLINF 1000000000000000009LL
using ll = long long;

const int mod = 998244353;
struct mint {
  long long x;
  mint(long long x=0) : x((x%mod+mod)%mod) {}
  mint operator-() const { return mint(-x); }
  mint& operator+=(const mint& a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint& a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint& a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint& a) const {
    return mint(*this) += a;
  }
  mint operator-(const mint& a) const {
    return mint(*this) -= a;
  }
  mint operator*(const mint& a) const {
    return mint(*this) *= a;
  }
  mint pow(long long t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
  // for prime mod
  mint inv() const { return pow(mod-2); }
  mint& operator/=(const mint& a) { return *this *= a.inv(); }
  mint operator/(const mint& a) const {
    return mint(*this) /= a;
  }
};
istream& operator>>(istream& is, const mint& a) {
  return is >> a.x;
}
ostream& operator<<(ostream& os, const mint& a) {
  return os << a.x;
}

mint dp[3009][3009];

int main(){
  int n,s;
  cin>>n>>s;
  vector<int>a(n);
  rep(i,n)cin>>a[i];

  dp[0][0]=1;
  rep(i,n){
    rep(j,s+1){
      dp[i+1][j]+=dp[i][j]*2;
      if(j+a[i]<=s){
        dp[i+1][j+a[i]]+=dp[i][j];
      }
    }
  }

  cout<<dp[n][s]<<endl;

  return(0);
}


Measured memory_bytes: 74388
#include <bits/stdc++.h>
using namespace std;
int main()
{
	string s,ss;
	cin >> s;
	cin >> ss;
	int l=s.size();
	int k=ss.size();
	int ind=-1;
	for(int i=0;i<=l-k;i++)
	{
		int f=0;
		for(int j=i;j<i+k;j++)
		{
			if(s[j]=='?')
				continue;
			if(s[j]!=ss[j-i])
			{
				f=1;
				break;
			}
		}
		//printf("%d\n",f);
		if(f==0)
		{
			ind=i;
		}
		
	}
	if(ind==-1)
	{
		printf("UNRESTORABLE\n");
		return 0;
	}
	for(int j=ind;j<ind+k;j++)
	{
		s[j]=ss[j-ind];
	}
	for(int j=0;j<l;j++)
	{
		if(s[j]=='?')
			printf("a");
		else
			printf("%c",s[j]);
	}
	printf("\n");
	return 0;
}

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

struct Dinic{
  const Int INF=1<<28;
  
  struct edge {
    Int to,cap,rev;
    edge(){}
    edge(Int to,Int cap,Int rev):to(to),cap(cap),rev(rev){}
  };

  Int n;
  vector<vector<edge> > G;
  vector<map<Int,Int> > M;
  vector<Int> level,iter;

  Dinic(){}
  Dinic(Int sz):n(sz),G(n),M(n),level(n),iter(n){}
  
  void add_edge(Int from,Int to,Int cap){
    M[from][to]=G[from].size();
    M[to][from]=G[to].size();
    G[from].push_back(edge(to,cap,G[to].size()));
    // undirected
    //G[to].push_back(edge(from,cap,G[from].size()-1));
    // directed
    G[to].push_back(edge(from,0,G[from].size()-1));
  }
  
  void bfs(Int s){
    fill(level.begin(),level.end(),-1);
    queue<Int> que;
    level[s]=0;
    que.push(s);
    while(!que.empty()){
      Int v=que.front();que.pop();
      for(Int i=0;i<(Int)G[v].size();i++){
	edge &e = G[v][i];
	if(e.cap>0&&level[e.to]<0){
	  level[e.to]=level[v]+1;
	  que.push(e.to);
	}
      }
    }
  }
  
  Int dfs(Int v,Int t,Int f){
    if(v==t) return f;
    for(Int &i=iter[v];i<(Int)G[v].size();i++){
      edge &e=G[v][i];
      if(e.cap>0&&level[v]<level[e.to]){
	Int d = dfs(e.to,t,min(f,e.cap));
	if(d>0){
	  e.cap-=d;
	  G[e.to][e.rev].cap+=d;
	  return d;
	}
      }
    }
    return 0;
  }
  
  Int flow(Int s,Int t,Int lim){
    Int fl=0;
    for(;;){
      bfs(s);
      if(level[t]<0||lim==0) return fl;
      fill(iter.begin(),iter.end(),0);
      Int f;
      while((f=dfs(s,t,lim))>0){
	fl+=f;
	lim-=f;
      }
    }
  }

  Int flow(Int s,Int t){
    return flow(s,t,INF);
  }

  //cap==1 only
  bool back_edge(Int s,Int t,Int from, Int to){
    for(Int i=0;i<(Int)G[from].size();i++) {
      edge& e=G[from][i];
      if(e.to==to) {
	if(e.cap==0&&flow(from,to,1)==0) {
	  flow(from,s,1);
	  flow(t,to,1);
	  return 1;
	}
      }
    }
    return 0;
  }
};


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

//INSERT ABOVE HERE
signed main(){
  Int n,m;
  cin>>n>>m;
  int d = 404;
  vector<Int> s(n),t(n);
  for(Int i=0;i<n;i++) cin>>s[i]>>t[i];  
  
  Int V=n+d*2;
  Int S=V++;
  Int T=V++;
  Dinic f(V);
  
  for(Int i=0;i<d;i++)
    f.add_edge(n+i,n+d+i,1);
  
  for(Int i=0;i<n;i++){
    s[i]--;
    if(i<m){
      f.add_edge(S,i,1);
      for(Int k=s[i];k<t[i];k++)
	f.add_edge(i,n+k,1);
    }else{
      for(Int k=s[i];k<t[i];k++)
	f.add_edge(n+d+k,i,1);
      f.add_edge(i,T,1);
    }
  }

  priority_queue<Int,vector<Int>, greater<Int> > pq;
  vector<queue<Int> > q(d); 
  for(Int i=0;i<n;i++) q[s[i]].emplace(t[i]);

  Int ans=0;
  for(Int i=0;i<d;i++){
    while(!q[i].empty()) pq.emplace(q[i].front()),q[i].pop();
    while(!pq.empty()&&pq.top()<=i) pq.pop();
    if(pq.empty()) continue;    
    ans++;pq.pop();
  }
  
  cout<<ans<<endl;
  cout<<f.flow(S,T)<<endl;
  return 0;
}



Measured memory_bytes: 12464