akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>

using namespace std;

using ll =  long long;

constexpr ll MOD = 998244353;
constexpr ll N_MAX = 200000;
constexpr ll A_MAX = 1000000;

inline ll modpow(ll a, ll t) {
    ll ret = 1LL;
    while(t){
        if(t & 1LL){
            ret *= a;
            ret %= MOD;
        }
        a *= a;
        a %= MOD;
        t >>= 1;
    }
    return ret;
}

inline ll modinv(ll a) {
    return modpow(a, MOD-2);
}

vector<ll> w(A_MAX);


// 遅い init_w
// inline void init_w() {
//     w[1] = 1;
//     w[2] = (modinv(2)-1+MOD) % MOD;
//     for(int i=3;i<=A_MAX;++i) {
//         ll s = 0;
//         for(int j=1;j*j<=i;++j) {
//             if(i % j) continue;
//             s += w[j];
//             if(1 < j && j*j < i) s += w[i/j];
//             s %= MOD;
//         }
//         w[i] = (modinv(i) - s + MOD) % MOD;
//     }
// }
// 速い init_w
inline void init_w() {
    for(int i=1;i<=A_MAX;++i) {
        w[i] = modinv(i);
    }
    for(int i=1;i<=A_MAX;++i) {
        for(int j=i+i;j<=A_MAX;j+=i) {
            w[j] += MOD-w[i];
            w[j] %= MOD;
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false); cin.tie(nullptr);
    init_w();
    int n;
    cin >> n;

    vector<ll> a(A_MAX+1, 0);
    ll aa;
    for(int i=0;i<n;++i) {
        cin >> aa;
        ++a[aa];
    }

    ll ans = 0LL;
    for(int i=1;i<=A_MAX;++i) {
        int j = i;
        ll s = 0, t = 0;
        while(j <= A_MAX) {
            ll tmp = (j*a[j]) % MOD;
            s += tmp;
            s %= MOD;
            t += (tmp * j) % MOD;
            t %= MOD;
            j += i;
        }
        ans += (w[i] * (((s*s)%MOD - t + MOD) % MOD)) % MOD;
        ans %= MOD;
        // cerr << (w[i] * (((s*s)%MOD - t + MOD) % MOD)) % MOD << endl;
    }
    
    cout << (ans * modinv(2)) % MOD << endl;
}


Measured memory_bytes: 15872
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
const ll mod = 1000000007;
const ll INF = 1e+14;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define _GLIBCXX_DEBUG

int main(){
    int h,w; cin>>h>>w;
    vector<string> field(h);
    rep(i,h) cin>>field[i];

    int dist[60][60];
    rep(i,60){
        rep(j,60){
            dist[i][j]=-1;
        }
    }
    queue<P> que;

    dist[0][0]=1;
    que.push({0,0});
    int dx[4]={-1,1,0,0};
    int dy[4]={0,0,-1,1};

    while(!que.empty()){
        P v=que.front();
        que.pop();
        rep(i,4){
        int nx=v.first+dx[i];
        int ny=v.second+dy[i];
        if(nx<0||nx>=h||ny<0||ny>=w) continue;
        if(dist[nx][ny]!=-1) continue;
        if(field[nx][ny]=='#') continue;

        dist[nx][ny]=dist[v.first][v.second]+1;
        que.push({nx,ny});


        }

    }
    int count=0;
    rep(i,h){
        rep(j,w){
            if(field[i][j]=='.') count++;
        }
    }

    if(dist[h-1][w-1]==-1) cout<<-1<<endl;
    else{
        int ans=count-dist[h-1][w-1];
        cout<<ans<<endl;
    }

}

Measured memory_bytes: 3644
BASE = 9973
MOD1 = 10 ** 9 + 7
MOD2 = 998244353


class RollingHash:
    # 文字列Sのローリングハッシュを構築
    # 計算量: O(N)
    def __init__(self, S, MOD):
        self.MOD = MOD
        # acc[i]はS[0:i]のハッシュ値となる
        self.acc = [0]
        a = 0
        # 累積和を計算するイメージ
        for i, c in enumerate(S):
            h = ord(c) - ord("a") + 1
            offset = pow(BASE, i, MOD)
            a = (a + (h * offset)) % MOD
            self.acc.append(a)

    # S[i:j]のハッシュ値を返す
    # 計算量: O(1)
    def hash(self, i, j):
        # 累積和を用いて部分区間の和を計算するイメージ
        # 注意: 基数によるオフセットをキャンセルする必要がある
        offset = pow(BASE, i, self.MOD)
        # 素数MODを法とする剰余類における除算は逆元を乗算することで計算できる
        # 素数MODを法とする剰余類におけるxの逆元はx^(MOD - 2)に等しい
        offset_inv = pow(offset, self.MOD - 2, self.MOD)
        return ((self.acc[j] - self.acc[i]) * offset_inv) % self.MOD


N = int(input())
S = input()

# Sのローリングハッシュを計算しておく
rolling1 = RollingHash(S, MOD1)
rolling2 = RollingHash(S, MOD2)

# 長さmのダジャレがSに含まれるならば、長さm-1のダジャレも含まれる
# つまり、長さmのダジャレがSに含まれるならば真となる述語をP(m)とすると、以下を満たす整数cが存在する:
#   - 0以上c以下の整数mについてP(m)は真
#   - cより大きい整数mについてP(m)は偽
# ※ Pは単調関数ということ
# このcを二分探索で発見すれば高速化できる！

# P(ok)は真
ok = 0
# P(ng)は偽
ng = N
while ng - ok > 1:
    # 区間[ok, ng)の中央値をmとする
    m = (ok + ng) // 2

    # 長さmのダジャレが存在するか判定する
    # 長さmのformerのハッシュ値のキャッシュ
    former_cache1 = set()
    former_cache2 = set()
    p = False
    # latterに着目してループを回す
    for i in range(m, N):
        # ダジャレ長を決め打ちしているのでjを直接計算できる
        j = i + m
        # S[i:j]がSをはみ出したらループ終了
        if j > N:
            break
        # formerのハッシュ値をキャッシュする
        former_cache1.add(rolling1.hash(i - m, i))
        former_cache2.add(rolling2.hash(i - m, i))
        # キャッシャに同一のハッシュ値が存在する場合（ハッシュ値が衝突した場合）、ダジャレになっていると判定できる
        # ハッシュ値の計算、キャッシュ存在判定は共にO(1)で処理できる！
        if (
            rolling1.hash(i, j) in former_cache1
            and rolling2.hash(i, j) in former_cache2
        ):
            p = True
    # 区間[ok, ng) を更新
    if p:
        ok = m
    else:
        ng = m
# whileループを抜けると区間[ok, ng)は[c, c + 1) になっている
ans = ok

print(ans)


Measured memory_bytes: 45292
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
using namespace std;
const int dy[] = {1, -1, 0, 0, 1, -1, 1, -1};
const int dx[] = {0, 0, 1, -1, 1, -1, -1, 1};
int h, w, sy, sx, max_size;
map<string, int> mp;
string table[15];
string str;
void solve(char ch)
{
	for(int i = 0; i < 8; i++)
	{
		int ny = sy;
		int nx = sx;
		str = "";
		while(1)
		{
			str += table[ny][nx];
			mp[str]++;
			if(mp[str] >= 2)
				max_size = max(max_size, (int)str.size());
			int tmp_y = ny + dy[i];
			int tmp_x = nx + dx[i];
			if(tmp_y < 0) tmp_y = h - 1;
			if(tmp_x < 0) tmp_x = w - 1;
			if(tmp_y >= h) tmp_y = 0;
			if(tmp_x >= w) tmp_x = 0;
			ny = tmp_y;
			nx = tmp_x;
			if(tmp_y == sy && tmp_x == sx)
				break;
		}
	}
}	
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	while(cin >> h >> w, h | w)
	{
		mp.clear();
		str = "";
		max_size = 2;
		for(int i = 0; i < h; i++)
		{
			cin >> table[i];
		}
		for(int i = 0; i < h; i++)
		{
			for(int j = 0; j < w; j++)
			{
				sy = i; sx = j;
				solve(table[i][j]);
			}
		}
		bool flag = false;
		for(auto itr = mp.begin(); itr != mp.end(); itr++)
		{
			if(itr->second >= 2 && itr->first.size() == max_size)
			{
				flag = true;
				cout << itr->first << endl;
				break;
			}
		}
		if(!flag)
			cout << 0 << endl;
	}
	return 0;
}



