akhauriyash/Code-Regression huggingface dataset:
n = int(input())
graph = dict()
for i in range(1,n+1):
    graph[i] = []

for i in range(n-1):
    u,v,w = map(int,input().split())
    graph[u].append([v,w])
    graph[v].append([u,w])

arrival = [-1 for i in range(n+1)]
q = [1]
r = []
while not(len(q) == 0 and len(r) == 0): 
    while len(q) != 0:
        arrival[q[0]] = 0
        for i in range(len(graph[q[0]])):
            if arrival[graph[q[0]][i][0]] == -1 and graph[q[0]][i][1] % 2 == 0:
                arrival[graph[q[0]][i][0]] = 0
                q.append(graph[q[0]][i][0])
            elif arrival[graph[q[0]][i][0]] == -1 and graph[q[0]][i][1] % 2 == 1:
                r.append(graph[q[0]][i][0])
        q.pop(0)

    while len(r) != 0:
        arrival[r[0]] = 1
        for i in range(len(graph[r[0]])):
            if arrival[graph[r[0]][i][0]] == -1 and graph[r[0]][i][1] % 2 == 0:
                arrival[graph[r[0]][i][0]] = 1
                r.append(graph[r[0]][i][0])
            elif arrival[graph[r[0]][i][0]] == -1 and graph[r[0]][i][1] % 2 == 1:
                q.append(graph[r[0]][i][0])
        r.pop(0)


for i in range(1,n+1):
    if arrival[i] != 0:
        print("1")
    else:
        print("0")

Measured memory_bytes: 53520
var
n,i,j,cnt,t:Longint;
a,b:array[1..10000]of Longint;
begin
read(n);
t:=n+1-n mod 2;
for i:=1 to n do begin
for j:=i+1 to n do begin
if i+j<>t then begin
inc(cnt);
a[cnt]:=i;
b[cnt]:=j;
end;
end;
end;
writeln(cnt);
for i:=1 to cnt do writeln(a[i],' ',b[i]);
end.

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

int main(){
    map<char, ll> c2i = {
        {'S', 0}, {'H', 1}, {'C', 2}, {'D', 3}
    };
    string i2c = "SHCD";

    ll n;
    cin >> n;
    vector<vector<bool>> ok(4, vector<bool>(13, false));
    REP(i, n){
        char x;
        ll num;
        cin >> x >> num;
        num--;
        ok.at(c2i.at(x)).at(num) = true;
    }

    REP(i, 4){
        REP(j, 13){
            if(ok.at(i).at(j)){ continue; }
            cout << i2c.at(i) << ' ' << j + 1 << endl;
        }
    }
}



Measured memory_bytes: 3208
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
  string s;
  ll z=0,o=0;
  cin>>s;
  for(ll i=0;i<s.size();i++){if(s[i]=='0')z++;else o++;}
  cout<<min(o,z)*2<<endl;
}

Measured memory_bytes: 512
import sys
input = sys.stdin.readline
from collections import deque

N,M=[int(val) for val in input().split()]
a=deque()
b=deque()

for i in range(M):
  x,y = (int(val) for val in input().split())
  a.append(x)
  b.append(y)

cnt=0
for j in range(M):
    
    val_a=a.popleft()
    val_b=b.popleft()

    stack=deque([1])
    visited=deque()

    while len(stack) > 0:
        val=stack.pop()
        if visited.count(val)==0:
            visited.append(val)
            for i in range(len(a)):
                if a[i]==val:
                    if b[i] != visited:
                        stack.append(b[i])
            for i in range(len(b)):
                if b[i]==val:
                    if a[i] != visited:
                        stack.append(a[i]) 
                        
    if len(visited) < N:
        cnt+=1
    
    a.append(val_a)
    b.append(val_b)

print(cnt)

Measured memory_bytes: 3316
#include<bits/stdc++.h>
using namespace std;
int main(){
	int x , y , e ,m ;
	cin>>e>>x>>y;
	if(y>(x+e))
	m=y-(x+e);
	else if(x>y+e)
	m=x-(y+e);
	else
	m=0;
	cout<<m;
	return 0;
}

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

int n;
vector<pair<int,int>> edge[100004];
int color[100004];
void dfs(int here){
	for(auto next : edge[here]){
		int there = next.first;
		int weight = next.second;
		if(color[there] != -1)	continue;
		if(weight % 2 == 0){
			color[there] = color[here];
		}
		else{
			color[there] = (color[here]^1);
		}
		dfs(there);
	}
}
int main() {
	cin>>n;
	int w, v, u;
	for(int i = 0;i<n-1;i++){
		cin>>u>>v>>w;
		edge[u].push_back({v, w});
		edge[v].push_back({u, w});
	}
	memset(color, -1,sizeof(color));
	color[1] = 0;
	dfs(1);
	for(int i = 1;i<=n;i++)	cout<<color[i]<<'\n';
	return 0;
}

Measured memory_bytes: 7552
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <chrono>
#include <random>
#include <functional>

using namespace std;

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
typedef long long ll;

using ipair = pair<int, int>;

ll INF = 1e16+7;

bool operator>(const ipair a,const ipair b){return a.first > b.first;}


int main(){
  ll K;
  cin >> K;
  ll N = 50;

  cout << N << endl;

  ll base = N-1;
  ll q = K/N;
  ll r = K%N;

  rep(i, N){
    ll tmp_ans = (N-1) + q - r;
    if(i<r) tmp_ans += N;
    if(i!=0) cout << " ";
    cout << tmp_ans ;
  }
  cout << endl;

  return 0;
}


Measured memory_bytes: 3604
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <stdio.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <tuple>
#include <map>
#include <sstream>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define FOR(i,a,b) for(int i=a; i<(int)(b); i++)
#define ALL(x) (x).begin(),(x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SORT(c) sort(ALL(x))
#define CLR(a) memset((a), 0 ,sizeof(a))
#define PB push_back
#define MP make_pair
#define SP << " " <<
const int INF = 1001001001;
const ll LINF = 100100100100100100;
const double EPS = 1e-10;
const double PI  = acos(-1.0);
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

