akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <algorithm>
#include <cassert>

using namespace std;

void debug_print_ints(int* as, int n){
  printf("%d\n", n);
  for(int i=0; i < n; i++){
    printf("%d, ", as[i]);
  }
  printf("\n");
}


int main(){
  int n;
  scanf("%d", &n);
  char dirs[300001];
  int sum_w[300001];
  int sum = 0;
  char dummy;
  scanf("%c", &dummy);  
  for(int i=0; i < n; i++){
    char temp;
    scanf("%c", &temp);
    dirs[i] = temp;
    if(temp == 'W'){
      sum++;
    }else if(temp == 'E'){
    }else{
      assert(0);
    }
    sum_w[i] = sum;
  }
  // debug_print_ints(sum_w, n);

  int res = n;
  for(int i=0; i < n; i++){
    int temp = 0;
    int right_ws = sum_w[n-1] - sum_w[i];
    int left_ws = (i == 0 ? 0 : sum_w[i-1]);
    int right = (i == n-1 ? 0 : (n - 1) - i);
    int right_es = right - right_ws;
    int left = i;
    int left_es = left - left_ws;
    // printf("debug! rws:%d, lws:%d, res:%d, les:%d\n", right_ws, left_ws, right_es, left_es);
    res = min(res, left_ws + right_es);
  }
  printf("%d\n", res);
  return 0;
}


Measured memory_bytes: 1280
#include<cstdio>
#include<vector>
using namespace std;
vector<int> v[210000];
int main(){
    int n,m,x,y;
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= m; i ++){
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    int flag = 0;
    int k = v[1].size();
    for(int i = 0; i < k; i ++){
        int tem = v[1][i];
        int k2 = v[tem].size();
        for(int j = 0; j < k2; j ++){
            if(v[tem][j] == n)
                flag = 1;
        }
    }
    if(flag)
        printf("POSSIBLE");
    else
        printf("IMPOSSIBLE");
    return 0;
}

Measured memory_bytes: 12144
from collections import Counter
n = int(input())
c = list(Counter(ai for ai in map(int, input().split())).values())
c.sort()

clen = len(c)

s = [0] * (clen + 1)
for i in range(clen):
    s[i + 1] = s[i] + c[i]

for i in range(1, n + 1):
    rest = clen - i
    if rest < 0:
        print(0)
        continue
    l1 = 0
    r1 = s[clen] // i + 2
    while r1 - l1 > 1:
        c1 = (l1 + r1) // 2

        l2 = -1
        r2 = clen
        while r2 - l2 > 1:
            c2 = (r2 + l2) // 2
            if c[c2] < c1:
                l2 = c2
            else:
                r2 = c2

        if (r2 - rest) * c1 <= s[r2]:
            l1 = c1
        else:
            r1 = c1
    print(l1)


Measured memory_bytes: 120120
#include<iostream>
#include<string>
#include<math.h>
#include<algorithm>

using namespace std;

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define IN cin >>
#define OUT cout <<


int main() {
	int N;
	IN N;
	int p[11]
		; REP(i, N)IN  p[i];
	sort(p, p + N);
	int ans;
	REP(i, N){
		if (i == N - 1)ans += p[i] / 2;
		if(i != N - 1)ans += p[i];


	}

	cout << ans;
	
	return 0;
}


Measured memory_bytes: 256
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        char[] s = br.readLine().toCharArray();
        char[] p = br.readLine().toCharArray();
        boolean result = false;
        
        main:
        for(int i = 0; i < s.length; i++){
            for(int j = 0; j < p.length; j++){
                int index = i+j;
                if(index >= s.length) index -= s.length;
                if(!(s[index] == p[j])) continue main;
            }
            result = true;
        }

        if(result)  System.out.println("Yes");
        else System.out.println("No");

    }
}

Measured memory_bytes: 24296
#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <functional>
using namespace std;
using Int = long long;
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,f,t) for(int i=f;i<t;i++)
void split2(Int H, Int W, Int &S1, Int &S2)
{
    Int s1, s2, s3, s4;
    s1 = (H/2) * W;
    s2 = (H - H/2) * W;
    s3 = H * (W / 2);
    s4 = H * (W - W / 2);
    if (abs(s1 - s2) < abs(s3 - s4)) {
        S1 = s1, S2 = s2;
    } else {
        S1 = s3, S2 = s4;
    }
}
int main()
{
    Int H, W; cin >> H >> W;
    Int res = numeric_limits<Int>::max();
    Int s1, s2, s3;
    for (int i = 1; i < H; i++) {
        s1 = i * W;
        split2(H - i, W, s2, s3);
        res = min(res, max({s1, s2, s3}) - min({s1, s2, s3}));
    }
    for (int i = 1; i < W; i++) {
        s1 = H * i;
        split2(H, W - i, s2, s3);
        res = min(res, max({s1, s2, s3}) - min({s1, s2, s3}));
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<sstream>
#include<vector>
#include<algorithm>
#include<string>
#include<stdexcept>
#include<stdio.h>
#include<queue>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
//Sの1文字目からi文字目までに出現するACの数の数列をかんがえる！
 int main(){
   int n,q; string s;
   cin >> n >> q >> s;    
   vector<int> vec(n+1,0) ;  
   for(int i=1;i<s.size();i++){
     if(s[i-1]=='A' && s[i]=='C') vec[i]=vec[i-1]+1;
     else vec[i]=vec[i-1];
      }
      for(int i=0;i<q;i++){
     int l,r;
     cin >> l >> r;
     cout << vec[r-1]-vec[l-1] <<endl;
   }
   return 0;
 }

Measured memory_bytes: 1408
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
use std::io::Read;
#[allow(dead_code)]
fn getline() -> String {
    let mut ret = String::new();
    std::io::stdin().read_line(&mut ret).ok().unwrap();
    ret
}
fn get_word() -> String {
    let mut stdin = std::io::stdin();
    let mut u8b: [u8; 1] = [0];
    loop {
        let mut buf: Vec<u8> = Vec::with_capacity(16);
        loop {
            let res = stdin.read(&mut u8b);
            if res.unwrap_or(0) == 0 || u8b[0] <= b' ' {
                break;
            } else {
                buf.push(u8b[0]);
            }
        }
        if buf.len() >= 1 {
            let ret = String::from_utf8(buf).unwrap();
            return ret;
        }
    }
}

#[allow(dead_code)]
fn get<T: std::str::FromStr>() -> T { get_word().parse().ok().unwrap() }

fn solve() {
    let a: Vec<i32> = (0..3).map(|_| get()).collect();
    println!("{}", a.iter().max().unwrap() - a.iter().min().unwrap());
}

fn main() {
    // In order to avoid potential stack overflow, spawn a new thread.
    let stack_size = 104_857_600; // 100 MB
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(|| solve()).unwrap().join().unwrap();
}


Measured memory_bytes: 8572
import math

def isPrime(n):
  if n == 2:
    return True
  if n % 2 == 0:
    return False
  
  # nの平方根まで計算する
  m = math.floor(math.sqrt(n)) + 1
  for p in range(3, m, 2):
      if n % p == 0:
        return False
  return True

if __name__ == "__main__":
  x = int(input())
  flag = False
  while flag == False:
    if isPrime(x) == True:
      flag = True
      print(x)
    else:
      x = x + 1



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

#ifdef __LOCAL
    #define DBG(X) cout << #X << " = " << (X) << endl;
    #define SAY(X) cout << (X) << endl;
#else
    #define DBG(X)
    #define SAY(X)
#endif

#ifdef __LOCAL
    #include <filesystem>
    namespace fs = std::filesystem;
#endif

using namespace std;

using ll = long long int;
inline void fast_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); };
template<typename T, typename S> inline ostream& operator<<(ostream& os, const pair<T, S> p) { cout << "[" << p.first << ";" << p.second << "]"; return os; }
template<typename T, typename S> inline ostream& operator<<(ostream& os, const map<T, S> p) { for (auto el : p) cout << "[" << el.first << ":" << el.second << "]"; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const vector<T>& v) { for (auto el : v) cout << el << "\n"; return os; }