Measured memory_bytes: 37960
N = int(input())

if N==111 :
    print("999")
elif N== 119:
    print("991")
elif N== 191:
    print("919")
elif N== 911:
    print("199")
elif N== 199:
    print("911")
elif N== 919:
    print("191")
elif N== 991:
    print("119")
elif N== 999:
    print("111")

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
using namespace std;
int main() {
    int n;
    cin >> n;
    int cnt = n;
    vector<int> d;
    while(cnt--){
        int x;
        cin >> x;
        d.push_back(x);
    }
    sort(all(d));
    cout << d[n/2]-d[(n/2)-1] << endl;
}

Measured memory_bytes: 892
package main

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

var sc *bufio.Scanner

func nextStr() 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 sugarWater struct {
	water int
	sugar int
}

func main() {
	sc = bufio.NewScanner(os.Stdin)
	sc.Buffer(make([]byte, 0), 1000000001*3)
	sc.Split(bufio.ScanWords)
	a, b, c, d, e, f := nextInt(), nextInt(), nextInt(), nextInt(), nextInt(), nextInt()

	sugarWaterArray := make([]sugarWater, 0)
	for ai := 0; ai*a*100 <= f; ai++ {
		sugarWaterArray = append(sugarWaterArray, sugarWater{ai * a * 100, 0})
	}

	l := len(sugarWaterArray)
	for li := 0; li < l; li++ {
		sw := sugarWaterArray[0]
		sugarWaterArray = sugarWaterArray[1:]
		for bi := 0; bi*b*100+sw.water <= f; bi++ {
			sugarWaterArray = append(sugarWaterArray, sugarWater{bi*b*100 + sw.water, 0})
		}
	}

	l = len(sugarWaterArray)
	for li := 0; li < l; li++ {
		sw := sugarWaterArray[0]
		sugarWaterArray = sugarWaterArray[1:]
		if sw.water == 0 {
			continue
		}
		for ci := 0; ci*c+sw.water <= f; ci++ {
			sugarWaterArray = append(sugarWaterArray, sugarWater{sw.water, ci * c})
		}
	}

	for swi := range sugarWaterArray {
		maxSugar1 := f - (sugarWaterArray[swi].water + sugarWaterArray[swi].sugar)
		maxSugar2 := (sugarWaterArray[swi].water * e / 100) - sugarWaterArray[swi].sugar
		var maxSugar int
		switch {
		case maxSugar1 < maxSugar2:
			maxSugar = maxSugar1
		default:
			maxSugar = maxSugar2
		}
		switch {
		case maxSugar < 0:
			sugarWaterArray[swi].sugar = 0
		default:
			sugarWaterArray[swi].sugar += (maxSugar / d) * d
		}
	}

	ans := sugarWaterArray[0]
	for _, sw := range sugarWaterArray {
		// sw.sugar/sw.water > ans.sugar/ans.water
		if sw.sugar*ans.water > ans.sugar*sw.water {
			ans = sw
		}
	}
	fmt.Println(ans.water+ans.sugar, ans.sugar)
}


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

int main () {
  
  int N, K;
  cin >> N >> K;
  
  vector<int> h(N);
  
  for (int i = 0; i < N; i++) {
    cin >> h[i];
  }
  
  vector<long long> dp(N, 1000000000); // dp[i]は高さh[i]の足場までの最小コスト
  
  dp[0] = 0;
  
  for (int i = 1; i <= N; i++) {
    for (int j = max(i - K, 0); j < i; j++) {
      if (dp[j] + max(h[i] - h[j], h[j] - h[i]) < dp[i]) {
        dp[i] = dp[j] + max(h[i] - h[j], h[j] - h[i]);
      }
    }
  }
  
  cout << dp[N - 1] << endl;
  
}

Measured memory_bytes: 1408
#include <utility>
#include <vector>
#include <iostream>
#include <algorithm>
#include <set>
#include <climits>
#define REP(i,n) for(int i=0;i<n;i++)
typedef unsigned long ul;
typedef unsigned long long ull;
typedef long long ll;
using namespace std;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int inf = 10000000;

int main() {
	cin.tie(0);
   	ios::sync_with_stdio(false);
    int N, K;
    cin >> N >> K;
    int A[N];
    int l, r;
    int orig;
    for(int i = 0; i < N; i++){
      cin >> A[i];
      if(A[i] == 1){
        orig = i;
      }
    }
    int min = INT_MAX;
    for (int i = 0; i < K; i++){
      l = orig + (i-K+1);
      r = orig + i;
      if(l >= 0 && r < N){
        int ans = 1;
        for(int i = l; i > 0; i -= K-1){
          ans++;
        }
        for(int i = r; i < N-1; i += K-1){
          ans++;
        }
        if (ans < min){
          min = ans;
        }
      }
    }
    cout << min << endl;
    return 0;
}