__attribute__((constructor))
void initial(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}


signed main(){
	int n; cin>>n;
  VI a(n+1);
  reps(i,n) cin>>a[i];
  VI b(n+1);
  REPS(i,n){
    int sum = 0;
    for(int j=2*i; j<=n; j+=i) sum^=b[j];
    b[i] = sum^a[i];
  }
  VI ans;
  reps(i,n) if(b[i]) ans.PB(i);
  cout << ans.size() << endl;
  rep(i,ans.size()) cout << ans[i] << ' ';
  cout << endl;

	return 0;
}


Measured memory_bytes: 3192
x, y = map(int, input().split())
ans = 0
if x == 3:
  ans += 100000
elif x == 2:
  ans += 200000
elif x ==1:
  ans += 300000
if y == 3:
  ans += 100000
elif y == 2:
  ans += 200000
elif y ==1:
  ans += 300000
if x == y == 1:
  ans += 400000
print(ans)

Measured memory_bytes: 3060
def main():
    n,m=map(int,input().split())
    A=[list(input()) for _ in range(n)]
    B=[list(input()) for _ in range(m)]
    for i in range(n-m+1):
        for j in range(n-m+1):
            tmp=[]
            for k in range(m):
                tmp.append(A[i+k][j:j+m])
            if B==tmp:
                print('Yes')
                return
    print('No')
main()

Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <functional>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <deque>
#include <ctime>
  
using namespace std;
  
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define pb push_back
#define mp make_pair
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()
#define fi first
#define se second
#define println(X) cout<<X<<endl;
#define DBG(X) cout<<#X<<" : "<<X<<endl;
  
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int INF = 1e9;
const ll LINF = 1e18;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;
const double PI = acos(-1);

struct Vector2{
    double x, y;
    Vector2(){};
    Vector2(double x, double y) : x(x), y(y){};

    double cross(const Vector2& p){
        return x*p.y - y*p.x;
    }

    const Vector2 medPoint(const Vector2& v){
        return {(x + v.x) / 2.0, (y + v.y) / 2.0};
    }

    const bool operator == (const Vector2& v){
        return abs(x - v.x) < EPS && abs(y - v.y) < EPS;
    }
    const bool operator != (const Vector2& v){
        return !(*this==(v));
    }
};

int main(){
	int n;
    cin>>n;
    vector<Vector2> v;
    rep(i, n){
        double x, y;
        cin>>x>>y;
        v.pb({x, y});
    }
    bool f = n & 1;
    Vector2 a = v[0].medPoint(v[n/2]);
    for(int i = 1; i < n /2; i++){
        f |= a != v[i].medPoint(v[i + n/2]);
    }
    if(f) cout<<"NA"<<endl;
    else printf("%.15lf %.15lf\n", a.x, a.y);
}

Measured memory_bytes: 3292
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <iterator>
#include <list>
#include <map>
#include <queue>
#include <bitset>
#include <fstream>
#include <cmath>
#include <ctime>
using namespace std;
typedef long long ll;

int C, R;
int rec(int, vector<vector<bool> >);
int count(vector<vector<bool> >);
vector<vector<bool> > reverserow(int, vector<vector<bool> >);


int main()
{
	while(cin>>C>>R && (C || R)){

		vector<vector<bool> > board(C, vector<bool>(R));

		for(int i = 0; i < C; i++){
			for(int j = 0; j < R; j++){
				int buf;
				cin>>buf;
				if(buf) board[i][j] = true;
				else	board[i][j] = false;
			}
		}

		cout<<rec(0, board)<<endl;

	}
}

int rec(int pos, vector<vector<bool> > board)
{
	if(pos == C) return count(board);
	return max(rec(pos + 1, board), rec(pos + 1, reverserow(pos, board)));
}

vector<vector<bool> > reverserow(int pos, vector<vector<bool> > board)
{
	for(int i = 0; i < board[pos].size(); i++)
		board[pos][i] = !board[pos][i];
	return board;
}

int count(vector<vector<bool> > board)
{
	int res = 0;

	for(int i = 0; i < board[0].size(); i++){
		int surface = 0, back = 0;
		for(int j = 0; j < board.size(); j++){
			if(board[j][i]) surface++;
			else			back++;
		}
		res += max(surface, back);
	}

	return res;
}

Measured memory_bytes: 1308
# https://atcoder.jp/contests/abc108/tasks/arc102_a
# ちょっと難しい
# 情報を整理すると以下の条件が整理される
# aに関する必要条件 2aはKの倍数。
# aが決定したとき(Aとする)のbとc必要十分条件、b=xK-Aを満たす数字 where xは整数、bは[1,N]
# 以上の条件を満たすものを数えればいいのか？


N, K = map(int, input().split())


def f(A):
    # Aが与えられたとき、必要十分条件を満たすbはいくつあるのか
    # 1+A<=xK<=N+A を満たす xの個数を知りたい
    # N+A以下の整数でKの倍数はいくつある？ - AまでにKの倍数はいくつある？
    nb = (N + A) // K - A // K
    return nb * nb


ans = 0
for i in range(1, N + 1):
    if (2 * i) % K == 0:
        ans += f(i)
print(ans)


Measured memory_bytes: 2940
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 510
int a[N][N];
int main()
{
    int i,j,k,n,m,q,l,r;
    scanf("%d%d%d",&n,&m,&q);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&l,&r);
        a[0][r]++;
        a[l+1][r]--;
    }
    for(i=0;i<=n;i++)
    for(j=0;j<=n;j++)
    {
        a[i+1][j]+=a[i][j];
        a[i][j]+=a[i][j-1];
    }
    for(i=0;i<q;i++)
    {
        scanf("%d%d",&l,&r);
        printf("%d\n",a[l][r]);
    }
    return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
long long ans = 0;
string S;
int s;

void dfs(int i, int b, long long sum){
	if (i == s-1){
		sum += stoll(S.substr(b+1,i-b));
		ans += sum;
	}
	else {
		dfs(i+1, b, sum);
		sum += stoll(S.substr(b+1, i - b));
		dfs(i+1,i, sum);
	}
}