string S;

int input(){
  #ifdef __LOCAL
    fs::path p = __FILE__;
    fs::path input,output;
    input = output = p.parent_path();
    input += string("/input/") + string(p.stem()) + string(".txt");
    output += string("/output/") + string(p.stem()) + string(".txt");
    freopen(input.c_str(), "r", stdin);
    freopen(output.c_str(), "w", stdout);
  #endif
  fast_io();
  cin >> S;
  return 0;
}


int solve(){
  string ans;
  int n=S.length();
  bool X = S[0]==S[n-1];
  if(X^(n%2==0)) ans = "Second";
  else ans="First";
  cout << ans << endl;  
  return 0;
}

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


Measured memory_bytes: 512
import java.util.*;

class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int A = sc.nextInt();
        int B = sc.nextInt();

        int C = A * N;
        if(C >= B){
            System.out.println(B);
        }else{
            System.out.println(C);
        }
    }
}

Measured memory_bytes: 21716
package main

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

var T [][]int
var dist []int

func main() {
	N := nextInt()
	u := nextInt() - 1
	v := nextInt() - 1
	T = make([][]int, N)
	dist = make([]int, N)

	for i := 0; i < N-1; i++ {
		A := nextInt() - 1
		B := nextInt() - 1
		T[A] = append(T[A], B)
		T[B] = append(T[B], A)
	}

	// 高橋くんを根として距離を出す
	dist[u] = 1
	fillDist(u)

	// 青木くんは最短を目指すので、とりあえず近づく
	var vk int
	var k int
	if (dist[v]-dist[u])%2 == 1 {
		k = (dist[v] - dist[u]) / 2
		vk = findUpper(v, k)
	} else {
		k = (dist[v] - dist[u] - 1) / 2
		vk = findUpper(v, k)
	}
	uk := findUpper(v, k+1)

	// ukから見て一番遠いところまでの距離。ただし、vkは通れない
	l := dfs(uk, vk)
	fmt.Println(k + l - 1)
}

func dfs(r, ignore int) int {
	m := 0
	for i := 0; i < len(T[r]); i++ {
		if T[r][i] == ignore {
			continue
		}
		m = max(m, dfs(T[r][i], r))
	}
	return m + 1
}

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

func findUpper(r, d int) int {
	if d == 0 {
		return r
	}

	for i := 0; i < len(T[r]); i++ {
		if dist[T[r][i]] < dist[r] {
			return findUpper(T[r][i], d-1)
		}
	}
	return -1
}

func fillDist(r int) {
	for i := 0; i < len(T[r]); i++ {
		n := T[r][i]
		if dist[n] == 0 {
			dist[T[r][i]] = dist[r] + 1
			fillDist(n)
		}
	}
}

var stdin = initStdin()

func initStdin() *bufio.Scanner {
	bufsize := 1 * 1024 * 1024 // 1 MB
	var stdin = bufio.NewScanner(os.Stdin)
	stdin.Buffer(make([]byte, bufsize), bufsize)
	stdin.Split(bufio.ScanWords)
	return stdin
}

func nextString() string {
	stdin.Scan()
	return stdin.Text()
}

func nextBytes() []byte {
	stdin.Scan()
	return stdin.Bytes()
}

func nextInt() int {
	i, _ := strconv.Atoi(nextString())
	return i
}

func nextInt64() int64 {
	i, _ := strconv.ParseInt(nextString(), 10, 64)
	return i
}


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

int main() {
    int n;
    cin >> n;
    vector<int> A(n);
    for(int i=0; i<n; ++i) cin >> A[i];

    int diff = 1;
    for(int i=0; i<n; ++i) {
        if(A[i] % 2 == 0) diff *= 2;
        else diff *= 1;
    }
    
    int ans = 1;
    for(int i=0; i<n; ++i) ans *= 3;
    ans -= diff;
    
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        if (N < 1200) {
            System.out.println("ABC");
        } else if (N < 2800) {
            System.out.println("ARC");
        } else {
            System.out.println("AGC");
        }
    }
}


Measured memory_bytes: 23380
public class Main{
  public void run(java.io.InputStream in, java.io.PrintStream out){
    java.util.Scanner sc = new java.util.Scanner(in);
    int a, b, c, h, m, s, i, t;

    for(i = 3;i-- > 0;){
      a = sc.nextInt(); b = sc.nextInt(); c = sc.nextInt();
      h = sc.nextInt(); m = sc.nextInt(); s = sc.nextInt();
      t = (h - a) * 3600 + (m - b) * 60 + (s - c);
      out.printf("%d %d %d%n", t / 3600, (t / 60) % 60, t % 60);
    }

    sc.close();
  }
  public static void main(String[] args){
    (new Main()).run(System.in, System.out);
  }
}

Measured memory_bytes: 17192
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <unordered_map>