Measured memory_bytes: 640
import java.util.Scanner;

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

        int a = scanner.nextInt();
        int b = scanner.nextInt();

        String cmp = "==";
        if (a < b)
            cmp = "<";
        else if (a > b)
            cmp = ">";

        System.out.printf("a %s b\n", cmp);
    }
}


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

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(), (x).end()

using namespace std;

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

using ll = long long;
using ld = long double;

const int INF = 1e9;
const ld eps = 1e-9, pi = acos(-1.0);

struct Node{
  int k;
  int p;
  Node* lc = NULL;
  Node* rc = NULL;
  Node(int k, int p) : k(k), p(p){}
};

Node* rightRotate(Node* n){
  Node* l = n->lc;
  if(l!=NULL){
    n->lc = l->rc;
    l->rc = n;
  }
  return l;
}

Node* leftRotate(Node* n){
  Node* r = n->rc;
  if(r!=NULL){
    n->rc = r->lc;
    r->lc = n;
  }
  return r;
}

void preorder(Node* n){
  if(n==NULL) return;
  cout << " " << n->k;
  preorder(n->lc);
  preorder(n->rc);
  return;
}

void inorder(Node* n){
  if(n==NULL) return;
  inorder(n->lc);
  cout << " " << n->k;
  inorder(n->rc);
  return;
}

Node* ins(Node* n, int k, int p){
  if(n==NULL) { return new Node(k, p); }
  if(k==n->k) return n;
  if(k<n->k){
    n->lc = ins(n->lc, k, p);
    if(n->p<n->lc->p) n = rightRotate(n);
  } else {
    n->rc = ins(n->rc, k, p);
    if(n->p<n->rc->p) n = leftRotate(n);
  }
  return n;
}

bool fnd(Node* n, int k){
  if(n==NULL) return false;
  if(n->k==k) return true;
  return (n->k>k ? fnd(n->lc, k) : fnd(n->rc, k));
}

Node* del(Node* n, int k);

Node* exec_del(Node* n,int k){
  if(n->lc==NULL && n->rc==NULL) { delete n; return NULL; }
  if(n->lc==NULL) n = leftRotate(n);
  else if(n->rc==NULL) n = rightRotate(n);
  else{
    if(n->lc->p > n->rc->p) n = rightRotate(n);
    else n = leftRotate(n);
  }
  return del(n, k);
}

Node* del(Node* n, int k){
  if(n==NULL) return NULL;
  if(k<n->k) n->lc = del(n->lc, k);
  else if(k>n->k) n->rc = del(n->rc, k);
  else return exec_del(n, k);
  return n;
}

void prt(Node* n){
  inorder(n);
  cout << endl;
  preorder(n);
  cout << endl;
  return;
}

int main(){
  int n;
  cin >> n;
  char str[10];
  int k, p;
  Node* top = NULL;
  REP(i, n){
    scanf("%s", str);
    if(str[0]=='i'){
      cin >> k >> p;
      top = ins(top, k, p);
    } else if (str[0]=='f'){
      cin >> k;
      cout << (fnd(top, k) ? "yes" : "no") << endl;
    } else if (str[0]=='d'){
      cin >> k;
      top = del(top, k);
    } else {
      prt(top);
    }
  }
  return 0;
}


Measured memory_bytes: 9380
#include <cstdio>
#include <cstdint>

constexpr intmax_t mod = 1e9+7;

int main() {
  intmax_t n, k;
  scanf("%jd %jd", &n, &k);

  intmax_t res = 1;
  for (int i = 0; i < n; ++i)
    (res *= k) %= mod;

  printf("%jd\n", res);
}



Measured memory_bytes: 2744
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		sc.close();
		int cnt = 0;
		if(s.charAt(0)=='1')cnt++;
		if(s.charAt(1)=='1')cnt++;
		if(s.charAt(2)=='1')cnt++;
		System.out.println(cnt);
	}
}


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

int main()
{
    int N, L;
    cin >> N >> L;
    int sum = N*(L - 1) + (N*(N+1))/2;
    int mv = 1e9;
    for (int i = 1; i <= N; ++i) {
        if (abs(L + i - 1) < abs(mv)) {
            mv = L + i - 1;
        }
    }
   
    cout << sum - mv << endl;  
    return 0;
}

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


int main() {
    int n,k;
    cin >> n >> k;
    if(n%k)cout << 1 << endl;
    else cout << 0;

    return 0;
}

/*
やっほい！
　　　　　　　やほほい！
　　　　+　　 　*
　　　 ∧∧　　. ∧∞∧　*
*　ヽ(=´ω｀)人(´ω｀*)ﾉ
　.～（ O x.） （ 　 O)～　+
。*　 　∪　　　　∪
*/

Measured memory_bytes: 256
s=input()
count=0

for i in range(len(s)):
  if i%2==0:
    if s[i]=="R" or s[i]=="U" or s[i]=="D":
      count+=1
  else:
    if s[i]=="L" or s[i]=="U" or s[i]=="D":
      count+=1

if count==len(s):
  print("Yes")
else:
  print("No")

Measured memory_bytes: 3060
h, w = map(int, input().split())
c = [list(map(int, input().split())) for _ in range(10)]
a = [list(map(int, input().split())) for _ in range(h)]

for x in range(10):
    for y in range(10):
        for z in range(10):
            c[y][z] = min(c[y][z], c[y][x] + c[x][z])

ans = 0
for x in range(h):
    for y in range(w):
        if a[x][y] >= 0:
            ans += c[a[x][y]][1]

print(ans)


Measured memory_bytes: 3316
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <numeric>
#include <cstdint>
#include <iomanip>
#include <set>
#include <map>
#include <unordered_map>
#include <cassert>
using ll = long long;
#define rep(i,n) for(int i=0; i<(n); i++)
#define fast_io(); std::ios_base::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0);

int main(){
    fast_io();

    int n,first=0,second=0; std::cin >> n;
    std::vector<int> a(n,0);
    rep(i,n){
        std::cin >> a[i];
        if(first<a[i]){
            first = a[i];
        }else if(second<a[i]){
            second = a[i];
        }
    }

    rep(i,n){
        if(a[i]==first) std::cout << second << "\n";
        else std::cout << first << "\n";
    }
    return 0;
}