int main() {
	cin >> S;
	s = S.size();
	dfs(0, -1, 0);
	cout << ans << endl;
	return 0;
}

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

using namespace std;
typedef long long ll;
#define sz(x) (ll)((x).size())
#define pb push_back
#define mp make_pair 
#define bg begin()
#define ed end()
#define all(x) (x).bg,(x).ed
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep1(i,n) for(ll i=1;i<=n;i++)

int main(){
	ll N; cin>>N;
	string mem;
	set<string> se;
	bool ans=true;
	rep(i,N){
		string tmp; cin>>tmp;
		if(i!=0){
			if(tmp[0]!=mem[sz(mem)-1]){
				ans=false;
			}
		}
		mem=tmp;
		se.insert(tmp);
	}
	if(!ans || sz(se)!=N) cout<<"No";
	else cout<<"Yes";
}

Measured memory_bytes: 256
"""

配列Aに対し、区間l,rを決めて、Al~Arのxor取ったやつと、足したやつが一致すればいい

a xor b = a + b が成立するとき、aとbを２進数で見たときに、i番目のビットが両方1になっている、ということがない。


"""


N = int(input())
A = list(map(int, input().split()))

bits= [-1] * 21
r = 0

ans = 0
for l in range(N):
    while r <= N-1:
        flag = True
        for j in range(21):
            if bits[j] != -1 and A[r] & (1 << j):
                flag = False
                break

        if flag:
            for j in range(21):
                if A[r] & (1 << j):
                    bits[j] = r
            r += 1

        else:
            break


    ans += r - l

    if l == r:
        r += 1

    for j in range(21):
        if A[l] & (1 << j):
            bits[j] = -1

print(ans)

Measured memory_bytes: 76748
H, W, N, *AS = $stdin.read.split.map(&:to_i)
board = Array.new(H){ Array.new(W) }
x = y = 0
d = +1
AS.each.with_index(1) do |a, i|
  a.times do
    board[y][x] = i
    x += d
    if x > W-1
      x -= 1
      d = -1
      y += 1
    elsif x < 0
      x += 1
      d = +1
      y += 1
    end
  end
end

board.each do |row|
  puts row.join(' ')
end


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

d=[0]*k
a=set()
for i in range(k):
    d[i]=int(input())
    if d[i]>1:
        ai=set(map(int,input().split()))
        a=a|ai
    else:
        a.add(int(input()))
    
print(n-len(a))


Measured memory_bytes: 9216
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin>>n;
  int a[n],c[8]={},pro=0,count=0;
  for(int i=0;i<n;++i){
    cin>>a[i];
  }
  for(int i=0;i<n;++i){
    if(a[i]>=3200){
      pro++;
    }
    else{
      c[a[i]/400]++;
    }
  }
  for(int i=0;i<8;++i){
    if(c[i]>0){
      count++;
    }
  }
  cout<<max(1,count)<<" "<<count+pro;
  return 0;
}


Measured memory_bytes: 256
package main

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

var sc = bufio.NewScanner(os.Stdin)

func Scan() string {
	sc.Scan()
	return sc.Text()
}

func iScan() int {
	n, _ := strconv.Atoi(Scan())
	return n
}

func fScan() float64 {
	n, _ := strconv.ParseFloat(Scan(), 64)
	return n
}
func stringToInt(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}
func SScan(n int) []string {
	a := make([]string, n)
	for i := 0; i < n; i++ {
		a[i] = Scan()
	}
	return a
}
func iSScan(n int) []int {
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = iScan()
	}
	return a
}
func abs(x int) int {
	if x < 0 {
		x = -x
	}
	return x
}
func larger(a, b int) int {
	if a < b {
		return b
	} else {
		return a
	}
}
func smaller(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}
func max(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x < a[i] {
			x = a[i]
		}
	}
	return x
}
func min(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x > a[i] {
			x = a[i]
		}
	}
	return x
}
func sum(a []int) int {
	x := 0
	for _, v := range a {
		x += v
	}
	return x
}

var mod int = 1000000007