using namespace std;
using ll = long long;

void _cin(){} template <class Head, class... Tail> void _cin(Head&& head, Tail&&... tail){ cin >> head; _cin(forward<Tail>(tail)...); }
void _cout(){ cout << "\n"; } template <class Head, class... Tail> void _cout(Head&& head, Tail&&... tail){ cout << head; _cout(forward<Tail>(tail)...); }
int gcd(int a, int b){ return (b == 0) ? a : gcd(b, a % b); }

#define Sq(x) (x)*(x)
#define For(i, n) for(int i = 0; i < (n); i ++)
#define Rep(n) For(_, n)
#define Range(c) c.begin(), c.end()
#define RevRange(c) c.rbegin(), c.rend()
#define Contains(c, x) (find(Range(c), x) != c.end())
#define Search(rb, re, x) distance(rb, find(rb, re, x))
#define Sort(a) sort(Range(a))
#define DeSort(a) sort(RevRange(a))
#define Reverse(c) reverse(Range(c))
#define Unique(a) a.erase(unique(Range(a)), a.end())
#define Vec2(T, n, m, xs) vector<vector<T>> xs(n, vector<T>(m))
#define Sum(a) accumulate(Range(a), 0)
#define Cusum(T, xs, sxs) vector<T> sxs(xs.size()+1); For(i, (int)xs.size()) sxs[i+1] = sxs[i] + xs[i]
#define Cin(T, ...) T __VA_ARGS__; _cin(__VA_ARGS__)
#define Cins(T, n, xs) vector<T> xs(n); For(i, n) cin >> xs[i]
#define Cins2(T, n, xs, ys) vector<T> xs(n), ys(n); For(i, n) cin >> xs[i] >> ys[i]
#define Cins3(T, n, xs, ys, zs) vector<T> xs(n), ys(n), zs(n); For(i, n) cin >> xs[i] >> ys[i] >> zs[i]
#define Cinss(T, n, m, xs) Vec2(T, n, m, xs); For(i, n) For(j, m) cin >> xs[i][j]
#define Cinm(T, n, map) unordered_map<T, int> map; Rep(n){ Cin(T, x); map[x] ++; }
#define Cout(...) _cout(__VA_ARGS__)
#define Couts(xs) for(const auto &e : xs) cout << e << " "; cout << "\n"
#define Coutyn(cond) Cout((cond) ? "yes" : "no")
#define CoutYn(cond) Cout((cond) ? "Yes" : "No")
#define CoutYN(cond) Cout((cond) ? "YES" : "NO")

// constexpr int MOD = 1e9+7;