Measured memory_bytes: 3996
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#define INF 1<<30
using namespace std;
int main() {
	cin.tie(0);ios::sync_with_stdio(false);
	int V, E, r; cin >> V >> E >> r;
	vector<vector<pair<int,int>>> g(V);
	vector<int> dp(V), f(V, 0);
	queue<int> q;

	//input
	int s, t, d;
	for (int i = 0; i < E; i++) {
		cin >> s >> t >> d;
		g[s].push_back(make_pair(t, d));
	}

	//initialize
	fill(dp.begin(), dp.end(), INF);
	dp[r] = 0;
	q.push(r);
	f[r]++;

	//Dijkstra
	while (!q.empty()) {
		int k = q.front(); q.pop();
		for (int i = 0; i < g[k].size();i++) {
			int next = g[k][i].first;
			int w = g[k][i].second;
			if (dp[k] + w < dp[next]) {
				dp[next] = dp[k] + w;
				f[next]++;
				q.push(next);
			}
			if (f[next] >= V) { cout << "NEGATIVE CYCLE" << endl; return 0; }
		}
	}
	//output
	for (int i = 0; i < V;i++) {
		if (dp[i] == INF) { cout << "INF" << endl; }
		else { cout << dp[i] << endl; }
	}
}

Measured memory_bytes: 3176
n, q = map(int, input().split())
s = input()
count = [0]*(n+1)
for i in range(1, n):
    count[i] += count[i-1]
    if s[i-1:i+1] == "AC":
      count[i] += 1
for i in range(q):
    l, r = map(int, input().split())
    print(count[r-1] - count[l-1])

Measured memory_bytes: 9492
class BinaryIndexedTree:
    def __init__(self, size):
        self.data = [0] * (size+1)
        self.size = size+1
        self.msb = 1 << (size.bit_length()-1)
    
    def _add(self, i, w):
        i += 1
        while i < self.size:
            self.data[i] += w
            i += i & -i
    
    def _get_sum(self, i):
        res = 0
        while i > 0:
            res += self.data[i]
            i -= i & -i
        return res

    def __getitem__(self, i):
        """
        [0,i)
        """
        if isinstance(i, slice):
            if i.start is None:
                return self._get_sum(i.stop)
            else:
                return self._get_sum(i.stop) - self._get_sum(i.start)
        else:
            return 0 # fake value
    
    __setitem__ = _add
    
    def bisect_left(self, v):
        """
        return smallest i s.t v <= sum[:i]
        """
        i = 0
        k = self.msb
        while k > 0:
            i += k
            if i < len(self.data) and self.data[i] < v:
                v -= self.data[i]
            else:
                i -= k
            k >>= 1
        return i
    
    def bisect_right(self, v):
        """
        return smallest i s.t v < sum[:i]
        """
        i = 0
        k = self.msb
        while k > 0:
            i += k
            if i < len(self.data) and self.data[i] <= v:
                v -= self.data[i]
            else:
                i -= k
            k >>= 1
        return i
    
    bisect = bisect_right



def solve(C, queries):
    N = len(C)
    Q = len(queries)
    bit = BinaryIndexedTree(N)

    last_ind = [None]*(N + 1)
    sorted_qi = sorted(range(Q), key=lambda i:queries[i][1])

    res = [None]*Q
    pr = 0
    temp = 0
    for qi in sorted_qi:
        l,r = queries[qi]
        for j in range(pr,r):
            c = C[j]
            if last_ind[c] is not None:
                bit._add(last_ind[c], -1)
            else:
                temp += 1
            last_ind[c] = j
            bit._add(j, 1)

        pr = r
        res[qi] = temp - bit._get_sum(l-1)

    return res

# from random import randrange, seed
# from time import perf_counter

# def test():
#     seed(1234)
#     N = 5*10**5
#     C = [randrange(N) for _ in range(N)]
#     queries = [tuple(sorted((randrange(1,N+1),randrange(1,N+1)))) for _ in range(N)]
#     start = perf_counter()
#     solve(C,queries)
#     stop = perf_counter()
#     print(stop-start)

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

if __name__ == '__main__':
    N,Q = map(int,readline().split())
    C = list(map(int,readline().split()))

    m = map(int,read().split())
    queries = list(zip(m,m))

    print(*solve(C,queries), sep='\n')
    # test()


Measured memory_bytes: 242264
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// #include <ext/pb_ds/detail/standard_policies.hpp>
// using namespace __gnu_pbds;
using namespace std;
// using cd = complex<double>;
// template <typename T>
// using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,
//     tree_order_statistics_node_update>;
 
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC optimization ("unroll-loops")
typedef long long int ll;
typedef long double ld;
const ll N = 1e6;
// const ll m = 1e9 + 7;
const ll inf= 1e14;
const ll mod =1e9+7;
const double PI = acos(-1);
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define pii pair<ll,ll>
#define pld pair<ld,ld>
ll powm(ll a, ll b) { a = a%mod;ll res = 1; while (b) { if (b & 1) res = (res * a) % mod; a = (a * a) % mod; b >>= 1; } return res; }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("error.txt","w",stderr); 
    #endif  
    ll t = 1;
    // cin>>t;
    while(t--){
        ll n,W;
        cin>>n>>W;
        ll w[n],v[n];
        for(int i = 0;i<n;i++){
            cin>>w[i]>>v[i];
        }
        map<ll,std::vector<ll>> val;
        for(int i = 0;i<n;i++){
            val[w[i]].pb(v[i]);
        }
        ll b[4] = {w[0],w[0]+1,w[0]+2,w[0]+3};
        for(int i = 0;i<4;i++){
            // cout<<val[b[i]].size()<<" "<<b[i]<<'\n';
            sort(val[b[i]].begin(),val[b[i]].end());
            reverse(val[b[i]].begin(),val[b[i]].end());
            for(int j = 1;j<val[b[i]].size();j++){
                val[b[i]][j]+=val[b[i]][j-1];
            }
        }
        ll ans = 0;
        for(int i = 0;i<=(int)val[b[0]].size();i++){
            
            for(int j = 0;j<=(int)val[b[1]].size();j++){
                
                for(int k = 0;k<=(int)val[b[2]].size();k++){
                    
                    for(int l = 0;l<=(int)val[b[3]].size();l++){
                        ll te = 0;
                        // cout<<i<<" "<<j<<" "<<k<<" "<<l<<'\n';
                        if(l){
                            te+=val[b[3]][l-1];
                        }
                        if(k){
                            te+=val[b[2]][k-1];
                        }
                        if(j){
                            te+=val[b[1]][j-1];
                        }
                        if(i){
                            te+=val[b[0]][i-1];
                        }
                        if(i*b[0]+j*b[1]+k*b[2]+l*b[3]<=W){
                            ans = max(ans,te);
                        }
                    }
                }
            }
        }
        cout<<ans<<'\n';

    }

} 

Measured memory_bytes: 3620
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

k = n_in()

h = {
    0: [0,1],
    1: [0,1,2],
    2: [1,2,3],
    3: [2,3,4],
    4: [3,4,5],
    5: [4,5,6],
    6: [5,6,7],
    7: [6,7,8],
    8: [7,8,9],
    9: [8,9],
}


from collections import deque

q = deque(['1','2','3','4','5','6','7','8','9'])