func main() {
	buf := make([]byte, 0)
	sc.Buffer(buf, mod)
	sc.Split(bufio.ScanWords)
	x := stringToInt(Scan() + Scan())
	ans := "No"
	for i := 1; i <= 1000; i++ {
		if i*i == x {
			ans = "Yes"
			break
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 1772
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main(){
	int n,m;
	int in[5000] = {};
	vector<int> rnk;
	vector<int> G[5000];
	cin >> n >> m;
	for(int i = 0;i < m;i++){
		int a,b;
		cin >> a >> b;
		G[a - 1].push_back(b - 1);
		in[b - 1]++;
	}
	queue<int> que;
	for(int i = 0;i < n;i++){
		if(in[i] == 0) que.push(i);
	}
	while(!que.empty()){
		int v = que.front();que.pop();
		rnk.push_back(v);
		for(int i = 0;i < G[v].size();i++){
			in[G[v][i]]--;
			if(in[G[v][i]] == 0){
				que.push(G[v][i]);
			}
		}
	}
	int flag = 0;
	for(int i = 0;i < n - 1;i++){
		bool f = false;
		for(int j = 0;j < G[rnk[i]].size();j++){
			if(G[rnk[i]][j] == rnk[i + 1]) f = true;
		}
		if(!f) flag = 1;
	}
	for(int i = 0;i < n;i++) cout << rnk[i] + 1 << endl;
	cout << flag << endl;
	return 0;
}

Measured memory_bytes: 3548
"""
普通に数え上げDPで行けそう
dp[i][j][k] ->　カードをi枚使う/j種類目のカードまで見る/カードの数字の合計がkになる
j種類目のカードを使う場合：
dp[i][j][k] += dp[i-1][j-1][k-x]
j種類目のカードを使わない場合：
dp[i][j][k] += dp[i][j-1][k]

という風に計算していって、最終的に各iごとにk/i=Aとなるようなkを見出して、dp[i][-1][k]をanswerとして加算する。
"""
N,A = map(int,input().split())
X = list(map(int,input().split()))
sumX = sum(X)
dp = [[[0]*(sumX+1) for _ in range(N+1)]for _ in range(N+1)]
for j in range(N+1):
    dp[0][j][0] = 1
for i in range(1,N+1):
    for j in range(1,N+1):
        x = X[j-1]
        for k in range(1,sumX+1):
            dp[i][j][k] += dp[i][j-1][k]
            if k-x >= 0:
                dp[i][j][k] += dp[i-1][j-1][k-x]
ans = 0
for i in range(1,N+1):
    target = A*i
    if target <= sumX:
        ans += dp[i][-1][target]

print(ans)



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

int main(){
  int h, w;
  string s[50],res[50];
  
  cin >> h >> w;
  for(int i = 0; i < h; i++){
    cin >> s[i];
  }
  for(int i = 0; i < h; i++){
    for(int j = 0; j < w; j++){
      if(s[i].at(j) == '#'){
        s[i].at(j) = '#';
        continue;
      }else{
        s[i].at(j) = '0';
      }
      for(int y = i - 1; y <= i + 1; y++){
        if(y < 0 || y >= h){
          continue;
        }
        for(int x = j - 1; x <= j + 1; x++){
          if(x < 0 || x >= w){
            continue;
          }
          if(s[y].at(x) == '#'){
            s[i].at(j)++;
          }
        }
      }
    }
  }
  for(int i = 0; i < h; i++){
    cout << s[i] << endl;
  }
  return 0;
}
    
  
    

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

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds; 
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> Tree;

#define dbg(x) cout<<#x<<"="<<x<<'\n'
#define ll long long
#define pr pair<int,int>
#define pb push_back
#define ff first
#define ss second
#define vi vector<int>
#define For(i,n) for(int i=0;i<(n);++i)
#define Forr(i,n) for(int i=n-1;i>=0;i--)
#pragma GCC optimization("Ofast")
#pragma GCC optimization("unroll-loops")
#define fin ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define MOD 1000000007
#define all(x) (x).begin(),(x).end()
#define sz(a) (int)a.size()
#define Fill(a,b) memset(a,b,sizeof(a));
#define fileio freopen("http://in.in", "r", stdin),freopen("out.out", "w", stdout);
#define sd(x) scanf("%d",&x)
#define sld(x) scanf("%lld",&x)
const int INF=1e9;
#define vvi vector<vi>



void solve(){
    int n,x,t;
    cin>>n>>x>>t;
    int ans;
    if(n%x)ans=n/x+1;
    else ans=n/x;
    ans*=t;
    cout<<ans<<endl;
}



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

Measured memory_bytes: 3600
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace _0007
{
    public class Program

    {
        public static void Main(string[] args)
        {
            int n = ReadInt();

            int debt = 100000;
            for (int i = 0 ; i < n ; i++)
            {
                debt = (int)(Math.Ceiling(debt * 1.05 / 1000) * 1000);
            }
            Console.WriteLine(debt);
        }

        static string ReadSt() { return Console.ReadLine(); }
        static int ReadInt() { return int.Parse(Console.ReadLine()); }
        static long ReadLong() { return long.Parse(Console.ReadLine()); }
        static double ReadDouble() { return double.Parse(Console.ReadLine()); }
        static string[] ReadStAr(char sep = ' ') { return Console.ReadLine().Split(sep); }
        static int[] ReadIntAr(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Split(sep), e => int.Parse(e)); }
        static long[] ReadLongAr(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Split(sep), e => long.Parse(e)); }
        static double[] ReadDoubleAr(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Split(sep), e => double.Parse(e)); }
        static string WriteAr(int[] array, string sep = " ") { return String.Join(sep, array.Select(x => x.ToString()).ToArray()); }
        static string WriteAr(double[] array, string sep = " ") { return String.Join(sep, array.Select(x => x.ToString()).ToArray()); }
        static string WriteAr(long[] array, string sep = " ") { return String.Join(sep, array.Select(x => x.ToString()).ToArray()); }

    }

}



Measured memory_bytes: 15880
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = pow(10, 9) + 7;
//const ll MOD = 998244353;
//const ll MOD = ;
ll mod(ll A, ll M) {return (A % M + M) % M;}
const ll INF = 1LL << 60;
template<class T> bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
ll divceil(ll A, ll B) {return (A + (B - 1)) / B;}
ll myctoi(char C) {return C - '0';}
char myitoc(ll N) {return '0' + N;}
#define FINALANS(A) {cout << (A) << '\n'; exit(0);}

int main()
{
  ll N, K;
  cin >> N >> K;
  string S;
  cin >> S;

  ll spl = 0;
  for (ll i = 1; i < N; i++)
  {
    if (S.at(i - 1) != S.at(i))
      spl++;
  }
  ll ans = N - max(0LL, spl - K * 2) - 1;
  cout << ans << endl;
}

Measured memory_bytes: 512
def norm(c):
    a = abs(c)
    return a*a
def dot_product(a,b):
    return (a.conjugate()*b).real
def cross_product(a,b):
    return (a.conjugate()*b).imag
def projection(p,b):
    return b*dot_product(p,b)/norm(b)

P = []
try:
    while True:
        x,y = map(float,input().split(','))
        P.append(complex(x,y))
except EOFError:
    pass

N = len(P)
total = 0.0
for i in range(1,N-1):
    a,b,c = P[0],P[i],P[i+1]
    S = abs(cross_product(b-a,c-a))/2
    total += S

print("%.6f" % (total))


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

using namespace std;
#define REP(i, n) for (int i=0; i<(n); ++i)
#define RREP(i, n) for (int i=(int)(n)-1; i>=0; --i)
#define FOR(i, a, n) for (int i=(a); i<(n); ++i)
#define RFOR(i, a, n) for (int i=(int)(n)-1; i>=(a); --i)

#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()

#define DUMP(x) cerr<<#x<<" = "<<(x)<<endl
#define DEBUG(x) cerr<<#x<<" = "<<(x)<<" (L"<<__LINE__<<")"<<endl;

template<class T>
ostream &operator<<(ostream &os, const vector <T> &v) {
    os << "[";
    REP(i, SZ(v)) {
        if (i) os << ", ";
        os << v[i];
    }
    return os << "]";
}