int main(void){
  	Cin(int, n, k);
  	vector<int> p(30);
    for(int i = 1; i <= n; i ++){
        int q = 0, j = i;
        while(j < k) j *= 2, q ++;
        p[q] ++;
    }
    
    double ans = 0;
    for(int i = 29; i >= 0; i --){
        ans = ans/2 + p[i];
    }
    printf("%.20f\n", ans / n);
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define LL long long
 
int main()
{
    int a,b,m;
    cin>>a>>b>>m;
   
    int mia=1e5,mib=1e5;
    
    vector<int>va(a),vb(b);
    for(auto &x:va){
        cin>>x;
        mia=min(mia,x);
    }
    
    for(auto &x:vb){
        cin>>x;
        mib=min(mib,x);
    }

    vector<LL>v;
   
    v.push_back(mia+mib);
    for(int i=0;i<m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        LL s;
        s=(va[x-1]+vb[y-1])-z;
        v.push_back(s);
    }
    
    LL rm=1e10;
    for(auto x:v)rm=min(rm,x);
    cout<<rm;
    return 0; 
}

Measured memory_bytes: 2168
//Bismillahir Rahmanir Rahim
#include <bits/stdc++.h>
using namespace std;

typedef long long              ll;
typedef long double            ld;
typedef pair<int, int>         pi;
typedef vector<int>            vi;
typedef vector<pair<int, int>> vpi;

#define pb          push_back
#define pf          push_front
#define all(x)      begin(x), end(x)
#define sz(x)       (int)(x).size()
#define ff          first
#define ss          second
#define mp          make_pair
#define lb          lower_bound
#define ub          upper_bound
#define Tcase()     int t; cin >> t; while(t--)
#define Forn(i, x)  for(int i = 0; i < (x); i++)

const int MOD = 1e9 + 7; // 998244353;
const int MX  = 2e5 + 5;
const ll  INF = 1e18;
const ld  PI  = acos((ld) -1);

void setIO(string name = "") {
    ios_base::sync_with_stdio(0); cin.tie(0);
    if(sz(name)){
        freopen((name+".in").c_str(), "r", stdin);
        freopen((name+".out").c_str(), "w", stdout);
    }
}

int main(){

    setIO();

    ll n;
    cin >> n;

    ll Ans = 0;

    for(ll i = 1; i < n; i++){

        ll p = (n + i - 1LL) / i - 1;

        if(p > 0) Ans += p;
    }

    cout << Ans;
}


Measured memory_bytes: 3648
/**
       ������������    ������������
		Author : Avi J Patel
		University : DA-IICT
       ������������    ������������
**/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair 
#define mt make_tuple
#define N 100000
#define ff first
#define ss second
#define si size()
#define MOD 1000000007
#define large 10000000000000001

#define For(i,m,n) for(long long i=m;i<n;i++)
#define st(x) sort(x.begin(),x.end())
#define re(x,i) reverse(x.begin()+i,x.end())
#define FAST ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);srand(time(NULL));

bool sortbysec(const pair<int,int> &a, 
              const pair<int,int> &b) 
{ 
    return (a.second < b.second); 
} 
int main()
{
	string s;
	cin>>s;
	sort(s.begin(),s.end());
	if(s[0]==s[1] && s[2]==s[3] && s[2]!=s[1])
	{
		cout<<"Yes";
	}
	else
	{
		cout<<"No";
	}
	return 0;
}








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

using namespace std;

int main() {
	int N;
	int L;
	cin >> N;
	cin >> L;

	vector<string> inputs(N);
	for (int i = 0; i < N; i++) {
		cin >> inputs[i];
	}

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

	string output = "";
	for (int i = 0; i < N; i++) {
		output += inputs[i];
	}
	cout << output << endl;
}

Measured memory_bytes: 384
#include <stdio.h>
int main() {
    char a[101], b[101];
    int n, i, j, cnt=0;
    scanf("%d", &n);
    scanf("%s", a);
    scanf("%s", b);
    for(i=0, j=0;i<n;i++) {
        if(a[i]==b[j]) j++;
        else {
            j=0;
            if(a[i]==b[j]) j++;
        }
    }
    cnt=n+(n-j);
    printf("%d\n", cnt);
    return 0;
}

Measured memory_bytes: 128
#include<cstdio>
#include<iostream>
#define maxn 5000000
#define LL long long
using namespace std;

struct edge{
	LL from,v,len;
}e[maxn];

LL tot,first[maxn];
void insert(LL u,LL v,LL len){
	tot++;
	e[tot].from = first[u];
	e[tot].v = v;
	e[tot].len = len;
	first[u] = tot;
}

LL dis[maxn],n,a,b,c,m,K;
bool book[maxn];
void dfs(LL now){
	for(LL i = first[now];i;i = e[i].from){
		LL v = e[i].v;
		if(!book[v]){
			book[v] = true;
			dis[v] = dis[now]+e[i].len;
			dfs(v);
		}
	}
}

int main(){
	scanf("%lld",&n);
	for(int i = 1;i < n;i++){
		scanf("%lld%lld%lld",&a,&b,&c);
		insert(a,b,c);
		insert(b,a,c);
	}
	
	scanf("%lld%lld",&m,&K);
	
	book[K] = true;
	dfs(K);
	
	for(int i = 0;i < m;i++){
		scanf("%lld%lld",&a,&b);
		printf("%lld\n",dis[a]+dis[b]);
	}
	
	return 0;
}

Measured memory_bytes: 15232
#include <iostream>

using std::cin;
using std::cout;
using std::endl;

int main(int argc, char* argv)
{
    constexpr int SIZE = 9;
    char input[SIZE];

    for (int index = 0; index < SIZE; index++)
    {
        cin >> input[index];
    }

    cout << input[0] << input [4] << input[8] << endl;
    return 0;
}

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

a = [list(map(int, input().split())) for _ in range(n)]

b = [int(input()) for _ in range(m)]

c = [ 0 for _ in range(n)]


for i in range(n):
    for j in range(m):
            c[i] += a[i][j]*b[j]
for i in range(n):
    print(c[i])


Measured memory_bytes: 6016
/*#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")*/
#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;

#define amen ;
#define vec vector
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define Str(x) to_string(x)
#define len(s) (int)s.size()

typedef long long ll;
typedef double d;
typedef long double lld;
typedef string str;
typedef unsigned long long ull;
typedef unsigned int ui;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int n;
    cin >> n;
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        ans = __gcd(x, ans);
    }
    cout << ans;


    return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] sa = br.readLine().split(" ");
		int n = Integer.parseInt(sa[0]);
		int k = Integer.parseInt(sa[1]);
		int k2 = k * 2;
		int k4 = k * 4;
		int[] x = new int[n];
		int[] y = new int[n];
		for (int i = 0; i < n; i++) {
			sa = br.readLine().split(" ");
			int a = Integer.parseInt(sa[0]);
			int b = Integer.parseInt(sa[1]);
			if (sa[2].equals("W")) {
				a += k;
			}
			x[i] = a % k2 + 1;
			y[i] = b % k2 + 1;
		}
		br.close();

		int[] dx = {-k, -k, k, k};
		int[] dy = {-k, k, -k, k};
		int[][] cnt = new int[k4 + 1][k4 + 1];
		for (int i = 0; i < n; i++) {
			cnt[x[i]][y[i]]++;
			for (int j = 0; j < 4; j++) {
				int nx = x[i] + dx[j];
				int ny = y[i] + dy[j];
				if (0 < nx && nx <= k2 && 0 < ny && ny <= k2) {
					cnt[nx][ny]++;
				}
			}
		}
		for (int i = 1; i <= k2; i++) {
			for (int j = 1; j <= k2; j++) {
				cnt[i + k2][j] = cnt[i][j];
				cnt[i][j + k2] = cnt[i][j];
				cnt[i + k2][j + k2] = cnt[i][j];
			}
		}

		for (int i = 0; i <= k4; i++) {
			for (int j = 0; j < k4; j++) {
				cnt[i][j + 1] += cnt[i][j];
			}
		}
		for (int j = 0; j <= k4; j++) {
			for (int i = 0; i < k4; i++) {
				cnt[i + 1][j] += cnt[i][j];
			}
		}

		int ans = 0;
		for (int i = 0; i <= k2; i++) {
			for (int j = 0; j <= k2; j++) {
				int val = cnt[i + k][j + k] - cnt[i][j + k] - cnt[i + k][j] + cnt[i][j];
				ans = Math.max(ans, val);
			}
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 127316
#include<bits/stdc++.h>
using namespace std;
int main(){
  int h,w;cin>>h>>w;
  vector<string> a(h);
  for(int i=0;i<h;i++)cin>>a.at(i);
  for(int j=0;j<h;j++){
    cout<<a.at(j)<<endl;
    cout<<a.at(j)<<endl;
  }
}

Measured memory_bytes: 256
#include<iostream>
#include<math.h>
#include<vector>
#include<algorithm>
#include<numeric>
#include<map>
#include<queue>
using namespace std;

int main(){
    int N,M,P[100010],Y[100010];cin>>N>>M;
    tuple<int,int,int>tp[100010];
    vector<string> v(100010);
    for(int i=0;i<M;++i){
        cin>>P[i]>>Y[i];
        tp[i]=make_tuple(P[i],Y[i],i);
    }
    sort(tp,tp+M);

    int x=1;
    string s1=to_string(get<0>(tp[0]));
    string s2=to_string(x);
    int n1=s1.size(),n2=s2.size();
    while(n1<6){
        s1="0"+s1;
        ++n1;
    }
    while(n2<6){
        s2="0"+s2;
        ++n2;
    }
    v[get<2>(tp[0])]=s1+s2;
    
    for(int i=1;i<M;++i){
        if(get<0>(tp[i])==get<0>(tp[i-1]))++x;
        else x=1;
        s1=to_string(get<0>(tp[i]));
        s2=to_string(x);
        int n1=s1.size(),n2=s2.size();
        while(n1<6){
            s1="0"+s1;
            ++n1;
        }
        while(n2<6){
            s2="0"+s2;
            ++n2;
        }
        v[get<2>(tp[i])]=s1+s2;
    }
    for(int i=0;i<M;++i)cout<<v[i]<<endl;
    return 0;
}

Measured memory_bytes: 10880
import Control.Monad

main = do
    [h, w] <- map read . words <$> getLine
    p <- replicateM h getLine
    putStrLn $ replicate (w + 2) '#'
    mapM_ putStrLn $ map (('#':) . (++"#")) p
    putStrLn $ replicate (w + 2) '#'

Measured memory_bytes: 1404
#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#ifdef int
const ll INF = (1LL<<60);
#else
const int INF = (1LL<<30);
#endif
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}

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