i = 0
current = '0'

while True:
    current = q.popleft()
    i += 1
    for j in h[int(current[-1])]:
        q.append(current + str(j))

    if i == k:
        break

print(current)



Measured memory_bytes: 68956
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<iomanip>
#include<set>
#include<queue>

using namespace std;

#define MOD 1000000007

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

	long long x=1,y=1,z=1;
	for(int i=0;i<n;i++)
	{
		x*=10;
		x%=MOD;

		y*=8;
		y%=MOD;

		z*=9;
		z%=MOD;
	}

//	cerr << x << " " << y << " " << z << endl;
	long long ans = (x-y-(z-y)*2);
	while(ans<0)
		ans+=MOD;
	cout <<  ans%MOD << endl;




}

Measured memory_bytes: 3628
// D - Practical Skill Test
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define rp(i,n) for(int i=0;i<(n);++i)

int main(){
	int H,W,D; cin>>H>>W>>D;

	int MAX = H * W;
	vi Y(MAX+1), X(MAX+1), C(MAX+1);

	rp(h, H) rp(w, W){ int a; cin>>a; Y[a] = h; X[a] = w; }

	for(int now=D+1; now<=MAX; ++now){
		int pre = now - D;
		C[now] = C[pre] + abs(Y[pre] - Y[now]) + abs(X[pre] - X[now]);
	}

	int Q; cin>>Q;
	while(Q--){ int l,r; cin>>l>>r; cout<< C[r] - C[l] <<endl; }
}

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

#define pb push_back
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,n,s) for(int i=(s);i<(n);i++)
#define rrep(i,n) for(int i=(n-1);i>=0;i--)
#define rreps(i,n,s) for(int i=s;i>=n;i--)
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

using ll = long long;

using namespace std;
constexpr long long MAX = 5100000;
constexpr long long INF = 1LL << 60;
constexpr int MOD = 1000000007;

int main(){
cin.tie(0);
ios::sync_with_stdio(false);
int n;
cin>>n;
vector<ll>a(n),b(n);
rep(i,n){
    cin>>a[i]>>b[i];
}
sort(a.begin(),a.end());
sort(b.begin(),b.end());

ll ans=0;
if(n%2!=0){
    ans=b[(n-1)/2]-a[(n-1)/2]+1;
}
else{
    ans=(b[n/2-1]+b[n/2])-(a[n/2-1]+a[n/2])+1;
}
cout<<ans<<endl;
return 0;
}

Measured memory_bytes: 6380
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i,l,r) for (int i=l; i<=r; i++)
typedef long long ll;
using namespace std;

const int N=40;
int n;
ll ans,f[N][N];
bool c[N];
char s[N],a[N],b[N];

void work(){
	int tot=0,tot2=0;
	rep(i,1,n) if (c[i]) a[++tot]=s[i]; else b[++tot2]=s[i];
	reverse(a+1,a+tot+1); reverse(b+1,b+tot2+1);
	memset(f,0,sizeof(f)); f[0][0]=1;
	rep(i,0,n){
		rep(j,0,min(i,tot)) if (f[i][j]) {
			if (j<tot && a[j+1]==s[i+n+1]) f[i+1][j+1]+=f[i][j];
			if (i-j<tot2 && b[i-j+1]==s[i+n+1]) f[i+1][j]+=f[i][j];
		}
	}
	ans+=f[n][tot];
}

void dfs(int x){
	if (x>n){ work(); return; }
	c[x]=1; dfs(x+1); c[x]=0; dfs(x+1);
}

int main(){
	scanf("%d",&n); scanf("%s",s+1);
	dfs(1); printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 256
#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
//問題文および制約はちゃんと確認しよう！
//サイズは10^5じゃなくて2×10^5とかかもしれないし、重要な制約・条件を見落としているかも
//とりあえずサンプルを読んでから解法を考えよう？
lint mo=1000000007;
lint zyo[5010];
lint dp[5010][5010][3];
int main()
{
	zyo[0]=1;
	rep(i,5005) zyo[i+1]=(zyo[i]*2)%mo;
	memset(dp,0,sizeof(dp));
	int n,a,b;cin>>n>>a>>b;
	if(a<b) swap(a,b);
	if(b==1){
		cout<<zyo[n]<<endl;return 0;
	}
	dp[1][1][0]=1;
	dp[1][1][1]=1;
	dp[b][b][2]=1;
	lint out=0;
	rep(i,n+1) rep(j,i+1){
		rep(k,3) dp[i][j][k]%=mo;
		if(j>=a){
			rep(k,3){
				out+=dp[i][j][k]*zyo[n-i];
				out%=mo;
			}
			continue;
		}
		if(i>=n) continue;
		
		dp[i+1][1][1]+=dp[i][j][0];
		if(j<b-1){
			dp[i+1][j+1][0]+=dp[i][j][0];
		}
		
		dp[i+1][j+1][1]+=dp[i][j][1];
		dp[i+1][1][0]+=dp[i][j][1];
		if(i+b<=n) dp[i+b][j+b][2]+=dp[i][j][1];
		
		dp[i+1][j+1][1]+=dp[i][j][2];
		dp[i+1][j+1][2]+=dp[i][j][2];
	}
	cout<<out<<endl;
}


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

using namespace std;

#define pb push_back
#define mp make_pair
#define lli long long int
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define mii map<lli,lli>
#define msi map<string,lli>
#define pii pair<lli,lli> 
#define vi vector<lli> 
#define vvi vector< vector<lli> >
#define sz(x) (lli)x.size()
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define MAX1 998244353
#define MAX2 1000000007
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    std::cerr << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');std::cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#define input(data,n,command) for(lli i=0;i<n;i++){lli tmp;cin>>tmp;data.pb(tmp);command}
#define sort_asc(a) sort(a.begin(),a.end());
//#define sort_desc(a) sort(a.begin(),a.end(),greater<lli>());
#define display(a) for(lli i = 0 ;i<a.size();i++){cout<<a[i]<<" ";} cout<<endl;
#define rep(i,a,b) for(lli i = a;i < b;i++)
#define endl "\n"

//Written By MUDIT BHARDWAJ...
/*--------------------------------------------------------------------*/
//vector<pair<lli,lli>>adj[300010];

lli solve()
{
    //start from here
    lli n;
    cin>>n;
    lli x = n%1000;
    if(x)
    {
        cout<<1000 - x;
    }
    else
    {
        cout<<x;
    }
    return 0;
}

int main()
{
    ios
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    lli T=1;
    //cin>>T;
    while(T--)
    {
        solve();
    }
    return 0;
}
/*-----------------------------------------------------------------------*/

Measured memory_bytes: 3592
#include <stdio.h>

int main(int argc, char const *argv[]) {
	int N;
	char A[101];
	char B[101];
	char C[101];
	scanf("%d", &N);
	scanf("%s", A);
	scanf("%s", B);
	scanf("%s", C);

	int count = 0;
	for (size_t i = 0; i < N; i++) {
		if (A[i] == B[i] && A[i] == C[i] && B[i] == C[i]) {
			count += 0;
		} else if (A[i] == B[i] || A[i] == C[i] || B[i] == C[i]) {
			count += 1;
		}

		if (A[i] != B[i] && A[i] != C[i] && B[i] != C[i]) {
			count += 2;
		}
	}

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

	return 0;
}


Measured memory_bytes: 128
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = Integer.parseInt(sc.next());
		int b = Integer.parseInt(sc.next());
		System.out.println(a*b + " " + (2*a+2*b));

	}

}

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