template<class T, class U>
ostream &operator<<(ostream &os, const pair <T, U> &p) {
    return os << "(" << p.first << " " << p.second << ")";
}

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

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

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using P = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vi>;
using vvll = vector<vll>;

const ll MOD = 1e9 + 7;
const int INF = INT_MAX / 2;
const ll LINF = LLONG_MAX / 2;
const ld eps = 1e-9;


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    // ifstream in("in.txt");
    // cin.rdbuf(in.rdbuf());

    int n; cin >> n;
    ll k; cin >> k;
    vi a(n);
    REP(i, n) {
        cin >> a[i];
        --a[i];
    }

    vi p;
    vi used(n, -1);
    int cur, i;
    for (i = 0, cur = 0; used[cur] == -1; cur = a[cur], ++i) {
        used[cur] = i;
        p.push_back(cur);
    }

    int ans;
    if (k < used[cur]) {
        ans = p[k] + 1;
    }
    else {
        ans = p[(k - used[cur]) % (i - used[cur]) + used[cur]] + 1;
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 5788
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
using namespace std;
typedef long long int ll;
typedef vector<int> vi;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define Sort(a) sort(a.begin(), a.end())
const int INF = 1<<30;
const ll MOD = 1000000007;

int main(void) {

    int n; cin >> n;
    ll ans = 0;
    vi d(n+1);
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j += i) d[j]++;
    }
    for (int i = 1; i <= n; i++) ans += ll(i)*d[i];
    cout << ans << endl;

    return 0;
}

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


int main()
{
    int n ; cin >> n ;
    int h[n] ;
    for(int i = 0; i < n; i++)
         cin >> h[i] ;
    int dp[n] ; memset(dp, 0, sizeof(dp));
    for(int i = 0; i < n; i++)
    {
        if(i > 1)
            dp[i] = min(dp[i-1] + abs(h[i] - h[i-1]), dp[i-2] + abs(h[i] - h[i-2]));
        else if(i > 0)
            dp[i] = dp[i-1] + abs(h[i] - h[i-1]);
    }
    cout << dp[n-1] ;
}


Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <sstream>   
#include<limits.h>
#include<float.h>
#include<list>
#include <array>
#include <complex>
#include<stdio.h>
#include<string.h>
#include <bitset>

using namespace std;
#define int  long long

#define I32_MAX 2147483647
#define I64_MAX 9223372036854775807LL
#define I64_MAX2 1223372036854775807LL
#define INF I64_MAX2
#define MOD 1000000007
#define MEM_SIZE 10000
#define DEBUG_OUT true
#define ALL(x) (x).begin(),(x).end()


template<typename T> void DEBUG(T e){if(DEBUG_OUT == false)return; std::cout << e <<" ";}
template<typename T> void DEBUG(const std::vector<T>& v){if(DEBUG_OUT == false)return;for(const auto& e : v){std::cout<< e << " "; } std::cout << std::endl;}
template<typename T> void DEBUG(const std::vector<std::vector<T> >& vv){if(DEBUG_OUT == false)return;for(const auto& v : vv){ DEBUG(v); } }
template<class T,class... Ts> void DEBUG(T d, Ts... e){if(DEBUG_OUT == false)return;DEBUG(d);DEBUG(e...);}
template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; exit(0);}}
template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }


void solve(void)
{
  int N; cin>>N;
  map<int,int> mp;
  int cnt = 0;
  for (int i = 0; i < N; i++)
  {
    int X;cin>>X;
    X /= 400;
    if(X <= 7)
    mp[X]++;
    else cnt++;

  }
  int check = 0;
  if(mp.size() == 0)check = 1;
  cout<<mp.size() + check<<" "<<mp.size()+cnt<<endl;
  
  return;
}
int32_t main(int32_t argc, const char *argv[])
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);

std::cout << std::fixed;
std::cout << std::setprecision(9);
solve();

return 0;
}


Measured memory_bytes: 256
num = int(input())

slist = list()
hlist = list()
clist = list()
dlist = list()

for i in range(num):

    mark,value = input().split()
    if (mark == "S"):
        slist.append(value)

    elif (mark == "H"):
        hlist.append(value)

    elif (mark == "C"):
        clist.append(value)

    elif (mark == "D"):
        dlist.append(value)





nslist = list()
nhlist = list()
nclist = list()
ndlist = list()

for i in range(1,14):
    if (str(i) not in slist):
        nslist.append(str(i))

for i in range(1,14):
    if (str(i) not in hlist):
        nhlist.append(str(i))

for i in range(1,14):
    if (str(i) not in clist):
        nclist.append(str(i))

for i in range(1,14):
    if (str(i) not in dlist):
        ndlist.append(str(i))

for j in nslist:
    print("S "+str(j))

for j in nhlist:
    print("H "+str(j))

for j in nclist:
    print("C "+str(j))

for j in ndlist:
    print("D "+str(j))



Measured memory_bytes: 5604
S=input()
acc,ans=0,0
for c in S:
    if c=='g':
        if acc > 0:
            ans += 1
            acc -=1
        else:
            acc += 1
    else:
        if acc > 0:
            acc -= 1
        else:
            ans -= 1
            acc +=1
print(ans)


Measured memory_bytes: 39664
use std::io;


fn main() {
    let i = read::<String>();

    let ans = match (&*i[0], &*i[1]) {
        ("H", "H") => true,
        ("D", "D") => true,
        ("H", "D") => false,
        ("D", "H") => false,
        _ => unreachable!(),
    };

    if ans { println!("H"); }
    else { println!("D"); }
}


#[allow(dead_code)]
fn read<T>() -> Vec<T>
where T:
    std::str::FromStr,
    T::Err: std::fmt::Debug {

    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.split_whitespace()
        .map(|s| s.trim().parse().unwrap())
        .collect()
}

#[allow(dead_code)]
fn read_one<T>() -> T
where T:
    std::str::FromStr,
    T::Err: std::fmt::Debug {

    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.trim().parse().unwrap()
}