VI g[100010];
int p[100010];
PII x[100010];
int rn;

PII dfs(int v, int par, int d) {
  if(g[v].size() == 1 && par != -1) {
    if(p[v] == -1) {
      x[v] = {-INF, INF};
    } else {
      x[v] = {p[v], p[v]};
      if(abs(p[v] - rn)%2 != d%2) x[v] = {INF, -INF};
    }
    // cout << v << " " << x[v] << endl;
    return x[v];
  } else {
    PII ret = {-INF, INF};
    for(int i: g[v]) {
      if(i == par) continue;
      PII tmp = dfs(i, v, d+1);
      // tmp.first-1 から tmp.second+1
      if(ret.first < tmp.first-1) ret.first = tmp.first-1;
      if(ret.second > tmp.second+1) ret.second = tmp.second+1;
    }
    if(ret.first > ret.second) ret = {INF, -INF};
    if(p[v] != -1) {
      if(ret.first > p[v] || p[v] > ret.second) ret = {INF, -INF};
      else if(abs(p[v] - rn)%2 != d%2) ret = {INF, -INF};
      else ret = {p[v], p[v]};
    }
    // cout << v << " " << ret << endl;
    return x[v] = ret;
  }
}

void dfs2(int v, int par, int d) {
  for(int i: g[v]) {
    if(i == par) continue;
    // p[v]-1 と p[v]+1のどっちを入れるか？
    if(x[i].first <= p[v]-1 && p[v]-1 <= x[i].second) p[i] = p[v]-1;
    else if(x[i].first <= p[v]+1 && p[v]+1 <= x[i].second) p[i] = p[v]+1;
    else assert(false);
    dfs2(i, v, d+1);
  }
}

signed main(void)
{
  int n, k;
  cin >> n;
  REP(i, n-1) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    g[a].PB(b);
    g[b].PB(a);
  }
  memset(p, -1, sizeof(p));
  int root;
  cin >> k;
  REP(i, k) {
    int a, b;
    cin >> a >> b;
    a--;
    p[a] = b;
    root = a; rn = b;
  }

  PII ret = dfs(root, -1, 0);
  if(ret.first > ret.second) cout << "No" << endl;
  else {
    cout << "Yes" << endl;
    dfs2(root, -1, 0);
    REP(i, n) cout << p[i] << endl;
  }

  return 0;
}


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