main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, K; cin >> N >> K; int a[N];
    for(int i = 0; i < N; i++) cin >> a[i];
    sort(a, a+N);
    ll ans = 0;
    for(int i = 0; i < K; i++) ans += a[i];
    cout << ans;
}

Measured memory_bytes: 3616
#include <cstdio>
typedef long long int64;
static const int MAXN = 1e5 + 3;
static const int MODULUS = 1e9 + 7;
#define _  %  MODULUS
#define __ %= MODULUS

int n, m;
int64 x[MAXN], y[MAXN];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i) scanf("%lld", &x[i]);
    for (int i = 0; i < m; ++i) scanf("%lld", &y[i]);

    int64 sum = 0, ans = 0;
    for (int i = 1; i < m; ++i)
        (sum += (int64)i * (m - i)_ * (y[i] - y[i - 1]))__;
    for (int i = 1; i < n; ++i)
        (ans += (int64)i * (n - i)_ * sum _ * (x[i] - x[i - 1]))__;

    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 1664
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        int k = Integer.parseInt(sc.next());
        Integer a[] = new Integer[n];
        Integer dp[] = new Integer[n];
        Arrays.fill(dp, Integer.MAX_VALUE); 
        dp[0] = 0;

        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(sc.next());
        }

        for (int i = 0; i < n-1; i++) {
            for (int j = 1; j < k+1; j++) {
                if (n <= i+j) {
                    continue;
                }
                dp[i+j] = Math.min(dp[i] + Math.abs(a[i] - a[i+j]), dp[i+j]);
            }
        }

        System.out.println(dp[n-1]);
        sc.close();
    }
}


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

using namespace std;

void dfs(int node, vector<vector<int>>& tree, vector<int>& d2){
  for(int next : tree[node]){
    if(d2[next] == -1){
      d2[next] = d2[node] ^ 1;
      dfs(next, tree, d2);
    }
  }
}

int main(){
  int N;
  cin >> N;
  
  vector<vector<int>> tree(N);
  for(int i = 0; i < N - 1; i++){
    int a, b;
    cin >> a >> b;
    a--; b--;
    
    tree[a].push_back(b);
    tree[b].push_back(a);
  }
  
  vector<int> d2(N, -1);
  d2[0] = 0;
  dfs(0, tree, d2);
  
  int yi = 0, ling = 0;
  queue<int> zero, one, two;
  for(int i = 0; i < N; i++){
    if(d2[i]) yi++;
    else ling++;
    
    if((i + 1) % 3 == 0) zero.push(i + 1);
    else if((i + 1) % 3 == 1) one.push(i + 1);
    else two.push(i + 1);
  }
  
  vector<int> p(N, 0);
  if(3 * ling <= N){
    for(int i = 0; i < N; i++){
      if(!d2[i]){
        p[i] = zero.front();
        zero.pop();
      }
    }
    for(int i = 0; i < N; i++){
      if(!p[i]){
        if(!one.empty()){
          p[i] = one.front();
          one.pop();
        }else if(!two.empty()){
          p[i] = two.front();
          two.pop();
        }else{
          p[i] = zero.front();
          zero.pop();
        }
      }
    }
  }else if(3 * yi <= N){
    for(int i = 0; i < N; i++){
      if(d2[i]){
        p[i] = zero.front();
        zero.pop();
      }
    }
    for(int i = 0; i < N; i++){
      if(!p[i]){
        if(!one.empty()){
          p[i] = one.front();
          one.pop();
        }else if(!two.empty()){
          p[i] = two.front();
          two.pop();
        }else{
          p[i] = zero.front();
          zero.pop();
        }
      }
    }
  }else{
    for(int i = 0; i < N; i++){
      if(d2[i]){
        if(!one.empty()){
          p[i] = one.front();
          one.pop();
        }else{
          p[i] = zero.front();
          zero.pop();
        }
      }else{
        if(!two.empty()){
          p[i] = two.front();
          two.pop();
        }else{
          p[i] = zero.front();
          zero.pop();
        }
      }
    }
  }
  
  for(int i = 0; i < N - 1; i++) cout << p[i] << ' ';
  cout << p[N - 1] << endl;
  
  return 0;
}

Measured memory_bytes: 18560
#include <bits/stdc++.h>
typedef long long LL;
#define SORT(c) sort((c).begin(),(c).end())

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

using namespace std;

struct Unionfind {
  vector<int> size;
  vector<int> par;

  Unionfind( int n ) :  size(n, 1), par(n) {
    iota( par.begin() , par.end() , 0 );
  }

  int find( int x ) {
    if ( par[x] == x ) return x;
    return par[x] = find( par[x] );
  }

  bool unite( int x , int y ) {
    x = find(x);
    y = find(y);
    if ( x == y ) return false;

    if ( size[y] < size[x] ) swap( x , y );
    par[x] = y;
    size[y] += size[x];

    return true;
  }

  bool same( int x , int y ) {
    return find(x) == find(y);
  }
};

int main(void)
{
  
  for(;;){
    int n,m;
    cin >> n >> m;
    if(!n) return 0;
    vector<pair<int,pair<int,int> > > e(m);
    REP(i,m) cin >> e[i].second.first >> e[i].second.second >> e[i].first;
    SORT(e);
    int answer=1048576,prew=-1;
    for(;;){
      int ind=lower_bound(e.begin(),e.end(),make_pair(prew+1,make_pair(0,0)))-e.begin();
      Unionfind uf(n+1);
      if(ind==m) break;
      prew=e[ind].first;
      int tsize=1;
      bool flag=false;
      FOR(i,ind,m){
	if(uf.unite(e[i].second.first,e[i].second.second)) ++tsize;
	if(tsize==n){
	  answer=min(answer,e[i].first-e[ind].first);
	  flag=true;
	  break;
	}
      }
      if(!flag)break;
    }
    if(answer==1048576) cout << -1 << endl;
    else cout << answer << endl;
    
  }
}

