akhauriyash/Code-Regression huggingface dataset:
open Batteries
module EnumL = Enum.Labels
module ListL = List.Labels
module ArrayL = Array.Labels

let dbg0 x = Printf.eprintf "[debug]%s\n" @@ dump x
let dbg1 x = dbg0 x; x

let id = identity

let (++) n m = List.range n `To m
let (++-) n m = if n >= m then List.range n `Downto m else []
let (++^) n m = if n < m then List.range n `To (pred m) else []

module ModOp = struct
  let prime = 1_000_000_007
  let (-) a b = (a + prime - b) mod prime
  let (+) a b = (a + b) mod prime
  let ( * ) a b = (a * b) mod prime

  let rec pow x n =
    if n = 0 then 1
    else if n mod 2 = 0 then pow (x*x) (n/2)
    else x * pow (x*x) (n/2)
end

let scan fmt = Scanf.sscanf (read_line ()) fmt

let scan_lines n fmt f =
  if n = 0 then []
  else List.map (fun _ -> scan fmt f) (1 ++ n)

let scan_list ?sep cnv =
  let line = read_line () in
  (match sep with
   | None -> List.map String.of_char @@ String.to_list line
   | Some sep -> String.split_on_char sep line)
  |> List.map cnv

let scan_array ?sep cnv = Array.of_list @@ scan_list ?sep cnv

let scan_matrix n m e ?sep conv =
  let arr = Array.make_matrix n m e in
  ListL.iter (0 ++^ n)
    ~f:(fun i -> arr.(i) <- Array.of_list @@ scan_list ?sep conv);
  arr

let atoi c = Char.code c - Char.code '0'

let rec powerset = function
  | [] -> [[]]
  | hd::tl ->
    let pws =  powerset tl in
    pws @ ListL.map pws ~f:(fun pw -> hd::pw)

let permutations l =
  let rec interleave x = function
    | [] -> [[x]]
    | (hd::tl) as l ->
      (x::l) :: (interleave x tl |> ListL.map ~f:(fun l -> hd::l)) in
  let rec aux = function
    | [] -> [[]]
    | a::rest ->
      aux rest |> ListL.map ~f:(interleave a) |> List.concat in
  aux l

let intersection l =
  EnumL.filter ~f:(fun x -> EnumL.exists ~f:((=) x) @@ Enum.clone l)

let zip l m =
  let n = min (List.length l) (List.length m) in
  List.combine (List.take n l) (List.take n m)

let lower_bound n f =
  let rec aux l u =
    if u - l > 1 then
      let m = (l + u) / 2 in
      if f m then aux l m
      else aux m u
    else u in aux (-1) n

let between n x m = n <= x && x < m

let (n,k) = scan "%d %d" Tuple2.make
let arr = scan_array ~sep:' ' Int.of_string

let visited = Array.make n false

let rec to_num from to_ n =
  if from = to_ then n
  else to_num arr.(pred from) to_ @@ succ n

let rec loop i =
  if visited.(pred i) then i
  else
    (visited.(pred i) <- true;
     loop arr.(pred i))

let rec route n i =
  if n = 0 then i
  else route (pred n) arr.(pred i)

let () =
  let loop_n = loop 1 in
  let loop_num = to_num arr.(pred loop_n) loop_n 1 in
  let to_loop = to_num 1 loop_n 0 in
  Printf.printf "%d\n"
    (if k < to_loop then route k 1
     else route ((k-to_loop) mod loop_num) loop_n)


Measured memory_bytes: 25848
#include <bits/stdc++.h> 
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
//typedef pair<ll, ll> P;
//typedef pair<int, pair<int, int>> P;
//typedef tuple<int,int,int> T;
ll INFL = 1000000000000000010;//10^18 = 2^60
int INF = 2147483600;//10^9
ll MOD  = 1000000007;
vector<int> dy = {0,0,1,-1};
vector<int> dx = {1,-1,0,0};
int n;
vector<int> G[200010];
int dist[200010];


void dfs(int v, int p, int d)
{
	dist[v] = d;
	for(int i = 0; i < G[v].size(); i++){
		if(G[v][i] == p) continue;
		dfs(G[v][i], v, d+1);
	}
}

vector<int> d(200020, INF);
void dijkstra(int x){
    priority_queue<P, vector<P>, greater<P>> pque;
    pque.push({0, x});
    d[x] = 0;
    while(!pque.empty()){
        int c = pque.top().first;
        int v = pque.top().second;
        pque.pop();
        if(c > d[v]) continue;
        
        for(int i = 0; i < G[v].size(); i++){
            int nv = G[v][i];
            if(d.at(nv) > c + 1){
                d.at(nv) = c+1;
                pque.push({c+1, nv});
            }
        }
    }
}


int main(void){
    cin >> n;
	int u, v;
	for(int i = 1; i < n; i++){
		cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
    
    
    dfs(1, -1, 0);
	int mx = 0, root;
	for(int i = 1; i <= n; i++){
		if(mx < dist[i]){
			mx = dist[i];
			root = i;
		}
	}
	int a = root;
	
	dfs(root, -1, 0);
	mx = 0;
	for(int i = 1; i <= n; i++){
		if(mx < dist[i]){
			mx = dist[i];
			root = i;
		}
	}
	int b = root;
	
    dijkstra(a);
    int l = d[b];
    
    if(l % 3 == 1){
        cout << "Second" << endl;
    }else{
        cout << "First" << endl;
    }
}


Measured memory_bytes: 25216
#Q2

x1, y1, x2, y2 = list(map(int,input().strip().split(' ')))
v12x = (x2 - x1)
v12y = (y2 - y1)

x4, y4 = x1 - v12y, y1 + v12x
x3, y3 = x2 - v12y, y2 + v12x 

print(x3, y3, x4, y4)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
typedef long  long ll;
ll cnt(ll arr[],ll n,ll *dp)
{
    if(n<=0)
        return 0;
    if(dp[n]!=-1)
        return dp[n];
    ll a1=INT_MAX,a2=INT_MAX;
    if(n>=2)
    {
        a1=abs(arr[n]-arr[n-1])+cnt(arr,n-1,dp);
        a2=abs(arr[n]-arr[n-2])+cnt(arr,n-2,dp);
    }
    else
    {
        a1=abs(arr[n]-arr[n-1])+cnt(arr,n-1,dp);
    }
    return dp[n]=min(a1,a2);
}
int main()
{
    ll n;
    cin>>n;
    ll arr[n];
    for(ll i=0;i<n;i++)
        cin>>arr[i];
    ll dp[n];
    for(ll i=0;i<n;i++)
        dp[i]=-1;
    cout<<cnt(arr,n-1,dp);


    return 0;
}


Measured memory_bytes: 9600
n,m=map(int,input().split())
a=list(map(int,input().split()))
a_sort=[]
a_sort=sorted(a,reverse=True)
sum=0
for i in a:
  sum+=i
b_sort=a_sort[0:m]
for j in b_sort:
 if j<sum/(4*m):
    print("No")
    exit()
print("Yes")

Measured memory_bytes: 9184
import queue as qu

mod = 10 ** 9 + 7
N, K = map(int, input().split())
D = {n: set() for n in range(N)}
for n in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    D[a].add(b)
    D[b].add(a)

res = 1
F = [0] * N
already = [False] * N

q = qu.Queue()
q.put(0)
for _ in range(N):
    n = q.get()
    already[n] = True
    d = D[n]

    m = 2 if n else 1
    for b in d:
        if already[b]:
            continue
        F[b] = m
        m += 1
        q.put(b)
        
if max(F) >= K:
    print(0)
else:
    res = 1
    for f in F:
        res = (res * (K - f)) % mod
    print(res)


Measured memory_bytes: 51804
import sys
input = lambda: sys.stdin.readline().rstrip() 

def resolve():
    A, B, C, X, Y = map(int, input().split())

    ans = 0
    if A+B > 2*C:
        ans = 2*C*min(X, Y)+min((A if X>Y else B)*abs(X-Y), 2*C*abs(X-Y))
    else:
        ans = A*X+B*Y
    
    print(ans)

if __name__ == '__main__':
    resolve()


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 ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))


typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
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);

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

int main(){
    int n, w;
    cin >> n >> w;
    int W[110], V[110];

    for(int i=0; i<n; i++){
        cin >> W[i] >> V[i];
    }

    vector<ll> itm[5];
    ll w1 = W[0];

    for(int i=0; i<n; i++){
        itm[W[i]-w1].pb(V[i]);
    }

    for(int i=0; i<5; i++) sort(itm[i].begin(), itm[i].end());

    for(int i=0; i<5; i++){
        itm[i].pb(0);
        reverse(itm[i].begin(), itm[i].end());
    }

    ll value_max = -1;

    for(int i=0; i<itm[0].size(); i++)if(i+1 != itm[0].size()) itm[0][i+1] += itm[0][i];

    for(int j=0; j<itm[1].size(); j++)if(j+1 != itm[1].size()) itm[1][j+1] += itm[1][j];

    for(int k=0; k<itm[2].size(); k++)if(k+1 != itm[2].size()) itm[2][k+1] += itm[2][k];

    for(int l=0; l<itm[3].size(); l++)if(l+1 != itm[3].size()) itm[3][l+1] += itm[3][l];
    

    // unsigned int で0-1はUNSINGED_INTMAX-1になるのでやばい
    for(int i=0; i<itm[0].size(); i++){
        for(int j=0; j<itm[1].size(); j++){
            for(int k=0; k<itm[2].size(); k++){
                for(int l=0; l<itm[3].size(); l++){
                    ll val_sum = 0;
                    val_sum = itm[0][i] + itm[1][j] + itm[2][k] + itm[3][l];
                    ll sum_W = w1*i + (w1+1)*j + (w1+2)*k + (w1+3)*l;
                    if(sum_W <= w && value_max < val_sum) value_max = val_sum;
                }
            }
        }
    }

    cout << value_max << endl;

}

Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author silviase
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        CBackAndForth solver = new CBackAndForth();
        solver.solve(1, in, out);
        out.close();
    }

    static class CBackAndForth {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int sx = in.nextInt();
            int sy = in.nextInt();
            int tx = in.nextInt();
            int ty = in.nextInt();

            int yoko = tx - sx;
            int tate = ty - sy;
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < yoko; i++) {
                sb.append("R");
            }
            for (int i = 0; i < tate; i++) {
                sb.append("U");
            }
            for (int i = 0; i < yoko; i++) {
                sb.append("L");
            }
            for (int i = 0; i <= tate; i++) {
                sb.append("D");
            }
            for (int i = 0; i <= yoko; i++) {
                sb.append("R");
            }
            for (int i = 0; i <= tate; i++) {
                sb.append("U");
            }
            sb.append("LU");
            for (int i = 0; i <= yoko; i++) {
                sb.append("L");
            }
            for (int i = 0; i <= tate; i++) {
                sb.append("D");
            }
            sb.append("R");

            out.println(sb);
        }
    }
}



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

int main() {
  int n, K;
  cin >> n >> K;
  int ans = 1;
  while(n > 0 && ans <= K) {
    ans *= 2;
    n--;
  }
  while(n > 0) {
    ans += K;
    n--;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,x[200005];
inline void F(ll y){
	long long res=0;
	for(int i=1;i<=n;i++)res+=abs(x[i-1]-y);
	cout<<res;
}
int main(){
	cin>>n;
	ll pnt=0;
	for(int i=0;i<n;i++)cin>>x[i],x[i]-=i+1;
	sort(x,x+n);
	pnt=x[n/2];
	F(pnt);
	return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>
#define LEN 100000

typedef struct{
	char name[10];
	int t;
}P;

P Q[LEN];
int head,tail,n;

void enqueue(P);
P dequeue();

int main(){
	int elaps = 0;
	int i,q;
	P u;

	scanf("%d %d",&n,&q);
	for(i = 0;i < n;i++)
		scanf("%s %d",Q[i].name,&Q[i].t);
	tail = n;

	while(head != tail){
		u = dequeue();
		if(u.t <= q){
			elaps += u.t;
			printf("%s %d\n",u.name,elaps);
		}
		else{
			u.t -= q;
			elaps += q;
			enqueue(u);
		}
	}
	return 0;
}

void enqueue(P u){
	Q[tail] = u;
	if(tail+1 == LEN)
		tail = 0;
	else
		tail++;
}

P dequeue(){
	if(head == LEN)
		head = 0;
	return Q[head++];
}


Measured memory_bytes: 3356
package main

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

func out(x ...interface{}) {
	fmt.Println(x...)
}

var sc = bufio.NewScanner(os.Stdin)

func getInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getInts(N int) []int {
	ret := make([]int, N)
	for i := 0; i < N; i++ {
		ret[i] = getInt()
	}
	return ret
}

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

// min, max, asub, absなど基本関数
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func asub(a, b int) int {
	if a > b {
		return a - b
	}
	return b - a
}

func abs(a int) int {
	if a >= 0 {
		return a
	}
	return -a
}

func lowerBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] >= x
	})
	return idx
}

func upperBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] > x
	})
	return idx
}

//　セグメント木
const inf = 1100100100
const mod = 998244353

type segtree struct {
	n int
	v []int
	a []int // 加算値
}

func (s *segtree) op(a, b int) int {
	return (a + b) % mod
}

func (s *segtree) init(n int) {
	N := 1
	for n > N {
		N *= 2
	}
	s.v = make([]int, N*2)
	s.a = make([]int, N*2)
	s.n = N
}

func (s *segtree) update() {
	K := s.n
	for K > 0 {
		K /= 2
		for i := K; i < 2*K; i++ {
			s.v[i] = s.compare(s.v[i*2], s.v[i*2+1])
		}
	}
}

func (s *segtree) lazyCalc(k int) {
	s.v[k] = s.op(s.v[k], s.a[k])
	if k < s.n {
		s.a[2*k] = s.op(s.a[2*k], s.a[k])
		s.a[2*k+1] = s.op(s.a[2*k+1], s.a[k])
	}
	s.a[k] = 0
}

func (s *segtree) compare(p, q int) int {
	if p > q {
		return q
	}
	return p
}

func (s *segtree) setSub(a, b, k, l, r, x int) {
	if b <= l || r <= a {
		return
	}
	if a <= l && r <= b {
		s.a[k] += x
		s.lazyCalc(k)
	} else {
		s.lazyCalc(k)
		s.setSub(a, b, k*2, l, (l+r)/2, x)
		s.setSub(a, b, k*2+1, (l+r)/2, r, x)
		s.v[k] = s.compare(s.v[2*k], s.v[2*k+1])
	}
}

// set v[k] = val
func (s *segtree) set(a, b, x int) {
	s.setSub(a, b, 1, 0, s.n, x)
}

// querySub
func (s *segtree) querySub(a, b, k, l, r int) int {
	s.lazyCalc(k)
	if b <= l || r <= a {
		return inf
	}
	if a <= l && r <= b {
		return s.op(s.v[k], s.a[k])
	}
	return s.compare(
		s.querySub(a, b, k*2, l, (l+r)/2),
		s.querySub(a, b, k*2+1, (l+r)/2, r))
}

// query([a,b) )
func (s *segtree) query(a, b int) int {
	return s.querySub(a, b, 1, 0, s.n)
}

func main() {
	sc.Split(bufio.ScanWords)
	sc.Buffer([]byte{}, 1000000)
	N, K := getInt(), getInt()
	l := make([]int, K)
	r := make([]int, K)
	for i := 0; i < K; i++ {
		l[i], r[i] = getInt(), getInt()
	}

	var s segtree
	s.init(2*N + 1)
	s.set(1, 2, 1)
	for i := 1; i < N; i++ {
		v := s.query(i, i+1)
		// out(i, v)
		for k := 0; k < K; k++ {
			ll := i + l[k]
			rr := i + r[k]
			s.set(ll, rr+1, v)
		}
	}
	out(s.query(N, N+1))
}


Measured memory_bytes: 14928
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int h,a;
	cin>>h>>a;
	int ans=ceil(h/float(a));
	cout<<ans;
	return 0;
	
}

Measured memory_bytes: 3616
//参考：http://ehafib.hatenablog.com/entry/2015/12/23/164517
//インクルード
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列

using namespace std;
typedef long long ll;

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

  ll n, k;
	cin >> n >> k;
  ll ans;

  ans = min(n%k, k-(n%k));
	cout << ans << "\n";
}


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

const int INF= 1e9 +5;
typedef std::vector<int> vi;
typedef pair<int,int> ii;

const int nax = 1e5 + 5;
vector<int> edges[nax];
int in_degree[nax]; // the number of edges going to 'b'
int dist[nax];
bool visited[nax];

void dfs(int a) {
    assert(!visited[a]);
    visited[a] = true;
    for(int b : edges[a]) {
        dist[b] = max(dist[b], dist[a] + 1);
        --in_degree[b];
        if(in_degree[b] == 0) {
            dfs(b);
        }
    }
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    while(m--) {
        int a, b;
        scanf("%d%d", &a, &b);
        edges[a].push_back(b);
        ++in_degree[b];
    }
    for(int i = 1; i <= n; ++i) {
        if(!visited[i] && in_degree[i] == 0) {
            dfs(i);
        }
    }
    int answer = 0;
    for(int i = 1; i <= n; ++i) {
        answer = max(answer, dist[i]);
    }
    printf("%d\n", answer);
}

Measured memory_bytes: 9728
package main

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

var sc = bufio.NewScanner(os.Stdin)

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

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

type Ball struct {
	number int
	count int
}

type Balls []Ball

func (b Balls) Len() int {
	return len(b)
}

func (b Balls) Less(i, j int) bool {
	return b[i].count < b[j].count
}

func (b Balls) Swap(i, j int) {
	b[i], b[j] = b[j], b[i]
}

func main() {
	sc.Split(bufio.ScanWords)

	N, K := nextInt(), nextInt()
	bucket := map[int]int{}
	var balls []Ball

	for i := 0; i < N; i++ {
		bucket[nextInt()]++
	}

	for num, c := range bucket {
		balls = append(balls, Ball{num, c})
	}

	sort.Sort(Balls(balls))

	c := 0
	for {
		if len(balls) <= K {
			fmt.Println(c)
			return
		}

		c += balls[0].count
		balls = balls[1:]
	}
}


Measured memory_bytes: 23040
#include <iostream>
#include <string>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <assert.h>
#include <map>
#include <set>
#include <bitset>
#include <iomanip>
#include <stack>
#include <unordered_map>
#include <cmath>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define INF 0x7f7f7f7f  //2139062143
#define INF1 0x3f3f3f3f //1061109567
#define INF2 2147483647
#define llINF 9223372036854775807
#define pi 3.14159265358979323846264338327950254
#define pb push_back
#define ll long long
#define debug cout << "debug\n";
#define STDIN                      \
    freopen("in.txt", "r", stdin); \
    freopen("out.txt", "w", stdout);
#define IOS                      \
    ios::sync_with_stdio(false); \
    cin.tie(NULL);
#define scai(x) scanf("%d", &x)
#define sca2i(x, y) scanf("%d %d", &x, &y)
#define scaf(x) scanf("%lf", &x)
#define sca2f(x, y) scanf("%lf %lf", &x, &y)
#define For(m, n) for (int i = m; i < n; i++)
#define PII pair<int, int>
#define PLL pair<long, long>
#define ft first
#define sd second
#define pb push_back
#define lson o << 1, l, mid
#define rson o << 1 | 1, mid + 1, r
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define ROF(i, a, b) for (int i = (a); i >= (b); i--)
#define MEM(x, v) memset(x, v, sizeof(x))
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define rrep(i, a, b) for (int i = a; i >= b; i--)
inline int read()
{
    char ch = getchar();
    int x = 0, f = 0;
    while (ch < '0' || ch > '9')
        f |= ch == '-', ch = getchar();
    while (ch >= '0' && ch <= '9')
        x = x * 10 + ch - '0', ch = getchar();
    return f ? -x : x;
}

int main() {
    // STDIN
    int a, b, c, k; cin >> a >> b >> c >> k;
    if (k > a + b) cout << a - (k-a-b) << endl;
    else if (k > a) cout << a << endl;
    else cout << k << endl;
}


Measured memory_bytes: 3140
n, m = [int(i) for i in input().split()]
a_list = []
b_list = []
for i in range(m):
    a, b = [int(i) for i in input().split()]
    a_list.append(a)
    b_list.append(b)

class UnionFind:
    # 親の番号を格納する。自身が親だったら-(その集合のサイズ)
    def __init__(self, n):
        self.parent = [-1 for i in range(n)]

    # aがどのグループに属しているか調べる
    def root(self, a):
        if self.parent[a] < 0:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]

    # aのサイズを返す
    def size(self, a):
        return -self.parent[self.root(a)]

    # aとｂをつなげる
    def connect(self, a, b):
        A = self.root(a)
        B = self.root(b)
        if A == B:
            return False

        # 大きい方(A)に小さい方(B)をつなげたい
        if self.size(B) > self.size(A):
            A, B = B, A

        self.parent[A] += self.parent[B]
        self.parent[B] = A
        return True

ans = [0 for i in range(m)]
ans[m-1] = n * (n-1) / 2

union_find = UnionFind(n)

for i in range(1, m)[::-1]:
    a = a_list[i] - 1
    b = b_list[i] - 1
    if union_find.root(a) == union_find.root(b):
        # すでにつながっている場合
        ans[i-1] = ans[i]
    else:
        # つながってないものがつながったとき
        a_size = union_find.size(a)
        b_size = union_find.size(b)
        diff = a_size * b_size
        ans[i-1] = ans[i] - diff
        union_find.connect(a, b)

for i in ans:
    print(int(i))

Measured memory_bytes: 17720
#include<bits/stdc++.h>
#define l(i,n) for(int i=0;i<n;i++)
using namespace std;
bool m[12][12],c[12][12],d[12][12],q;
int main(){int n;cin>>n;l(u,n){l(i,10)l(j,10)cin>>m[i][j];
bool f[10],t[10]={0};for(int p=1;p<=1024;p++){
l(i,10)f[i]=t[i];l(i,10)l(j,10)c[i][j]=m[i][j];l(k,10){l(i,10)
if(f[i]){for(int j=max(0,i-1);j<=min(9,i+1);j++)c[k][j]^=1;c[k+1][i]^=1;}
l(i,10)d[k][i]=f[i];l(i,10)f[i]=c[k][i];}q=0;l(i,10)q|=f[i];
if(!q){l(i,10){l(j,10){if(j)cout<<" ";cout<<d[i][j];}cout<<endl;}
break;}l(i,10)if(p%(int)pow(2,i)==0)t[i]^=1;
}}return 0;}

Measured memory_bytes: 3240
#define CPP17
#include <limits>
#include <initializer_list>
#include <utility>
#include <bitset>
#include <tuple>
#include <type_traits>
#include <functional>
#include <string>
#include <array>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <iterator>
#include <algorithm>
#include <complex>
#include <random>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <regex>
#include <cassert>
#include <cstddef>
#ifdef CPP17
#include <variant>
#endif

// Yay!!
#define endl codeforces

// macros for iterator
#define ALL(v) std::begin(v), std::end(v)
#define ALLR(v) std::rbegin(v), std::rend(v)

// alias
using ll = std::int64_t;
using ull = std::uint64_t;
using pii = std::pair<int, int>;
using tii = std::tuple<int, int, int>;
using pll = std::pair<ll, ll>;
using tll = std::tuple<ll, ll, ll>;
template <typename T> using vec = std::vector<T>;
template <typename T> using vvec = vec<vec<T>>;

// variadic min/max
template <typename T> const T& var_min(const T &t) { return t; }
template <typename T> const T& var_max(const T &t) { return t; }
template <typename T, typename... Tail> const T& var_min(const T &t, const Tail&... tail) { return std::min(t, var_min(tail...)); }
template <typename T, typename... Tail> const T& var_max(const T &t, const Tail&... tail) { return std::max(t, var_max(tail...)); }

// variadic chmin/chmax
template <typename T, typename... Tail> void chmin(T &t, const Tail&... tail) { t = var_min(t, tail...); }
template <typename T, typename... Tail> void chmax(T &t, const Tail&... tail) { t = var_max(t, tail...); }

// multi demension array
template <typename T, std::size_t Head, std::size_t... Tail> struct multi_dim_array { using type = std::array<typename multi_dim_array<T, Tail...>::type, Head>; };
template <typename T, std::size_t Head> struct multi_dim_array<T, Head> { using type = std::array<T, Head>; };
template <typename T, std::size_t... Args> using mdarray = typename multi_dim_array<T, Args...>::type;

#ifdef CPP17
// fill container
template <typename T, typename F, typename... Args> 
void fill_seq(T &t, F f, Args... args) { if constexpr (std::is_invocable<F, Args...>::value) { t = f(args...); } else { for (ssize_t i = 0; i < t.size(); i++) fill_seq(t[i], f, args..., i); } }
#endif

// make multi dimension vector
template <typename T> vec<T> make_v(ssize_t sz) { return vec<T>(sz); }
template <typename T, typename... Tail> auto make_v(ssize_t hs, Tail&&... ts) { auto v = std::move(make_v<T>(std::forward<Tail>(ts)...)); return vec<decltype(v)>(hs, v); }

// init
namespace init__ { 
struct InitIO { InitIO() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); std::cout << std::fixed << std::setprecision(30); } } init_io; 
}


int main() {
    ll n;
    std::cin >> n;
    vec<ll> av(n);
    for (ll &e : av) std::cin >> e;
    ll sum = 0;
    for (ll e : av) sum ^= e;
    for (ll i = 0; i < n; i++) std::cout << (sum ^ av[i]) << " \n"[i + 1 == n];
    return 0;
}


Measured memory_bytes: 4780
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define rt register int
#define l putchar('\n')
#define ll long long
#define r read()
#define p 998244353
using namespace std;
inline ll read(){
    ll x = 0; char zf = 1; char ch = getchar();
    while (ch != '-' && !isdigit(ch)) ch = getchar();
    if (ch == '-') zf = -1, ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar(); return x * zf;
}
void write(ll y){if(y<0)putchar('-'),y=-y;if(y>9)write(y/10);putchar(y%10+48);}
void writeln(const ll y){write(y);putchar('\n');}
int i,j,k,m,n,x,y,z,cnt,sum;
int id[1010];
int main(){
	n=r;
	if(n&1){
		id[n]=++cnt;
		for(rt i=1;i<=n/2;i++)id[i]=id[n-i]=++cnt;
	}
	else {
		for(rt i=1;i<=n/2;i++)id[i]=id[n+1-i]=++cnt;
	}
	for(rt i=1;i<=n;i++)for(rt j=i+1;j<=n;j++)
	if(id[i]!=id[j])sum++;writeln(sum);
	for(rt i=1;i<=n;i++)for(rt j=i+1;j<=n;j++)
	if(id[i]!=id[j])cout<<i<<' '<<j<<endl;
    return 0;
}








Measured memory_bytes: 256
#include<iostream>
#include<cstring>
using namespace std;
int main(){
	char a[110];
	cin>>a;
	int s=0;
	for(int i=0;i<strlen(a);i++){
		if(i==0)cout<<a[i];
		else
		if(i==strlen(a)-1)cout<<s<<a[i];
		else
		s++;
	}
}

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

int k,n=3;
int a[4][4],b[4][4];

signed main()
{
	for (int i=1;i<=3;i++)
	{
		for (int j=1;j<=3;j++)  cin>>a[i][j];
	}
	cin>>k;
	for (int i=1;i<=k;i++)
	{
		int x,flag=1;
		cin>>x;
		for (int j=1;j<=n;j++)
		{
			for (int k=1;k<=n;k++)
			{
				if (a[j][k]==x)
				{
					b[j][k]=1;
					flag=0;
					break;
				}
			} 
			if (flag==0)  break;
		}
	}
	for (int i=1;i<=3;i++)
	{
		int flag=1;
		for (int j=1;j<=3;j++)
		{
			if (!b[i][j])
			{
				flag=0;
				break;
			}	
		}
		if (flag==1)
		{
			cout<<"Yes"<<endl;
			return 0;
		}
	}
	for (int j=1;j<=3;j++)
	{
		int flag=1;
		for (int i=1;i<=3;i++)
		{
			if (!b[i][j])
			{
				flag=0;
				break;
			}
		}
		if (flag==1)
		{
			cout<<"Yes"<<endl;
			return 0;
		}
	}
	if (b[1][1]&&b[2][2]&&b[3][3])
	{
		cout<<"Yes"<<endl;
		return 0;
	}
	if (b[1][3]&&b[2][2]&&b[3][1])
	{
		cout<<"Yes"<<endl;
		return 0;
	}
	cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 256
//
//  main.cpp
//  union_find_tree
//
//  Created by ???????????? on 2017/11/11.
//  Copyright ?? 2017 ????????????. All rights reserved.
//

#include <iostream>
#include <vector>
#include <stdio.h>

using namespace std;

class DisjointSet{
public:
    vector<int> parent, rank;
    
    DisjointSet(int num){
        for(int i = 0; i < num; i ++){
            parent.push_back(i);
            rank.push_back(1);
        }
    }
    
    void unite(int temp1, int temp2){
        int rank1 = rank[temp1];
        int rank2 = rank[temp2];
        int newRank = rank1 + rank2;
        int rank1Parent = parent[temp1];
        int rank2Parent = parent[temp2];
        if(rank1 > rank2){
            update(rank2Parent, rank1Parent, newRank);
        }
        else{
            update(rank1Parent, rank2Parent, newRank);
        }
    }
    
    // update from dummy's parent to target's parent
    void update(int dummy, int target, int newRank){
        for (int i = 0; i < parent.size(); i++){
            if(parent[i] == dummy || parent[i] == target){
                rank[i] = newRank;
                if(parent[i] == dummy){
                    parent[i] = target;
                }
            }
        }
    }
    
    void findSet(int temp1, int temp2){
        int p1 = parent[temp1];
        int p2 = parent[temp2];
        
        if (p1 == p2){cout <<1<<endl;}
        else {cout <<0 << endl;}
    }
};

int main(int argc, const char * argv[]) {
    int num, num_com, command, temp1, temp2;
    
    scanf("%d %d", &num, &num_com);
    DisjointSet ds = DisjointSet(num);
    for (int i = 0; i < num_com; i++){
        scanf("%d %d %d", &command, &temp1, &temp2);
        if(command == 0){
            ds.unite(temp1, temp2);
        }
        else if(command == 1){
            ds.findSet(temp1, temp2);
        }
    }

//    std::cout << "Hello, World!\n";
    return 0;
}

Measured memory_bytes: 3340
#include <stdio.h>

int main(void)
{
	int W,H,x,y,r;
	
	scanf("%d %d %d %d %d",&W,&H,&x,&y,&r);
	
	if (0<=x-r && x+r<=W && 0<=y-r && y+r<=H){
		printf("Yes\n");
	}else{
		printf("No\n");
	}
	return 0;
}

Measured memory_bytes: 584
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int t=1,n,k;
    while(t--)
    {
        long long int s=0;
        cin>>n>>k;
        int a[n];
        for(int i=0;i<n;i++)
        {
            cin>>a[i];
        }
        sort(a,a+n);
        for(int i=0;i<k;i++)
        {
            s=s+a[i];
        }
        cout<<s;
    }

}


Measured memory_bytes: 3608
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		if((char)s.charAt(2)==(char)s.charAt(3) && (char)s.charAt(4)==(char)s.charAt(5)) {
			System.out.println("Yes");
		}else {
			System.out.println("No");
		}
	}
}


Measured memory_bytes: 23508
#include <iostream>

#define ll long long int
using namespace std;

int main() {
  ll n, k;
  cin >> n >> k;
  if (k % 2) {
    ll i = k;
    ll count = 0;
    while (i <= n) {
      count++;
      i += k;
    }
    ll ans = count + count * (count - 1) * (count - 2) + 3 * count * (count - 1);
    cout << ans;
  }
  else {
    ll i = k;
    ll count = 0;
    while (i <= n) {
      count++;
      i += k;
    }
    ll ans = count + count * (count - 1) * (count - 2) + 3 * count * (count - 1);
    i = k / 2;
    count = 0;
    while (i <= n) {
      count++;
      i += k;
    }
    ans += count + count * (count - 1) * (count - 2) + 3 * count * (count - 1);
    cout << ans;
  }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
/**
******************* Author:Bisnu sarkar ****************************
**/
#define ull            unsigned long long
#define ll             long long
#define pii            pair<int,int>
#define sit            set<int> :: iterator
#define vrit           vector<int> :: reverse iterator
#define ff             first
#define ss             second
#define endl           '\n';
#define sz(s)          (int)s.size()
#define all(s)         s.begin(),s.end()
#define IO             ios_base::sync_with_stdio(false),cin.tie(NULL);  
#define what_is(x)     cerr << #x << " is " << x << endl;
///*....Debugger....*///
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {cout << endl;}
template<typename T, typename... Args> void err(istream_iterator<string> it, T a, Args... args) {
  cerr << *it << " = " << a << ", ";
  err(++it, args...);
}
///*....Input....*///
template <typename T> inline void Int(T &n) {
  n = 0; int f = 1; register int ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) n = (n << 3) + (n << 1) + ch - '0';
  n = n * f;
}
 
template <typename T, typename TT> inline void Int(T &n, TT &m) { Int(n); Int(m); }
template <typename T, typename TT, typename TTT> inline void Int(T &n, TT &m, TTT &l) { Int(n, m); Int(l);}
double ind(){double x; scanf("%lf",&x);return x;}

///*....Bitmask....*///
int set_1(int n,int pos){return n = (n | (1<<pos));}
int reset_0(int n,int pos){return n= n & ~(1<<pos);}
bool check_bit(int n,int pos){return n = n & (1<<pos);}

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

///*....Constraints....*///
const int N = (int) 5e5 + 5;
const int M = (int) 1e9 + 7;
const double pi=2* acos(0.0);
const double eps=1e-9;

struct query
{
	int l,r,id;
}q[N];
int a[N],k=1000,l=1,r=0;

bool compare(query &a,query &b){
	int b_a = a.l/k;
	int b_b = b.l/k;
	if(b_a==b_b)return a.r<b.r;

	return b_a<b_b;
}
int cnt[N],ans[N];
int res=0;
void add(int x){
	cnt[a[x]]++;
	if(cnt[a[x]]==1)++res;
}
void remove(int x){
	cnt[a[x]]--;
	if(cnt[a[x]]==0)--res;
}

int main()
{
    int t=1,te=0;
    //Int(t);
    while(t--){
		int n;
		Int(n);
        int Q;
		Int(Q);
		for(int i=1;i<=n;++i)Int(a[i]);

		
		for(int i=1;i<=Q;++i){
			Int(q[i].l,q[i].r);
			q[i].id=i;
		}
		sort(q+1,q+Q+1,compare);

		for(int i=1;i<=Q;++i){
			while(l > q[i].l)add(--l);
			while(r < q[i].r)add(++r);
			while(l < q[i].l)remove(l++);
			while(r > q[i].r)remove(r--);
			ans[q[i].id]=res;
		}

		for(int i=1;i<=Q;++i){
			printf("%d\n", ans[i]);
		}

        //printf("Case %d: ",++te);
    }
    return 0;
}



Measured memory_bytes: 15488
#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>

#define ll long long
#define rr register

#define inf 1e9
#define MAXN 1000010

using namespace std;

inline int read() {
	int s = 0, f = 0;
	char ch = getchar();
	while (!isdigit(ch)) f |= ch == '-', ch = getchar();
	while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
	return f ? -s : s;
}

void print(int x) {
	if (x < 0) putchar('-'), x = -x;
	if (x > 9) print(x / 10);
	putchar(x % 10 + 48);
}

int n, m, ans;

int a[MAXN], f[MAXN];

signed main() {
	n = read();
	for (rr int i = 1; i <= n; i++) a[i] = read();
	for (rr int i = 1; i <= n; i++) f[a[i]]++;
	for (rr int i = 1000000; i >= 0; i--)
		if (f[i]) 
			for (rr int j = i + i; j <= 1000000; j += i)
				f[j] += f[i];
	for (rr int i = 1; i <= n; i++) ans += (f[a[i]] == 1);
	cout << ans << "\n";
}

Measured memory_bytes: 8308
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <utility>
#include <iomanip>
using namespace std;
typedef long long ll;

const ll MOD = 1e9+7;

int main()
{
	int n;
	string s;
	string ans;
	cin>>n;
	cin>>s;
	for(int i=0;i<s.size();i++)
		ans+=((s[i]-'A')+n)%26+'A';
	cout<<ans<<endl;
	return 0;
}

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

bool M[100][100];
int n,m,num;
int color[100], d[100], f[100], tt,mark[100];

int next(int u) {
	for (int i = mark[u]; i < n; i++) {
		if (M[u][i] != 0) {
			mark[u] = i + 1;
			return i;
		}
	}
	return -1;
}

void dfs_visit(int r) {
	stack<int> s;
	s.push(r);
	d[r] = ++tt;
	color[r] = 1;

	while (!s.empty()){
		int v = s.top();
		int k = next(v);
		if (k != -1) {
			if (color[k] == 0) {
				color[k] = 1;
				d[k] = ++tt;
				s.push(k);
			}
		}
		else {
			color[v] = 2;
			f[v] = ++tt;
			s.pop();
		}
	}




}




int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> m;
		cin >> m;
		for (int v = 0; v < m; v++) {
			cin >> num;
			M[i - 1][num-1] = 1;
		}
	}
	for (int i = 0; i < n; i++) {
		if (color[i] == 0) {
			dfs_visit(i);
		}
	}
	for (int i = 0; i < n; i++) {
		cout << i + 1 << " " << d[i] << " " << f[i]<< endl;
	}
	
}


Measured memory_bytes: 3112
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <memory>
#include <complex>
#include <numeric>
#include <cstdio>
#include <iomanip>

#define REP(i,m,n) for(int i=int(m);i<int(n);i++)
#define RREP(i,m,n) for(int i=int(n)-1;i>=int(m);--i)
#define EACH(i,c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

#ifdef LOCAL
#define DEBUG(s) cout << (s) << endl
#define dump(x)  cerr << #x << " = " << (x) << endl
#define BR cout << endl;
#else
#define DEBUG(s) do{}while(0)
#define dump(x) do{}while(0)
#define BR 
#endif
using namespace std;

using UI = unsigned int;
using UL = unsigned long;
using LL = long long int;
using ULL = unsigned long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VS = vector<string>;
using PII = pair<int,int>;
using VP = vector<PII>;

//struct edge {int from, to, cost;};

constexpr double EPS = 1e-10;
//constexpr double PI  = acos(-1.0);
//constexpr int INF = INT_MAX;
constexpr int MOD = 1'000'000'007;

template<class T> inline T sqr(T x) {return x*x;}

void solve() {
    int n;
    cin >> n;
    vector<double> p(n);
    REP(i,0,n) cin >> p[i];
    vector<vector<double>> dp(n,vector<double>(n+1));
    dp[0][0] = 1 - p[0];
    dp[0][1] = p[0];
    REP(i,1,n) {
        dp[i][0] = dp[i-1][0] * (1 - p[i]);
        REP(j,1,i+2) {
            dp[i][j] = dp[i-1][j-1] * p[i] + dp[i-1][j] * (1 - p[i]);
        }
    }
    double sum = 0;
    REP(i,(n+1)/2,n+1) sum += dp[n-1][i];
    //cout << sum << endl;
    printf("%.12lf\n", sum);
}

int main() {
    solve();
    
    return 0;
}

Measured memory_bytes: 70656
#include <iostream>

int main()
{
    std::string s;
    std::cin >> s;

    int p = 0;
    for (char c : s) {
        if (p == 0 && c == 'C') {
            p = 1;
        } else if (p == 1 && c == 'F') {
            p = 2;
        }
    }

    std::cout << (p == 2 ? "Yes" : "No") << std::endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(int argc, char * argv[]) {
	int N;
	cin >> N;

	vector<int> cards;
	for (int i = 0; i < N; i++) {
		int n;
		cin >> n;
		cards.push_back(n);
	}

	sort(cards.begin(), cards.end(), greater<int>());

	int sign = 1;
	int pt = 0;
	for (int i = 0; i < cards.size(); i++, sign *= -1) {
		pt += sign * cards[i];
	}

	cout << pt << endl;

	return 0;
}

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

int main(){
  
  int H,W,h,w;
  
  cin >> H >> W >> h >> w;
  
  int white;
  
  white = H*W - h*W -(H-h)*w;
  
  cout << white << endl;
  
  return 0;
  
  
}

Measured memory_bytes: 256
#include<iostream>
 #include<string>
using namespace std;
int main(){
 string s;
 cin>>s;
 int zbir=0;
 for(int i=0;i<s.size();i++){
     int x=s[i]-'0';
     zbir=(zbir+x)%9;
 }
 zbir=zbir%9;
 if(zbir==0){
     cout<<"Yes";
 }else{
     cout<<"No";
}
}

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

#include <algorithm>

int main() {
	int h[10];
	for (int i=0; i<10; i++) cin >> h[i];
	sort(h, h+10);
	for (int i=0; i<3; i++) cout << h[9-i] << endl;
	return 0;
}

Measured memory_bytes: 1176
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <map>
#include <queue>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using p = pair<int, int>;
int main()
{
	int k, t, tmp;
	cin >> k >> t;
	vector<int> a(t);
	int old = -1, next = 0;
	int m = 0;
	rep(i, t) cin >> a[i];
	sort(a.rbegin(), a.rend());
	int ans = 0;
	rep(i, k) {
		if (old == next)	ans++;
		a[next]--;
		old = next;
		m = 0;
		rep(j, t) {
			if (old == j)	continue;
			if (a[j] != 0) {
				if (m < a[j]) {
					next = j;
					m = a[j];
				}
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3600
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

const unsigned long long MOD = 1e9+7;

int main()
{
	int n;
	cin >> n;
	string str;
	cin >> str;
	vector<int> v(2*n);

	if(str[0] == 'B')
		v[0] = 0;
	else
		v[0] = 1;

	for(int i=1;i<2*n;i++){
		if(str[i] != str[i-1]){
			v[i] = v[i-1];
		}else{
			v[i] = 1 - v[i-1];
		}
	}

	unsigned long long ans = 1;
	unsigned long long cnt_0 = 0;
	for(int i=0;i<2*n;i++){
		if(v[i] == 0){
			cnt_0++;
		}else{
			ans = ans*cnt_0 % MOD;
			cnt_0--;
		}
	}

	for(unsigned long long i=1;i<=n;i++){
		ans = (ans * i) % MOD;
	}

	if(cnt_0 != 0)
		cout << 0 << endl;
	else
		cout << ans << endl;
}

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

using namespace std;

int main() {
  long long a, b, x; cin >> a >> b >> x;
  long long ans = 0;
  if(a == 0) {
    a = 1;
    ans++;
  }

  ans += b/x - (a-1)/x;

  cout << ans << endl;
}


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

int main(){
  ll N;
  cin >> N;
  int K;
  cin >> K;
  int digit = 0;
  int res = 1;
  while(res <= N){
    digit++;
    res *= K;
  }
  cout << digit << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define optimize ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0) ;
#define ll long long
#define ld long double
#define lint __int128
#define vi vector<int>
#define pb push_back
#define lp(i,a,b) for(int i = a ; i <= b ; i ++)
#define rlp(i,a,b) for(int i = b ; i >= a ; i --)
#define a_sort(v) sort(v.begin(), v.end())
#define d_sort(v) sort(v.rbegin(), v.rend())
#define pii pair<int,int>
#define pi 3.14159265358979323846264338327950
using namespace std ;
// #define debug

const int MOD = 1E9 + 7 ;
const int N = 1E5 ;

int main() {
    #ifdef debug
    freopen("input.txt", "r", stdin) ;
    freopen("output.txt", "w", stdout) ;
    #endif // debug
    optimize

    ld a , b , h , m ; cin >> a >> b >> h >> m ;
    ld angle = 2 * pi * (h / 12.0 + m / 720.0 - m / 60.0) ;
    ld ans = sqrtl(a * a + b * b - 2 * a * b * cosl(angle)) ;
    cout << fixed << setprecision(20) << ans << endl ;
}


Measured memory_bytes: 4144
import std.stdio;
import std.algorithm;
import std.string;
import std.functional;
import std.array;
import std.conv;
import std.math;
import std.typecons;
import std.regex;
import std.range;

void main(){

    while(true){
	int n = readln().chomp().to!int;
	if(n==0) break;
	int fi;
	int[] pl;
	for(int i=0;i<n;i++) pl ~= 0;
	string c = readln().chomp();
	for(int i=0;i<100;i++){
	    if(c[i] == 'M') pl[i%n]++;
	    else if(c[i] == 'S'){
		pl[i%n]++;
		fi += pl[i%n];
		pl[i%n] = 0;
	    }else if(c[i] == 'L'){
		pl[i%n] += 1 + fi;
		fi = 0;
	    }
	}
	pl.sort();
	write(pl[0]);
	for(int i=1;i<n;i++){
	    writef(" %d",pl[i]);
	}
	writef(" %d\n",fi);
    }

}

Measured memory_bytes: 2484
N,C = map(int,input().split())
D = [list(map(int,input().split())) for i in range(C)]
E = [list(map(int,input().split())) for i in range(N)]

from collections import Counter
ctrs = [Counter() for _ in range(3)]
for i,row in enumerate(E):
    for j,c in enumerate(row):
        ctrs[(i+j)%3][c] += 1

ans = float('inf')
from itertools import permutations
for ptn in permutations(range(1,C+1), 3):
    t = 0
    for p,c in zip(ptn,ctrs):
        for k,v in c.items():
            t += D[k-1][p-1] * v
    ans = min(ans, t)
print(ans)

Measured memory_bytes: 11872
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <ctime>
#include <climits>
#include <cfloat>
#include <cstdint>
#include <cstddef>
#include <cinttypes>
#include <memory>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <array>
#include <valarray>
#include <string>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stack>
#include <bitset>
#include <queue>
#include <complex>
#include <tuple>
#include <utility>
#include <functional>
#include <algorithm>
#include <numeric>

using namespace std;

const double EPS = 1e-10;
const int64_t INF = 1e9;

const int MAX_N = 100000;
const int64_t MOD = 1000000007;

int n;
int c[MAX_N];

void solve()
{
	bool f = true;
	n--;
	int a = 0;
	for (int i = 0; i <= n; ++i) {
		if (i % 2 == 1 && c[n-i] > 0) { f = false; }
		if (i % 2 == 0 && i != n && c[n-i] != 2) { f = false; }
		if (c[n-i] == 2) ++a;
	}
	if (n % 2 == 0 && c[0] != 1) { f = false; }

	int64_t ans = 0;
	if (f) {
		ans = 1;
		while (a > 0) {
			ans = (ans * 2) % MOD;
			--a;
		}
	}

	printf("%" PRId64 "\n", ans);
}

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

	return 0;
}



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

typedef long long ll;
#define rep(i,n) for( ll (i)=0; (i)<(n); ++(i) )
#define rpi(i,n) for( int (i)=0; (i)<(n); ++(i) )
#define rpv(d) for(auto& v:d)
#if __cplusplus < 201703L
  std::ostream& co_(){ return std::cout << std::endl; }
  std::istream& cn_(){ return std::cin; }
  template<class Head, class... Args>
  std::ostream& co_( Head&& head, Args&&... args ){ std::cout << head; return co_(std::forward<Args>(args)...); }
  template<class Head, class... Args>
  std::istream& cn_( Head&& head, Args&&... args ){ std::cin >> head; return cn_(std::forward<Args>(args)...); }
#else
  template<class... Args>
  std::ostream& co_( Args... args ){ return std::cout << ... << args << std::endl; }
  template<class... Args>
  std::istream& cn_( Args... args ){ return std::cin >> ... >> args; }
#endif
#define co(...) co_(__VA_ARGS__);
#define cn(...) cn_(__VA_ARGS__);
#define all(x) (x).begin(), (x).end()
#define rgt(x,i) (x).begin(), (x).begin()+(i)

int main(){
  int n;cn(n)
  vector<vector<int>> d(n,vector<int>(n,-1));
  rpv(d){
    int t;cn(t);
    rep(i,t){
      int x,y;cn(x,y)
      v[x-1]=y;
    }
  }
  int ans = 0;
  for( int i=1; i<(1<<n); ++i ){
    bool sw = true;
    int mn = 0;
    rep(j,n){
      if ( (i>>j)&0x01 ){
        ++mn;
        rep( k, n ){
          //if (j==k)continue;
          if ( (( ((i>>k)&0x01) == 0 )&&( d[j][k]==1 )) || ( ((i>>k)&0x01) )&&( d[j][k]==0 ) ){
            sw = false;
            break;
          }
        }
      }
      if(!sw)break;
    }
    if(sw){
      ans=max(ans,mn);
    }
  }
  co(ans)
}

Measured memory_bytes: 256
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cassert>
using namespace std;
using ll = long long;

namespace io {
#define File(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
  const int SIZE = (1 << 21) + 1;
  char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1;
  inline char getc () {return (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++);}
  inline void flush () {fwrite (obuf, 1, oS - obuf, stdout); oS = obuf;}
  inline void putc (char x) {*oS ++ = x; if (oS == oT) flush ();}
  template<class T>
  inline void read(T &x) {
    char ch; int f = 1;
    x = 0;
    while(isspace(ch = getc()));
    if(ch == '-') ch = getc(), f = -1;
    do x = x * 10 + ch - '0'; while(isdigit(ch = getc()));
    x *= f;
  }
  template<class T, class ...Args>
  inline void read(T &x, Args&... args) {read(x); read(args...);}
  template<class T>
  inline void write(T x) {
    static char stk[128];
    int top = 0;
    if(x == 0) {putc('0'); return;}
    if(x < 0) putc('-'), x = -x;
    while(x) stk[top++] = x % 10, x /= 10;
    while(top) putc(stk[--top] + '0');
  }
  template<class T, class ...Args>
  inline void write(T x, Args... args) {write(x); putc(' '); write(args...);}
  inline void space() {putc(' ');}
  inline void endl() {putc('\n');}
  struct _flush {~_flush() {flush();}} __flush;
};
using io::read; using io::write; using io::flush; using io::space; using io::endl; using io::getc; using io::putc;

const int N = 200005;
int lgn;
int n, k;

struct max_good_set {
  int a[N], nxt[N][20];
  ll sum[N][20];
  void init() {
    int p = 0;
    for (int i = 0; i < n; ++i) {
      while (abs(a[p] - a[i]) < k && p < n) ++p;
      nxt[i][0] = p;
      sum[i][0] = i;
    }
    for (int i = 0; i <= lgn; ++i)
      nxt[n][i] = n, sum[n][i] = 0;
    for (int j = 1; j <= lgn; ++j)
      for (int i = 0; i < n; ++i) {
        nxt[i][j] = nxt[nxt[i][j - 1]][j - 1];
        sum[i][j] = sum[i][j - 1] + sum[nxt[i][j - 1]][j - 1];
      }
  }
  pair<ll, int> query(int l, int r) {
    int p = l, c = 1;
    ll s = 0;
    for (int i = lgn; i >= 0; --i)
      if (nxt[p][i] <= r) {
        s += sum[p][i];
        c += 1 << i;
        p = nxt[p][i];
      }
    assert(p <= r);
    return {s + p, c};
  }
}a, b;

int main() {
  read(n, k);
  lgn = log2(n);
  for (int i = 0; i < n; ++i)
    read(a.a[i]);
  reverse_copy(a.a, a.a + n, b.a);
  a.init(); b.init();
  int q;
  read(q);
  while (q--) {
    int l, r;
    read(l, r);
    --l; --r;
    auto A = a.query(l, r), B = b.query(n - 1 - r, n - 1 - l);
    B.first = 1LL * (n - 1) * B.second - B.first;
    write(B.first - A.first + A.second), endl();
  }
  return 0;
}

Measured memory_bytes: 101692