int main(){
    int n,m; cin >> n >> m;
    vector<P> vec(m);
    rep(i,m) {
        int a,b; cin >> a >> b;
        a--;b--;
        vec[i] = P(b,a);
    }
    sort(ALL(vec));
    int ans = 0;
    int now = 0;
    int end = 0;
    while(now <= m-1){
        if(end <= vec[now].second){
            ans++;
            end = vec[now].first;
        }
        now++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 4052
<?php

$vectors = [[1, 0], [0, -1], [-1, 0], [0, 1]];

function solve() {
    $mp = [];
    for ($i = 0; $i < 12; $i++) {
        $mp[$i] = trim(fgets(STDIN));
        //echo $mp[$i] . "\n";
        //echo $mp[$i][10] . "\n";
    }
    $visited = array_fill(0, 12, array_fill(0, 12, false));
    $cnt = 0;
    for ($y = 0; $y < 12; $y++) {
        for ($x = 0; $x < 12; $x++) {
            if (!$visited[$y][$x] and $mp[$y][$x] === "1") {
                $cnt++;
                $visited[$y][$x] = true;
                search($x, $y, $mp, $visited);
            }
        }
    }
    return [$cnt, fgets(STDIN)];
}

function search($x, $y, &$mp, &$visited) {
    global $vectors;
    foreach ($vectors as $vector) {
        list($dx, $dy) = $vector;
        $nx = $x + $dx;
        $ny = $y + $dy;
        if ((0 <= $nx and $nx < 12 and 0 <= $ny and $ny < 12) and ($mp[$ny][$nx] === "1" and !$visited[$ny][$nx])) {
            $visited[$ny][$nx] = true;
            search($nx, $ny, $mp, $visited);
        }
    }
}

while (true) {
    list($cnt, $ok) = solve();
    echo $cnt . "\n";
    if (!$ok) {
        break;
    }
}


Measured memory_bytes: 9508
N = int(input())
A = []
for i in range(N):
    A.append(int(input())-1)
    
index = 0
count = 0
flag = True
while flag:
    index = A[index]
    if index == 1:
        flag = False
    if count > N:
        count = -1
        flag = False
    else:
        count += 1
print(count)

Measured memory_bytes: 7084
#include<iostream>
#include<vector>
#include<cstdio>
using namespace std;
int main(){
    char s[50][51];
    int H,W,count;
    cin >> H >> W;
    for(int i=0;i<H;i++)    scanf("%s",s[i]);

    for(int y=0;y<H;y++){
        for(int x=0;x<W;x++){
            if(s[y][x]=='#')    cout << '#';
            else{
                count = 0;
                for(int i=-1;i<=1;i++){
                    for(int j=-1;j<=1;j++){
                        if(y+i>=0&&y+i<H&&x+j>=0&&x+j<W&&s[y+i][x+j]=='#')  count++;    
                    }
                }
                cout << count;
            }
        }
        cout << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <numeric>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iterator>
#include <fstream>
#include <cstddef>
#include <cstring>

using namespace std;

typedef pair<int, int> P;
typedef long long ll;
#define PB push_back
#define rep(i, a) for(int i = 0; i < a; i++)
#define all(v) v.begin(),v.end()
#define FF first
#define SS second
#define mp make_pair
#define INT int_64
const ll INF = (1<<30);
const ll NEGA=-INF*10000; 


int ans = 0;
int n,m;
int cnt=0;

//最長増加部分列の長さの計算
int LIS(vector<int> V) {
	int DP[200001] = { 0 };
	fill(DP, DP + V.size(), INF);
	rep(i, V.size()) {
		*lower_bound(DP, DP + V.size(), V[i]) = V[i];
	}
	return lower_bound(DP, DP + V.size(), INF) - DP;
}

vector<int> p;
int main() 
{
 int t;
 cin>>n>>t;
 int a[100001]={0};
 rep(i,n) cin>>a[i];

 int maxv=-2000000;
 int minv=a[0];
 int cnt=0;
 rep(i,n){
   maxv=max(maxv,a[i]-minv);
   minv=min(minv,a[i]);
 }
 int memo=maxv;
 maxv=-2000000;
 minv=a[0];
 int sm[100000]={0};
 int p=0;
 rep(i,n){
   maxv=max(maxv,a[i]-minv); 
   if(a[i]-minv==memo) cnt++;
   if(minv>a[i]) p=i;
   minv=min(minv,a[i]);
 }

  cout<<cnt<<endl;
}



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

#define FOR(i,a,b) for(int i=int(a);i<int(b);i++)
#define REP(i,b) FOR(i,0,b)

long long read(void) {
	long long d;
	cin >> d;
	return d;
}
double readReal(void) {
	double d;
	cin >> d;
	return d;
}
string readString(void) {
	string s;
	cin >> s;
	return s;
}
void println(void) {
	cout << endl;
}
template <typename T>void print(T t) {
	cout << t;
}
template <typename T>void println(T t) {
	print(t);
	println();
}
template <typename T>
void print(const vector<T> &v, const string &sep = " ") {
	if (v.empty()) return;
	print(v[0]);
	for(int i = 1;  i < v.size(); ++i) {
		print(sep);
		print(v[i]);
	}
	return;
}
template <typename T>
void println(const vector<T> &v, const string &sep = " ") {
	print(v, sep);
	println();
	return;
}

int InsertSort(vector<int> *v) {
	vector<int> &vec = *v;
	FOR(i, 1, vec.size()) {
		int pivod = vec[i];
		int j = i - 1;
		while(j >= 0 && vec[j] > pivod) {
			vec[j + 1] = vec[j];
			j--;
		}
		vec[j + 1] = pivod;
		println(vec);
	}
	return 0;
}

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

	int size = read();
	vector<int> vec(size);
	REP(i, size) {
		vec[i] = read();
	}
	println(vec);
	InsertSort(&vec);

	return 0;
}



Measured memory_bytes: 3216
#include <bits/stdc++.h>
#define cinf(n,x) for(int i=0;i<(n);i++) cin >> x[i];
typedef long long int ll;
using namespace std;
const long long INF = 1LL<<60;

int main(){
	int n; cin >>n;
	vector<int> x(n),a(n); cinf(n,x);
	for(int i=0;i<n;i++){
		a[i]=x[i];
	}
	sort(a.begin(),a.end());
	int Xn=a[n/2-1];
	int Xn1=a[n/2];
	for(int i=0;i<n;i++){
		if(x[i]<=Xn){
			cout << Xn1 << endl;
		}
		else cout << Xn << endl;
	}
}

Measured memory_bytes: 3712
import java.util.Scanner;
class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int x = sc.nextInt();
    int y = sc.nextInt();
    
    System.out.print(x*y);
    System.out.print(" ");
    System.out.println(2*(x+y));
  }
}


Measured memory_bytes: 26112
from fractions import gcd
from math import ceil

def lcm(a,b):
    return a*b//gcd(a,b)

def num(l,r,n):
    return r//n-(l-1)//n

a,b,c,d=map(int,input().split())

l=lcm(c,d)
print((b-a+1)-num(a,b,c)-num(a,b,d)+num(a,b,l))


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

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

    vector<int> vec(n);

    for (int i = 0; i < k; i++)
    {
        int d;
        cin >> d;

        for (int j = 0; j < d; j++)
        {
            int a;
            cin >> a;
            vec.at(a - 1)++;
        }
    }

    int count = 0;

    for (int i = 0; i < n; i++)
    {
        if (vec.at(i) == 0)
        {
            count++;
        }
    }

    cout << count << endl;
}

Measured memory_bytes: 3584
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

ll f(ll n){
  if(n==0) return 0;
  if(n%4==1) return 1;
  if(n%4==2) return 4*(n/4)+3;
  if(n%4==3) return 0;
  return 4*(n/4);
}