Measured memory_bytes: 3068
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cctype>
using namespace std;
int map[26];
int main(void) {
	string s;
	cin >> s;
	s += s;
	string m;
	cin >> m;
	if (s.find(m) != string::npos) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}


Measured memory_bytes: 3204
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(a) (a).begin(),(a).end()
#define overload4(_1, _2, _3, _4, name, ...) name
#define rep1(n) for(ll i = 0;i < (n);i++)
#define rep2(i,n) for(ll i = 0;i < (n);i++)
#define rep3(i,a,b) for(ll i = (a);i < (b);i++)
#define rep4(i,a,b,c) for(ll i = (a);i < (b);i += (c))
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep1(n) for(ll i = (n)-1;i >= 0;i--)
#define rrep2(i,n) for(ll i = (n)-1;i >= 0;i--)
#define rrep3(i,a,b) for(ll i = (a)-1;i >= (b);i--)
#define rrep4(i,a,b,c) for(ll i = (a)-1;i >= (b);i -= (c))
#define rrep(...) overload4(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__)
const ll INF=1e18,MOD = 1e9+7;
const int iINF = 1e9;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int l,r,d,ans=0;
    cin>>l>>r>>d;
    rep(i,l,r+1)if(i%d==0)ans++;
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i,n) for (int i = 0; i < (n); ++i)
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;
int main(){
    int n,k,r,s,p,ret=0,cnt_r=0,cnt_s=0,cnt_p=0;
    cin >> n >> k >> r >> s >> p;
    string t;
    cin >> t;

    REP(i,n){
        if(i+k<n){
            if(t[i]==t[i+k]){
                t[i+k] = 'z'; // lose
            }
        }
        if(t[i]=='r'){
            cnt_r++;
        }else if(t[i]=='s'){
            cnt_s++;
        }else if(t[i]=='p'){
            cnt_p++;
        }
    }
    ret = (cnt_r * p) + (cnt_s * r) + (cnt_p * s);
    cout << ret << endl;
    return 0;
}

Measured memory_bytes: 512
def min(c1, c2, c3, c4)
    x = (c1 < c2) ? c1 : c2
    y = (c3 < c4) ? c3 : c4
    (x < y) ? x : y
end

def mp(n, a, b, c)
    if n == $N
        if min(a, b, c, c) > 0
            (a - $A).abs + (b - $B).abs + (c - $C).abs - 30
        else
            10000
        end
    else
        c1 = mp(n + 1, a, b, c)
        c2 = mp(n + 1, a + $l[n], b, c) + 10
        c3 = mp(n + 1, a, b + $l[n], c) + 10
        c4 = mp(n + 1, a, b, c + $l[n]) + 10

        min(c1, c2, c3, c4)
    end
end

$N, $A, $B, $C = gets.split.map!{|n| n.to_i}
$l = Array.new($N)

for i in 1..$N
    $l[i-1] = gets.to_i
end

puts mp(0, 0, 0, 0)

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

int main()
{
	long long n, m, l;
	cin >> n >> m >> l;
	vector<vector<long long>>v1(n, vector<long long>(m));
	for (long long i = 0; i < n; i++)
	{
		for (long long j = 0; j < m; j++)
		{
			cin >> v1[i][j];
		}

	}
	vector<vector<long long>>v2(m, vector<long long>(l));
	for (long long i = 0; i < m; i++)
	{
		for (long long j = 0; j < l; j++)
		{
			cin >> v2[i][j];
		}

	}
	vector<vector<long long>>v3(n, vector<long long>(l, 0));
	for (long long i = 0; i < n; i++)
	{
		for (long long j = 0; j < l; j++)

		{
			for (long long k = 0; k < m; k++)
			{
				v3[i][j] += v1[i][k] * v2[k][j];
			}
		}
	}
	for (long long i = 0; i < n; i++)
	{
		for (long long j = 0; j < l; j++)
		{
			cout << v3[i][j];
			if (j < l - 1)
			{
				cout << " ";
			}
		}
		cout << endl;
	}
	

}


Measured memory_bytes: 3284
from collections import deque
count = 0
s = deque(list(input()))
q = int(input())

for i in range(q):
  a = list(input().split())
  if a[0] == '1':
    count += 1
    continue
    
  if count%2 == 0:
    if a[0] == '2':
      if a[1] == '1':
        s.appendleft(a[2])
      elif a[1] == '2':
        s.append(a[2])
        
  if count%2 == 1:
    if a[0] == '2':
      if a[1] == '1':
        s.append(a[2])
      elif a[1] == '2':
        s.appendleft(a[2])
      
ans = ''.join(s)
print(ans if count%2 == 0 else ''.join(list(reversed(ans))))

Measured memory_bytes: 8804
n, k = map(int, input().split())
a = list(map(int, input().split()))
m = sum(a)