Measured memory_bytes: 4352
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.IO;
using static System.Math;
namespace AtCoder
{
    class Program
    {
        static StreamReader sr;

        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }
        static long Mod = (long)1e9 + 7;
        static void Main(string[] args)
        {
            //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
            var NDA = Sarray();
            var N = NDA[0];
            var D = NDA[1];
            var A = NDA[2];
            var XH = new List<Tuple<long, long>>();
            for (var i = 0; i < N; ++i)
            {
                var xh = Sarray();
                XH.Add(Tuple.Create(xh[0], xh[1]));
            }
            XH.Sort((l, r) => (int)(l.Item1 - r.Item1));
            var bombPos = new List<long>();
            var bombNum = new List<long>();
            var damege = 0L;
            int left = 0;
            for (var i = 0; i < N; ++i)
            {
                while (left < bombPos.Count && bombPos[left] + D < XH[i].Item1) damege -= bombNum[left++] * A;
                var num = (XH[i].Item2 - damege + A - 1) / A;
                if (num <= 0) continue;
                bombNum.Add(num);
                damege += num * A;
                bombPos.Add(XH[i].Item1 + D);
            }
            WriteLine(bombNum.Sum());
            //Out.Flush();
        }
    }
}

Measured memory_bytes: 34428
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

pub fn ceil_div(a: usize, b: usize) -> usize {
    (a + b - 1) / b
}

fn main() {
    input! {
        n: usize,
        d: usize
    }
    let x = d * 2 + 1;
    println!("{}", ceil_div(n, x));
}


Measured memory_bytes: 4352
#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(int i=0;i<N;++i)
typedef long long int LL;

int A, B, C, D;

int main()
{
	in>>A>>B>>C>>D;
	int l=A+B;
	int r=C+D;
	if(l<r)
	{	out<<"Right"<<std::endl;}
	else if(l>r)
	{	out<<"Left"<<std::endl;}
	else
	{	out<<"Balanced"<<std::endl;}
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>

int main(void) {
	double r,x,y;
	double PI=3.141592653589;
	scanf("%lf",&r);
	x=2*r*PI;
	y=r*r*PI;
	printf("%f %f\n",y,x);
	return 0;
}

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

#include <boost/range/adaptors.hpp>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;
using namespace boost::adaptors;

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

    auto x = min(b - 1, n);
    cout << a * x / b - a * (x / b) << endl;
}

Measured memory_bytes: 3636
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <climits>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>

#define REP(i,n) for(long long i=0;i<n;++i)
#define REPR(i,n) for(long long i=n;i>=0;--i)
#define REPI(itr,v) for(auto itr=v.begin();itr!=v.end();++itr)
#define REPIR(itr,v) for(auto itr=v.rbegin();itr!=v.rend();++itr)
#define FOR(i,a,b) for(long long i=a;i<b;++i)
#define SORT(v,n) sort(v, v+n)
#define SORTV(v) sort(v.begin(), v.end())
#define ALL(v) v.begin(),v.end()
#define llong long long
#define INF 999999999
#define MOD 1000000007
#define pb push_back
#define pf push_front
#define MP make_pair
#define SV(v) {for(long long sitr=0;sitr<v.size();++sitr){cin>>v[sitr];}}

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

using namespace std;

typedef pair<int,int> pii;

bool divisor(llong n){
  llong res = 1;
  for(llong i = 1; i * i <= n; ++i){
    if(n % i == 0){
      res *= i;
      if(res >= 2 * n) return true;
      //cout << res << endl;
      if(i * i != n && i != 1){
        res *= n / i;
      }
    }
  }
  if(res >= 2 * n) return true;
  return false;
}

int main(){

  int q;
  cin >> q;

  llong a[100010] = {};
  for(llong i = 1; i<100001; ++i){
    if(divisor(i)) a[i]++;
  }
  REP(i,100001){
    a[i+1] += a[i];
  }

  REP(i,q){
    int tmp;
    cin >> tmp;
    cout << a[tmp] << endl;
  }
  return 0;
}




Measured memory_bytes: 3884
#include <iostream>
#include <algorithm>
#include <cmath>
#include <limits>
#include <vector>
#include <cstdio>
#include <bits/stdc++.h>
#include <set>
#include <map>
#include <stdio.h>
#include <stack>
#include <queue>
#include <deque>
#include <numeric>
#include <bits/stdc++.h>
#include <utility>
#include <iomanip>

#define ALL(obj) (obj).begin(), (obj).end()
#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define RFOR(i,a,b) for(int i = (a); (b) <= i; i--)
#define REP(i,n) for(int i = 0; i < (n); i++)
#define RREP(i,n) for(int i = n; n <= i; i--)
#define ABS(a) ((a < 0) ? ((-1)*(a)) : (a))
#define elif else if
#define MOD 1000000007
#define INF (1<<29)

using namespace std;

#define ld long double
#define ll long long

map <int ,int> mpa,mpb;
typedef pair<ll, ll> P;
priority_queue<P, vector<P>, greater<P>> pque;

bool IsPrime[100100];
bool nearPrime[100010];