int main(){
  ll A, B;
  cin >> A >> B;

  if(A==0){
    cout << f(B) << endl;
  }else{
    cout << (f(B) ^ f(A-1)) << endl;
  }
  
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<list>
#include<map>
#define REP(i,m,n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i,n) REP(i,0,n)
#define ll long long

using namespace std;

int n, x[100];

int main() {
	cin >> n;
	rep(i, n) {
		cin >> x[i];
	}

	int temp = 0;
	int MIN = 9999999;
	REP(i,1,101) {
		rep(j, n) {
			temp += (x[j] - i) * (x[j] - i);
		}
		MIN = min({ temp,MIN });
		temp = 0;
	}

	cout << MIN << endl;
	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
int n,k,v[50];
int val(int l, int r){
    int w[50],wn=0;
    for(int i=0;i<l;i++){
        w[wn]=v[i];
        wn++;
    }
    for(int i=r;i<n;i++){
        w[wn]=v[i];
        wn++;
    }
    if(wn>k)return -1;
    std::sort(w,w+wn);
    int push_num=k-wn;
    for(int i=0;i<wn&&i<push_num;i++){
        if(w[i]>=0)break;
        w[i]=0;
    }
    int sum=0;
    for(int i=0;i<wn;i++)sum+=w[i];
    return sum;
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++)scanf("%d",&v[i]);
    int ans=0;
    for(int l=0;l<=n;l++){
        for(int r=l;r<=n;r++){
            int tmp=val(l,r);
            if(tmp>ans)ans=tmp;
        }
    }
    printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<bits/stdc++.h>
#include<map>
#define ll long long int
using namespace std;
int main(){
	ll n;
	cin>>n;
	string s;
	map <string ,ll> m;
	while(n--){
		cin>>s;
		m[s]++;
	}
	cout<<"AC x "<<m["AC"]<<endl;
	cout<<"WA x "<<m["WA"]<<endl;
	cout<<"TLE x "<<m["TLE"]<<endl;
	cout<<"RE x "<<m["RE"]<<endl;
}

Measured memory_bytes: 3632
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
int k;
string ans;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> k >> ans;
    if(ans.size() <= k)
        cout << ans;
    else
        cout << ans.substr(0, k) + "...";
    return 0;
}


Measured memory_bytes: 3652
#include<bits/stdc++.h>
using namespace std;
const int maxN = 1e6 + 13;
string s;
int n, ans[maxN];

int get_val(string a) {
    if (a == "Male")
	return 0;
    else if (a == "Female")
	return 1;
    exit(0);
}
int main () {
    cin >> n;
    cout << 0 << endl;
    cin >> s;
    ans[0] = get_val(s);
    ans[n] = get_val(s);
    int l = 0, r = n;
    while (1) {
	int mid = l + r >> 1;
	cout << mid << endl;
	cin >> s;
	ans[mid] = get_val(s);
	if (((mid - l) % 2 == 0 && ans[mid] != ans[l]) || ((mid - l) % 2 == 1 && ans[mid] == ans[l]))
	    r = mid;
	else
	    l = mid;
    }
}
	    


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

#define pb push_back
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define ll long long
#define ii pair<int,int>
#define vi vector<int>
#define vll vector<ll>
#define vii vector<ii>

using namespace std;

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//#ifndef ONLINE_JUDGE
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	//#endif
	int a,b;
	cin>>a>>b;
	if(a>=13){
		cout<<b<<endl;
	}
	else if(a>=6 && a<=12){
		cout<<b/2<<endl;
	}
	else
		cout<<0<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#define repi(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,a) repi(i,0,a)
#define all(a) (a).begin(), (a).end()

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int X;

int main()
{
  std::cin >> X;

  if( X == 7 || X == 5 || X == 3 )
    std::cout << "YES" << std::endl;
  else
    std::cout << "NO" << std::endl;

  return 0;
}

Measured memory_bytes: 256
n=int(input())
a=[]
for i in range(n):
    a.append(int(input()))
a.sort()
a.reverse()
sum=0
if n%2==1:
    sum1=0
    sum2=0
    for j in range(n):
        if j+1<=n//2:
            sum1+=a[j]*2
        elif j+1<=n//2+2:
            sum1-=a[j]
        else:
            sum1-=a[j]*2
    a.reverse()
    for j in range(n):
        if j+1<=n//2:
            sum2-=a[j]*2
        elif j+1<=n//2+2:
            sum2+=a[j]
        else:
            sum2+=a[j]*2
    sum=max(sum1,sum2)
else:
    for j in range(n):
        if j+1<=n//2-1:
            sum+=a[j]*2
        elif j+1==n//2:
            sum+=a[j]
        elif j+1==n//2+1:
            sum-=a[j]
        else:
            sum-=a[j]*2
print(sum)

Measured memory_bytes: 7512
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define MOD 1000000007
#define MAX 1000000007
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define ub upper_bound
#define lb lower_bound
#define zoom ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;

int main() {


    zoom;
    ll N, K, i;
    cin >> N >> K;
    K = (ll)min(K, N);
    vector<ll> h(N), dp(N);
    for(i = 0; i < N; i += 1)
        cin >> h[i];
    dp[N - 1] = 0;
    for(i = N - 2; i >= N - K; i -= 1)
        dp[i] = (ll)abs(h[i] - h[N - 1]);
    for(; i >= 0; i -= 1) {
        dp[i] = -1;
        for(ll j = i + 1; j <= i + K; j += 1) {
            if(dp[i] == -1)
                dp[i] = (ll)abs(h[i] - h[j]) + dp[j];
            dp[i] = (ll)min(dp[i], (ll)abs(h[i] - h[j]) + dp[j]);
        }
    }
    cout << dp[0];
    return 0;
}

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

ll gcd(ll a,ll b){
  if(a%b==0)
    return(b);
  else
    return(gcd(b,a%b));
}

int main(){
  ll n,m;
  string s,t;
  cin >> n >> m >> s >> t;
  ll l=n*m/gcd(n,m);
  int ans=1;
  ll g=gcd(n,m);
  for(int i=0;i<g;i++){
    if(s[i*(n/g)]!=t[i*(m/g)]) ans=0;
  }
  if(ans) cout << l << endl;
  else cout << -1 << endl;
}

Measured memory_bytes: 3736
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (__typeof(a) i=(a); i<(b); ++i)
#define iter(it,c) for (__typeof((c).begin()) \
  it = (c).begin(); it != (c).end(); ++it)
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long long ll;
const int INF = ~(1<<31);

const double EPS = 1e-9;
const double pi = acos(-1);
typedef unsigned long long ull;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
template <class T> T smod(T a, T b) {
  return (a % b + b) % b; }

int main()
{
    int r, g, b, n;
    cin >> r >> g >> b >> n;
    int cnt = 0;
    rep(i,0,3001)
    {
        rep(j,0,3001)
        {
            int left = n - r*i - g*j;
            if(left >= 0 && left%b == 0) cnt++;
        }
    }
    cout << cnt << endl;
}


Measured memory_bytes: 256
from collections import defaultdict
mod = 10**9+7
#素因数分解
def factors_nojit(n):
    gaps = [1,2,2,4,2,4,2,4,6,2,6]
    length, cycle = 11, 3
    f, fs, nxt = 2, [], 0
    while f * f <= n:
        while n % f == 0:
            fs.append(f)
            n0 = n
            n //= f
        f += gaps[nxt]
        nxt += 1
        if nxt == length:
            nxt = cycle
    if n > 1: fs.append(n)
    return fs
#Combination事前計算
MAX = 10**5 + 100
fac = [1]*(MAX+1)
for i in range(1,MAX+1):
    fac[i] = (fac[i-1]*i)%mod
rev_m = [1]*(MAX+1)
rev_m[MAX] = pow(fac[MAX],mod-2,mod)
for i in range(MAX,0,-1):
    rev_m[i-1] = (rev_m[i]*i)%mod
def Comb(n,k):#nCk
    return (fac[n]*rev_m[k]*rev_m[n-k])%mod
N,M = map(int, input().split())
fs =  factors_nojit(M)
fs.sort()
dd = defaultdict(int)
ed = []
for f in fs:
    if dd[f] == 0:
        ed.append(f)
    dd[f] += 1
ans =1
for e in ed:
  k = dd[e]
  ans *= Comb(k+N-1,k)
  ans %= mod
print(ans)