def divisor(n):
    ass = []
    for i in range(1, int(n**0.5)+1):
        if n%i == 0:
            ass.append(i)
            ass.append(n//i)
    return ass
f = divisor(m)
f.sort(reverse=True)

for p in f:
  b = [x%p for x in a]
  b.sort()
  t = 0
  c = n
  for x in b:
    if x + t > k:
      break
    t += x
    c -= 1
  if c*p - sum(b) + t <= k:
    print(p)
    break

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

int main() {
  int A, B, C, D;
  cin >> A >> B >> C >> D;

  if ( A + B > C + D ) {
    cout << "Left" << endl;
  }
  else if (A + B < C + D ){
    cout << "Right" << endl;
  }
  else {
    cout << "Balanced" << endl;
  }
}
  


Measured memory_bytes: 256
n,m = gets.split.map(&:to_i)

s = Array.new(n+1){[]}
m.times do
    a,b = gets.split.map(&:to_i)
    s[a] << b
    s[b] << a
end

s[1].each do |e|
    if s[e].include?(n)
        puts "POSSIBLE"
        exit
    end
end

puts "IMPOSSIBLE"

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

const int N = 4;
const int LIMIT = 100;
int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
int limit;
int puz[N*N];
int zero;
int esti;
int MDT[N*N][N*N];

int dfs(int dep, int pre) {
	if ( esti == 0 ) return dep;
	if ( dep+esti >= limit ) return LIMIT;	

	int ret = LIMIT;
	for ( int i = 0; i < 4; i++ ) {
		if ( (i+2)%4 == pre ) continue;
		int y = zero/N, x = zero%N;
		int ny = y+dy[i], nx = x+dx[i];
		if ( ny < 0 || nx < 0 || ny >= N || nx >= N ) continue;
		int tmp[N*N];
		int tmp_zero  = zero;
		int tmp_esti = esti;		
		for ( int j = 0; j < N*N; j++ ) tmp[j] = puz[j];
		int ch_id = ny*N+nx;
		int ch_dat = puz[ch_id];		
		esti -= MDT[zero][N*N-1];
		esti -= MDT[ny*N+nx][ch_dat];
		esti += MDT[zero][ch_dat];
		esti += MDT[ny*N+nx][N*N-1];
		swap(puz[zero], puz[ch_id]);
		zero = ch_id;		
		ret = min(ret, dfs(dep+1, i));
		for ( int j = 0; j < N*N; j++ ) puz[j] = tmp[j];
		zero = tmp_zero;
		esti = tmp_esti;		
	}

	return ret;
}

int main() {
	for ( int i = 0; i < N*N; i++ ) {
		for ( int j = 0; j < N*N; j++ ) {
			MDT[i][j] = abs(i/N-j/N) + abs(i%N-j%N);            
		}
	}

	for ( int i = 0; i < N*N; i++ ) {		
		cin >> puz[i];
		if ( puz[i] == 0 ) {
			zero = i;
			puz[i] = N*N-1;			
		} else {
			puz[i]--;
		}
		esti += abs(i/N-puz[i]/N) + abs(i%N-puz[i]%N);        
	}

	for ( int i = esti; i <= LIMIT; i++ ) {
		limit = i;
		int ans = dfs(0, -1);
		if ( ans < 100 ) {
			cout << ans << endl;
			break;
		}
	}
	
	return 0;
}



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

#define ll long long
#define vi vector<int>
#define pb push_back
#define P pair<int,int>
#define PP pair<P,int>
#define fi first
#define se second
#define INF (1<<30)
#define MOD 1000000007
#define all(a) (a).begin(),(a).end()


signed main(){
    string st;
    cin>>st;
    for(int i=0;i<st.length();i+=2){
        cout<<st[i];
    }cout<<endl;
    return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <string.h>
#include <algorithm>
#include <vector>
#include <math.h>
#include <queue>
#include <stack>
using namespace std;
int main(void){
    int s;
    cin>>s;
    int check[1000001];
    for(int i=0;i<1000001;i++){
        check[i]=0;
    }
    bool judge=false; int anow=0; int abef=s; int count=1;
    check[s]=1;
    while(!judge){
      count++;
      if(abef%2==0){anow=abef/2;}
      else {anow=abef*3+1;}
      if(check[anow]==0){check[anow]=1;}
      else {judge=true; break;}
      abef=anow;
    }
    cout<<count;
    return 0;
}

Measured memory_bytes: 4096
from itertools import permutations

N = int(input())
P = list(map(int,input().split()))
Q = list(map(int,input().split()))

ls = list(permutations(range(1,N+1)))
tup_p = tuple(P)
tup_q = tuple(Q)

print(abs(ls.index(tup_p)-ls.index(tup_q)))

Measured memory_bytes: 44784
#include <iostream>
#include <algorithm>
#include <memory.h>
using namespace std;

int main() {
    int x, n;
    scanf("%d %d", &x, &n);
    int p[200];
    int nMin = 100000;
    int nMinTmp = 1000000;
    int vis[200];
    memset(vis, 0, sizeof(vis));
    for(int i=0; i<n; i++) {
        scanf("%d", &p[i]);
        vis[p[i]] = 1;
    }
    for(int i=0; i<=150; i++) {
        if(vis[i] == 0 && abs(i - x) <= nMinTmp) {
            if(abs(i - x) == nMinTmp) {
                if(nMin > i) {
                    nMin = i;
                }
            }
            else {
                nMin = i;
                nMinTmp = abs(i - x);
            }
            
        }
    }
    
    printf("%d\n", nMin);
    return 0;
}

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

#define PI 3.14159265359
#define rep(i,a,n) for(int i=a;i<(int)n;++i)
#define SZ(x) ((int)(x).size())	//size() unsigned -> int
#define descSort(a) sort(a.begin(),a.end(),std::greater<int>())
using namespace std;
typedef long long ll;
const ll INF = 1e9 + 7;

int main() {
    string s;
    cin>>s;
    int cnt=count(s.begin(),s.end(),'o');
    if(cnt>=8 || (15-s.size()+cnt >=8))cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}

Measured memory_bytes: 3560
#include<stdio.h>
#define N 1000

int main(void){
  int i,num,j,k;
  int n,c2[N],c5[N],ans[N];
  int j2,j5,c;

  for(i=0;;i++){
    c2[i]=0;
    c5[i]=0;
    scanf("%d",&n);
    if(n==0)
      break;
    for(j=1;j<=n;j++){
      c=0;
      j2=j;
      for(;;){
        if(j2%2==0){
          c++;
          j2/=2;
        }else{
          break;
        }
      }
      c2[i]+=c;
      c=0;
      j5=j;
      for(;;){
        if(j5%5==0){
          c++;
          j5/=5;
        }else{
          break;
        }
      }
      c5[i]+=c;
    }
  }
  num=i;
  for(i=0;i<num;i++){
    if(c2[i]<=c5[i]){
      printf("%d\n",c2[i]);
    }else if(c2[i]>c5[i]){
      printf("%d\n",c5[i]);
    }
  }
  return 0;
}

Measured memory_bytes: 0
using System;

class Program
{
    static void Main(string[] args)
    {
        var n = int.Parse(Console.ReadLine());

        if (n % 111 == 0)
        {
            Console.WriteLine(n);
        }
        else
        {
            Console.WriteLine((n / 111 + 1) * 111);
        }
    }
}

Measured memory_bytes: 11092
h,w=map(int,input().split())
s=[]
l=[[0 for i in range(w)]for j in range(h)]
 
for i in range(h):
    a=input()
    s.append(a)

yoko=[[0 for j in range(w)] for j in range(h)]
tate=[[0 for j in range(w)] for j in range(h)]

for i in range(h):
    p=0
    for j in range(w):
        if s[i][j]=="#" or j==w-1:
            if s[i][j]==".":
                for k in range(p):
                    yoko[i][j-k-1]+=p+1
                yoko[i][j]+=p+1
            else:
                for k in range(p):
                    yoko[i][j-k-1]+=p
            p=0
        elif s[i][j]==".":
            p+=1
for i in range(w):
    p=0
    for j in range(h):
        if s[j][i]=="#" or j==h-1:
            if s[j][i]==".":
                for k in range(p):
                    tate[j-k-1][i]+=p+1
                yoko[j][i]+=p+1
            else:
                for k in range(p):
                    tate[j-k-1][i]+=p
            p=0
        elif s[j][i]==".":
            p+=1
ans=0
for i in range(h):
    for j in range(w):
        ans=max(ans,yoko[i][j]+tate[i][j]-1)

print(ans)







Measured memory_bytes: 153864