void Sieve_Eratosthenes(int max){
    /*if(max+1 > IsPrime.size()){     // resizeで要素数が減らないように
        IsPrime.resize(max+1,true); // IsPrimeに必要な要素数を確保
    }*/
    for(int i=0;i<max;i++){
      IsPrime[i]=true;
    }
    IsPrime[0] = false; // 0は素数ではない
    IsPrime[1] = false; // 1は素数ではない

    for(size_t i=2; i*i<=max; ++i) // 0からsqrt(max)まで調べる
        if(IsPrime[i]) // iが素数ならば
            for(size_t j=2; i*j<=max; ++j) // (max以下の)iの倍数は
                IsPrime[i*j] = false;      // 素数ではない
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int Q;
  int l,r;
  cin >> Q;
  Sieve_Eratosthenes(100010);
  for(int i=3;i<100010;i+=2){
    if(IsPrime[i]==true && IsPrime[(i+1)/2]){
      nearPrime[i]=true;
      //cout << i << endl;
    }
  }
  int a[100010]={0};
  for(int i=1;i<100010;i++){
    if(nearPrime[i]){
      a[i]=a[i-1]+1;
    }else{
      a[i]=a[i-1];
    }
  }
  for(int i=0;i<Q;i++){
    int ans=0;
    cin >> l >> r;
    ans=a[r]-a[l-1];
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
// #include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <math.h>

using namespace std;
typedef long long ll;

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

template<class T> inline void chmin(T& a, T b) {if (a > b) a = b;}
template<class T> inline void chmax(T& a, T b) {if (a < b) a = b;}
const ll inf = 1LL<<60;

int main(){
  int n,k;cin>>n>>k;
  vector<int> w(n+10);
  vector<int> v(n+10);
  ll dp[n+10][k+10];
  rep(i,n){
    cin>>w[i]>>v[i];
  }
  rep(i,k+1){
    dp[0][i]=0;
  }
  
  for(int i=1;i<=n;i++){
    int now_w=w[i-1];
    int now_v=v[i-1];

    for(int j=0;j<=k;j++){
      if(now_w<=j){
        dp[i][j]=max(dp[i-1][j-now_w]+now_v,dp[i-1][j]);
      }else{
        dp[i][j]=dp[i-1][j];
      }
    }
  }
  cout<<dp[n][k]<<endl;
}


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

#define sz(x) (int)x.size()
#define ld long double
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second

using namespace std;

int n, k;
vector<int> cnt;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> k;
    cnt.assign(n, 0);
    for(int i = 0;  i < k; ++i){
        int d; cin >> d;
        for(int j = 0; j < d; ++j){
            int x; cin >> x; x--;
            cnt[x]++;
        }
    }
    int res = 0;
    for(int i = 0;  i < n; ++i){
        if(!cnt[i]) res++;
    }
    cout << res;
    return 0;
}

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

int main(){
    int N, K;
    cin >> N >> K;
    int balls[N];
    for(int i = 0; i < N; i++){
        cin >> balls[i];
    }
    sort(balls, balls + N);
    vector<int> serials;
    int serial = 1;
    for(int i = 1; i < N; i++){
        if(balls[i] == balls[i - 1]){
            serial++;
        }else{
            serials.push_back(serial);
            serial = 1;
        }
    }
    serials.push_back(serial);
    sort(serials.begin(), serials.end());
    int ans = 0;
    for(int i = 0; i < serials.size() - min(K, int(serials.size())); i++){
        ans += serials[i];
    }
    cout << ans << endl;
}


Measured memory_bytes: 2168
n = int(input())
a_list = list(map(int,input().split()))

count_dict = {}
result_dict = {}

for a in a_list:
    if a not in count_dict:
        count_dict[a] = 1
    else:
        count_dict[a] += 1

# default count
count = 0
for k,v in count_dict.items():
    if v >= 2:
        count += v*(v-1)//2

for a in a_list:
    num = count_dict[a]
    if num >= 3:
        print(count-num*(num-1)//2+(num-1)*(num-2)//2)
    elif num == 2:
        print(count-1)
    else:
        print(count)
    

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

int main(){
  int n;
  while (std::cin >> n, n) {
    int sum = 0;
    for (int i = 0; i < 9; i++) {
      int tmp;
      std::cin >> tmp;
      sum += tmp;
    }
    std::cout << n - sum << std::endl;
  }
  return 0;
}

Measured memory_bytes: 1160
#解説を写経することは最高に悪魔的な行為だ…
def between(x,y1,y2):
    if y1>y2:y1,y2=y2,y1
    y1+=1;y2-=1
    if not(y1<=y2):
        return False
    while(x>0):
        if x%3==1:
            if y2-y1>3:
                return True
            for y in range(y1,y2+1):
                if y%3==1:
                    return True
        x//=3
        y1//=3
        y2//=3
    return False
def get_extra(x1,y1,x2,y2):
    ans=0
    three=1
    for i in range(35):
        if(x1//three==x2//three and between(x1//three,y1//three,y2//three)):
            tmp=min(min(x1%three,x2%three)+1,three-max(x1%three,x2%three))
            ans=max(ans,tmp)
        three*=3
    return ans
def get_dist(x1,y1,x2,y2):
    return abs(x1-x2)+abs(y1-y2)+2*max(get_extra(x1,y1,x2,y2),get_extra(y1,x1,y2,x2))
Q=int(input())
for i in range(Q):
    a,b,c,d=map(int,input().split())
    print(get_dist(a-1,b-1,c-1,d-1))

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

int main() {
  int64_t n;
  std::cin >> n;

  std::set<int64_t> a;

  for (int64_t i = 0; i < n; i++) {
    int64_t t;
    std::cin >> t;
    if (a.find(t) == a.cend()) {
      a.insert(t);
    } else {
      a.erase(t);
    }
  }

  std::cout << a.size() << std::endl;
  return 0;
}


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

int main() {
	long long int a,b,c,ans;
  cin>>a>>b;
  ans=0;
  vector<long long int> vec(a);
  for(int i=0;i<a;i++){
  	cin>>vec.at(i);
  }
  sort(vec.begin(),vec.end());
  
  for(int i=0;i<a-b;i++){
  	ans += vec.at(i);
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 1792
import static java.lang.Math.*;
import static java.util.Arrays.*;
import java.util.*;
import java.io.*;

public class Main {

	void solve() {
		int N = sc.nextInt();
		int K = sc.nextInt();
		boolean[] ng = new boolean[10];
		for (int i = 0; i < K; i++) {
			ng[sc.nextInt()] = true;
		}
		
		
		int ans = N;
		while (!check(ans, ng)) ++ans;
		out.println(ans);
	}
	
	boolean check(int n, boolean[] ng) {
		boolean ok = true;
		while (n > 0) {
			if (ng[n % 10]) return false;
			n /= 10;
		}
		return ok;
	}
	
	static void tr(Object... os) { System.err.println(deepToString(os)); }
	static void tr(int[][] as) { for (int[] a : as) tr(a); }

	void print(int[] a) {
		out.print(a[0]);
		for (int i = 1; i < a.length; i++) out.print(" " + a[i]);
		out.println();
	}

	public static void main(String[] args) throws Exception {
		new Main().run();
	}

	MyScanner sc = null;
	PrintWriter out = null;
	public void run() throws Exception {
		sc = new MyScanner(System.in);
		out = new PrintWriter(System.out);
		for (;sc.hasNext();) {
			solve();
			out.flush();
		}
		out.close();
	}

	class MyScanner {
		String line;
		BufferedReader reader;
		StringTokenizer tokenizer;

		public MyScanner(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream));
			tokenizer = null;
		}
		public void eat() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					line = reader.readLine();
					if (line == null) {
						tokenizer = null;
						return;
					}
					tokenizer = new StringTokenizer(line);
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
		}
		public String next() {
			eat();
			return tokenizer.nextToken();
		}
		public String nextLine() {
			try {
				return reader.readLine();
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}
		public boolean hasNext() {
			eat();
			return (tokenizer != null && tokenizer.hasMoreElements());
		}
		public int nextInt() {
			return Integer.parseInt(next());
		}
		public long nextLong() {
			return Long.parseLong(next());
		}
		public double nextDouble() {
			return Double.parseDouble(next());
		}
		public int[] nextIntArray(int n) {
			int[] a = new int[n];
			for (int i = 0; i < n; i++) a[i] = nextInt();
			return a;
		}
	}
}

Measured memory_bytes: 8148
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;

long long value[110][100010];

int main() {
    int n, W;
    cin >> n >> W;
    vector<P> goods(n+1);
    for(int i = 1; i <= n; i++)
        cin >> goods[i].first >> goods[i].second;

    for(int w = 0; w <= W; w++) {
        if(goods[1].first <= w)
            value[1][w] = goods[1].second;
    }

    for(int i = 2; i <= n; i++) {
        P g = goods[i];
        for(int w = 0; w <= W; w++) {
            if(w - g.first >= 0)
                value[i][w] = max(value[i-1][w-g.first] + g.second,
                                  value[i-1][w]);
            else
                value[i][w] = value[i-1][w];
        }
    }

    cout << value[n][W] << endl;
}



Measured memory_bytes: 79360
#include <iostream>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <bitset>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef pair<ll,ll> P;
typedef vector<P> vpl;
#define rep(i,n) for(ll i=0; i<(n); i++)
#define REP(i,a,b) for(ll i=(a); i<(b); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const int inf = 1<<30;
const ll linf = 1LL<<62;
const int MAX = 510000;
ll dy[8] = {0,1,0,-1,1,-1,1,-1};
ll dx[8] = {1,0,-1,0,1,-1,-1,1};
const double pi = acos(-1);
const double eps = 1e-7;
template<typename T1,typename T2> inline bool chmin(T1 &a,T2 b){
	if(a>b){
		a = b; return true;
	}
	else return false;
}
template<typename T1,typename T2> inline bool chmax(T1 &a,T2 b){
	if(a<b){
		a = b; return true;
	}
	else return false;
}
template<typename T1,typename T2> inline void print2(T1 a, T2 b){cout << a << " " << b << endl;}
template<typename T1,typename T2,typename T3> inline void print3(T1 a, T2 b, T3 c){
	cout << a << " " << b << " " << c << endl;
}
const int mod = 1e9 + 7;

ll modpow(ll x, ll n, ll mod){
	ll res = 1;
	while(n > 0){
		if(n & 1) res = res * x % mod;
		x = x * x % mod;
		n >>= 1;
	}
	return res;
}

vector<ll> fac(MAX), finv(MAX), inv(MAX);

void comInit(){
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for(ll 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;
	}
}


ll com(ll n, ll k){
	if(n < k) return 0;
	if(n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n-k] % mod) % mod;
}

int main(){
	comInit();
	ll n,a,b; cin >> n >> a >> b;
	ll minus = 0;
	ll cnt = 1;
	rep(i,a){
		cnt *= (n-i)*inv[i+1]%mod;
		cnt %= mod;
	}
	minus += cnt;
	cnt = 1;
	rep(i,b){
		cnt *= (n-i)*inv[i+1]%mod;
		cnt %= mod;
	}
	minus += cnt;
	minus %= mod;
	ll ans = modpow(2,n,mod) - minus - 1;
	while(ans < 0) ans += mod;
	cout << ans << endl;
}

Measured memory_bytes: 12160
#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

const int INF (1<<28);
const int MAX_M = 20;
const int MAX_N = 50000;

int COINS[MAX_M+1];
int CNTS[MAX_M+1][MAX_N+1];

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

  for (int i = 1; i <= m; i++)
    cin >> COINS[i];

  memset(CNTS, 0, sizeof(CNTS));

  for (int i = 0; i <= n; i++) CNTS[0][i] = INF;

  for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
      if (j - COINS[i] < 0)
        CNTS[i][j] = CNTS[i-1][j];
      else
        CNTS[i][j] = min(CNTS[i][j-COINS[i]] + 1, CNTS[i-1][j]);
    }
  }

  cout << CNTS[m][n] << endl;
}

Measured memory_bytes: 5268
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a; i< (int)(b); ++i)
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
typedef long double ld;
using ll=long long;
using namespace std;
const auto mod=1e9+7;


int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(20);
  
  int n; cin >> n;
  vector<pair<int, int>> p(n);
  vector<int> a(n);
  rep(i,0,n){
  	 cin >> a[i];
  	 p[i].first=a[i];
  	 p[i].second=i+1;
  }
  sort(All(p));
  rep(i,0,n) cout << p[i].second << " " ;
  cout  << endl;
  
}

Measured memory_bytes: 2048
n = int(input())
a = list(map(int,input().split()))
q = int(input())
for i in range(q):
  b1, b2 = map(int,input().split())
  b = a[b1:b2]
  b.reverse()
  k = 0
  for j in range(n):
    if b1 <= j < b2 :
      a[j] = b[k]
      k += 1

print(a[0],end="")
for aa in a[1:]:
  print(" {}".format(aa),end="")
print()
  
   


Measured memory_bytes: 5816