Measured memory_bytes: 41200
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, w, h;
    cin >> w >> h >> n;
    int left = 0, right = w, up = h, down = 0;
    for (int i = 0; i < n; ++i) {
        int x, y, a;
        cin >> x >> y >> a;
        if (a == 1) {
            left = max(left, x);
        } else if (a == 2) {
            right = min(right, x);
        } else if (a == 3) {
            down = max(down, y);
        } else {
            up = min(up, y);
        }
    }
    int x = right-left, y = up-down;
    if (x <= 0 || y <= 0) cout << "0\n";
    else cout << x*y << "\n";
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<climits>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<numeric>
#include<map>
#include<set>
#include<bitset>
using namespace std;
#define REP(i,m,n) for(int i = m; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a)  (a).rbegin(),(a).rend()
#define PI 3.14159265359
#define MOD 1000000007
typedef long long LL;

template<class T> inline void chmax(T& a, T b) { if (a < b) { a = b; } }
template<class T> inline void chmin(T& a, T b) { if (a > b) { a = b; } }
template<class T> void print_vector(vector<T> vec) {
	cout << "[ ";
	for (int i = 0; i < vec.size(); i++) {
		cout << vec[i] << " ";
	}
	cout << "]" << endl;
}
template<class T> void print_pair_vector(vector<pair<T, T> > vec) {
	cout << "[ ";
	for (int i = 0; i < vec.size(); i++) {
		cout << "(" << vec[i].first << "," << vec[i].second << ") ";
	}
	cout << "]" << endl;
}

const int INF = 1 << 30;

int main(void) {
	LL N, K;
	cin >> N >> K;

	printf("%lld\n",K * LL(pow(K - 1, N - 1)));
	return 0;
}

Measured memory_bytes: 384
from sys import stdin


def fetch_one_line():
    return stdin.readline().rstrip()


def fetch_int_input():
    return [int(s) for s in fetch_one_line().split()]


def fetch_inputs(times):
    return [fetch_one_line() for _ in range(times)]


def fetch_int_inputs(times):
    return [[int(s) for s in fetch_one_line()] for _ in range(times)]


S = fetch_one_line()
is_ACGT = []
ACGT = "A C G T".split()

for s in S:
    is_ACGT.append(s in ACGT)

longest = -1
count = 0
for b in is_ACGT:
    if b:
        count += 1
    else:
        if count > longest:
            longest = count
            count = 0


if count > longest:
    longest = count

print(longest)




Measured memory_bytes: 38256
#include <algorithm>
#include <cstdio>
#include <vector>
#define pb push_back
std::vector<int> vec[200005];
int main()
{
	// freopen("AGC029-D.in", "r", stdin);
	int h, w, n;
	scanf("%d%d%d", &h, &w, &n);
	while (n--)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		vec[y].pb(x);
	}
	for (int i = 1; i <= w; i++)
		std::sort(vec[i].begin(), vec[i].end());
	int x = 1, y = 1, ans = h;
	while (x <= h)
	{
		auto it = std::lower_bound(vec[y].begin(), vec[y].end(), x);
		if (it != vec[y].end())
		{
			ans = std::min(ans, *it - 1);
			if (*it == x + 1)
				break;
		}
		x++;
		if (y != w && !binary_search(vec[y + 1].begin(), vec[y + 1].end(), x))
			y++;
	}
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 8832
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
int m[1919];
signed main(){
	int n,x;cin>>n>>x;
	rep(i,n)cin>>m[i];
	int sum=0;
	rep(i,n)sum+=m[i];
	sort(m,m+n);
	cout<<n+(x-sum)/m[0]<<endl;
	}


Measured memory_bytes: 256
// J'aime
// Chemise Blanche

#include <bits/stdc++.h>
using namespace std;

#define int long long

#define ii pair<int,int>
#define fi first
#define sc second

#define all(x) (x).begin(),(x).end()
#define dbg(x) cerr << __LINE__ << " > " << #x << " = " << (x) << endl

void MAIN() {
  int a, b;
  cin >> a >> b;
  if (a > b) swap(a, b);
  int t = b - a;
  if (t % 2) cout << "IMPOSSIBLE" << '\n';
  else cout << a + t / 2 << '\n';
}

signed main() {
#ifdef _DEBUG
  // freopen("in" , "r", stdin );
  // freopen("out", "w", stdout);
#endif
  ios::sync_with_stdio(0); cin.tie(0);
  int T = 1;
  // cin >> T;
  while (T--) MAIN();
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
 
#define rep(i, N) for (int i = 0; i < N; i++)
#define pb push_back
 
typedef long long ll;
typedef pair<ll, int> ll_i;

int main() {
    ll N, ans = 0;
    cin >> N;
    ll a[N];
    rep(i, N) cin>>a[i];
    for(int i=0; i < N; i++){
        for(int j = 0; j < N; j++){
            if (i != j){
                ans = max(ans, abs(a[i] - a[j]));
            }
        }
    }
    cout << ans << endl;
	return 0;
}

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

constexpr auto MAXN = 1000000+500;

std::string s,t;
std::queue<int> que;

signed main(void)
{
  int len,down,up; size_t ans = 0;

  std::cin>>len>>s>>t;

  if(s == t){ puts("0"); return 0; }
  
  down = up = len-1;

  while(down >= 0){
    while(down && t[down-1]==t[down]) --down;
    while(up>=0 && (up>down || s[up]!=t[down])) --up;
    if(up < 0){ puts("-1"); return 0; }

    while(!que.empty() && que.front()-que.size() >= down) que.pop();
    if(up != down) que.push(up);
    ans = std::max(ans,que.size()+1);
    --down;
  }

  std::cout<<ans<<std::endl;
  
  return 0;
}


Measured memory_bytes: 6280
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=n-1;i>=(0);i--)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define eall(v) unique(all(v), v.end())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;

int me[110];
int main(void){
	int n; cin >> n;
	string s; cin >> s;
	rep(i, s.size()){
		reps(j, i, s.size()){
			if(s[i] == '(' && s[j] == ')' && me[i] == 0 && me[j] == 0 ){
				me[i] = me[j] = 1;
			}
		}
	}
	int r = 0, l = 0;
	rep(i, s.size()){
		if(me[i] == 0){
			if(s[i] == '(') r++;
			else l++;
		} 
	}
	rep(i, l) s = '(' + s;
	rep(i, r) s = s + ')';
	cout << s << endl;
	return 0;
}

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

int main()
{
    string s;
    string x = "ox";
    int count = 0;
    cin >>  s;
    
    for(int i = 0; i < 3; i++){
        if(s[i] == x[0]){
            count++;
        }
    }
    
    cout << 700 + count * 100 << endl;

    return 0;
}

Measured memory_bytes: 256