akhauriyash/Code-Regression huggingface dataset:
// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

const long long MOD = 1000000007;
const i64 INF = i64(1e18) + 7;


template <typename T>
bool chmin(T& x, T y){
    if(x > y){
        x = y;
        return true;
    }
    return false;
}

template <typename T>
bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}

template <i64 mod = MOD>
struct ModInt{
    i64 p;

    ModInt() : p(0){}
    ModInt(i64 x){p = x >= 0 ? x % mod : x + (-x + mod - 1) / mod * mod;}

    ModInt& operator+=(const ModInt& y){p = p + *y - ((p + *y) >= mod ? mod : 0); return *this;}
    ModInt& operator-=(const ModInt& y){p = p - *y + (p - *y < 0 ? mod : 0); return *this;}
    ModInt& operator*=(const ModInt& y){p = (p * *y) % mod; return *this;}
    ModInt& operator%=(const ModInt& y){if(y)p %= *y; return *this;}

    ModInt operator+(const ModInt& y) const{ModInt x = *this; return x += y;}
    ModInt operator-(const ModInt& y) const{ModInt x = *this; return x -= y;}
    ModInt operator*(const ModInt& y) const{ModInt x = *this; return x *= y;}
    ModInt operator%(const ModInt& y) const{ModInt x = *this; return x %= y;}

    friend ostream& operator<<(ostream& stream, const ModInt<mod>& x){
        stream << *x;
        return stream;
    }

    friend ostream& operator>>(ostream& stream, const ModInt<mod>& x){
        stream >> *x;
        return stream;
    }

    ModInt& operator++(){p = (p + 1) % mod; return *this;}
    ModInt& operator--(){p = (p - 1 + mod) % mod; return *this;}

    bool operator==(const ModInt& y) const{return p == *y;}
    bool operator!=(const ModInt& y) const{return p != *y;}

    const i64& operator*() const{return p;}
    i64& operator*(){return p;}

};

using mint = ModInt<>;


void solve(long long n, std::vector<long long> a){
    vector<i64> cnt(63, 0);

    mint ans = 0;
    int i = 0;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < 63; ++j){
            bool fl = ((a[i] >> j) & 1);
            i64 c = fl ? (i - cnt[j]) : cnt[j];
            ans += mint(c) * mint(1LL << j);
            if(fl)
                ++cnt[j];
        }
    cout << *ans << endl;
}


signed main(){
    long long N;
    scanf("%lld",&N);
    std::vector<long long> A(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&A[i]);
    }
    solve(N, std::move(A));
    return 0;
}


Measured memory_bytes: 2560
#include <cstdio>

using ll = long long;

ll K;

void solve() {
	for (int N = 2; N <= 50; N++) {
		ll a[51];
		
		ll d = K / N;
		ll r = K % N;
		for (int i = 1; i <= N; i++) {
			a[i] = N - 1;

			if (i <= r) {
				a[i] += N * (d + 1);
				a[i] -= (K - (d + 1));
			} else {
				a[i] += N * d;
				a[i] -= K - d;
			}
		}

		bool valid = true;
		for (int i = 1; i <= N; i++) {
			if (a[i] < 0 || a[i] > 10000000000000000ll + 1000ll) {
				valid = false;
			}
		}

		if (!valid) {
			continue;
		}

		printf("%d\n", N);
		for (int i = 1; i <= N; i++) {
			printf("%lld%s", a[i], i == N ? "\n" : " ");
		}
		return;
	}
}

int main() {
	scanf("%lld", &K);
	solve();
	return 0;
}



Measured memory_bytes: 128
using System.Linq;
using System.Collections.Generic;
using System;

public class hello
{
    public static void Main()
    {
        var a = new List<int>();
        var a2 = new List<int>();
        var b = new List<int>();
        var b2 = new List<int>();
        var s = Console.ReadLine().Trim();
        for (int i = 0; i < s.Length; i++)
        {
            if (i % 2 == 0)
            {
                var ww = int.Parse(s[i].ToString());
                a.Add(ww); a2.Add(ww);
            }
            else if (s[i] == '+') { b.Add(0); b2.Add(0); }
            else { b.Add(1); b2.Add(1); }
        }
        var norm = getNomal(a, b);
        var left = getFromLeft(a2, b2);
        var bob = int.Parse(Console.ReadLine().Trim());
        string res;
        if (bob == norm && bob != left) res = "M";
        else if (bob != norm && bob == left) res = "L";
        else if (bob == norm && bob == left) res = "U";
        else res = "I";
        Console.WriteLine(res);
    }
    public static int getFromLeft(List<int> a, List<int> b)
    {
        for (int i = 0; i < b.Count(); i++)
        {
            if (b[i] == 0) a[i + 1] += a[i];
            else a[i + 1] *= a[i];
        }
        return a[a.Count() - 1];
    }
    public static int getNomal(List<int> a, List<int> b)
    {
        while (true)
        {
            if (b.Sum() == 0) return a.Sum();
            for (int i = 0; i < b.Count(); i++)
                if (b[i] == 1)
                {
                    a[i] *= a[i + 1];
                    a.RemoveAt(i + 1);
                    b.RemoveAt(i);
                }
        }
    }
}


Measured memory_bytes: 8112
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr long long MOD = 1000000007;
int main(){
ll n;
string s;
cin >> n >> s;
ll r,g,b;
r = count(s.begin(), s.end(), 'R');
g = count(s.begin(), s.end(), 'G');
b = count(s.begin(), s.end(), 'B');
ll ans = r * g * b;
for (ll i = 0; i < n;i++){
    for (ll j = i+1; j < n;j++){
        ll k = 2 * j - i;
        if (k >= n) continue;
        if (s[i] != s[j] && s[i] != s[k] && s[j] != s[k]) ans--;
    }
}
cout << ans << endl;
}

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


int main(){
    string n;
    cin >> n;
    ll naive = 0;
    rep(i, 0, n.size()){
        naive += (n[i]-'0');
    }
    if(n.size() > 1){
        cout << max(naive, (ll)((ll)(n[0]-'0'-1)+9*(n.size()-1))) << endl;
    }else{
        cout << n[0] << endl;
    }
    return 0;
}

Measured memory_bytes: 256
// ABC057
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

#define INF 1000000000

using namespace std;

int nd(int a)
{
    int n = 0;
    while (1)
    {
        n++;
        a /= 10;
        if(a == 0) break;
    }

    return n;
}

int f(int a, int b)
{
    return max(nd(a), nd(b));
}


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

    for(int i = sqrt(n); i >= 1; i--)
    {
        if(n % i == 0)
        {
            div = i;
            break;
        }
    }

    cout << f(div, n/div) << endl;

    return 0;
}


Measured memory_bytes: 256
fun main(args: Array<String>) {
    val n = readInt()
    val a = List(n) { readInt() }
    val max = a.max()!!
    if (a.count { it == max } >= 2) {
        repeat(n) {
            println(max)
        }
        return
    }

    val next = a.filter { it != max }.max()!!
    for (i in 0 until n) {
        when (a[i]) {
            max -> println(next)
            else -> println(max)
        }
    }
}

// Tools
fun readString() = readLine()!!
fun readInt() = readLine()!!.toInt()

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

int main(){

  int n;

  while(cin>>n){
    int cnt=0;

    for(int i=0;i<=9;++i){
      for(int j=0;j<=9;++j){
        for(int k=0;k<=9;++k){
          if(n-i-j-k<10&&n-i-j-k>=0) ++cnt;
        }
      }
    }

    cout<<cnt<<endl;
  }

  return EXIT_SUCCESS;
}

Measured memory_bytes: 1160
import java.util.*;
import static java.lang.System.*;
import static java.lang.Math.*;
public class Main {
public static void main(String[] args){
Scanner sc = new Scanner(in);
String s = sc.next();
long k = sc.nextLong();
int temp=0;
char p='1';
for (int i = 0; i < s.length(); i++) {
    if(s.charAt(i)!='1'){
        p=s.charAt(i);break;
    }
    temp++;
}
if(temp>=k){
    out.println(1);
}else{
    out.println(p);
}
}}

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

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

	vector<int> dp(n, 0);
	dp[0] = 0; dp[1] = abs(h[1] - h[0]);
	for (int i = 2; i < n; i++) {
		dp[i] = min(dp[i-2] + abs(h[i] - h[i-2]), dp[i-1] + abs(h[i] - h[i-1]));
	}

	cout << dp[n-1] << endl;

	return 0;
}


Measured memory_bytes: 1024
import java.awt.*;
import java.io.*;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
import java.util.HashMap;
import java.util.Map;
import java.util.LinkedList;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int w=sc.nextInt();
        int[] a=new int[n+1];
        int[] b=new int[n+1];

        for(int i=1;i<=n;i++){
            a[i]=sc.nextInt();
            b[i]=sc.nextInt();
        }
        long[][] dp=new long[n+1][w+1];

        for(int i=1;i<=n;i++){
            for(int j=1;j<=w;j++){
                if(j<a[i])dp[i][j]=dp[i-1][j];
                else dp[i][j]=Long.max(b[i]+dp[i-1][j-a[i]],dp[i-1][j]);
            }
        }
        System.out.println(dp[n][w]);

    }
}



Measured memory_bytes: 127956
void main(){
  import std.stdio, std.string, std.conv, std.algorithm, std.math;

  long q, h, s, d; rd(q, h, s, d);
  long n; rd(n);

  s=min(s, 2*h, 4*q);
  long c=n*s;
  if(n%2==0){
    c=min(c, n/2*d);
  }else{
    c=min(c, s+(n-1)/2*d);
  }

  writeln(c);
}

void rd(T...)(ref T x){
  import std.stdio, std.string, std.conv;
  auto l=readln.split;
  foreach(i, ref e; x){
    e=l[i].to!(typeof(e));
  }
}

Measured memory_bytes: 256
s = input()
rs = s[::-1]
for i in range(8):
    #print(s[:i], s[len(s)-(7-i):], s[:i]+s[len(s)-(7-i):])
    if s[:i]+s[len(s)-(7-i):] == 'keyence':
        print('YES')
        exit(0)
print('NO')


Measured memory_bytes: 2940
# 参考・参照サイト https://ikatakos.com/pot/programming_algorithm/contest_history/atcoder/2019/0106_educational_dp_2
# 学習を目的として上記サイトを参考に、セグメント木の箇所をBinary Index Treeに変更し、動作確認をさせていただきました。

# メモ：高さの低い順に美しさの総和の最大値が確定される


# require 'pry'
N = gets.to_i
ind = -1
height = gets.split.map do |high|
  ind += 1
  t = high.to_i
  [t, ind]
end

beauty = gets.split.map(&:to_i)

@data = Array.new(N+1, 0)

def update(k, x)
  while k <= N
    if @data[k] < x
      @data[k] = x
    else
      break
    end
    k += k & -k
  end
end


def get_max(k)
  ret = @data[k]
  while k > 0
    ret = @data[k] if ret < @data[k]
  k -= k & -k
  end
  return ret
end

# 高さの昇順でソート
srt = height.sort_by{|x|x[0]}

srt.each do |h, i|
  # 左端〜i番目間の最大値(高さh未満)
  # →高さが低い順なので、現在の高さより大きい花の美しさは反映されていない
  # BITは1origin(BITは先頭の要素を使用しない為)
  max_i = get_max(i+1)
  update(i+1 , max_i + beauty[i])
end

# 全区間における最大値が解答
puts get_max(N)

Measured memory_bytes: 44472
// #include {{{
#include <iostream>
#include <cassert>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <ctime>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <bitset>
#include <vector>
#include <complex>
#include <algorithm>
using namespace std;
// }}}
// #define {{{
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define de(x) cout << #x << "=" << x << endl
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define per(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
// }}}

const int N = 1e5 + 10;
struct ele{
    int x,y,z;
    bool operator < (const ele&b) const {
        return x+b.y>y+b.x;
    }
    void read(){
        scanf("%d%d%d",&x,&y,&z);
    }
};
int x,y,z,n;
ele p[N];
ll lft[N];

int main(){
    scanf("%d%d%d",&x,&y,&z);
    n=x+y+z;
    rep(i,0,n) p[i].read();
    ll ans=-1e18,sumc=0;
    rep(i,0,n) sumc+=p[i].z,p[i].x-=p[i].z,p[i].y-=p[i].z;
    sort(p,p+n);
    ll tmp=0;
    priority_queue<int> Q;
    //rep(i,0,n) cout << p[i].x << " " << p[i].y << " " << p[i].z << endl;
    rep(i,0,n) {
        Q.push(-p[i].x);tmp+=p[i].x;
        if(sz(Q)>x) tmp+=Q.top(),Q.pop();
        if(sz(Q)==x) lft[i+1]=tmp;
    }
    while(sz(Q)) Q.pop();
    tmp=0;
    per(i,0,n) {
        Q.push(-p[i].y);tmp+=p[i].y;
        if(sz(Q)>y) tmp+=Q.top(),Q.pop();
        if(sz(Q)==y&&i>=x) ans=max(ans,tmp+lft[i]);
    }
    printf("%lld\n",ans+sumc);
    return 0;
}


Measured memory_bytes: 2812
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i <= n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define VSORTR(v) sort(v.rbegin(), v.rend());
#define ALL(v) (v).begin(),(v).end()
 
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;

const ll mod = 1e9 + 7;

vll dijkstra(vvll &e, ll s) {
    ll n = e.size();
    vll d(n), used(n);
    queue<ll> que;
    d[s] = 0;
    used[s] = 1;
    que.push(s);
    while (!que.empty()) {
        ll cur = que.front();
        que.pop();
        for (auto nxt : e[cur]) {
            if (used[nxt]) continue;
            d[nxt] = d[cur] + 1;
            que.push(nxt);
            used[nxt] = 1;
        }
    }
    return d;
}

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

    ll n, u, v;
    cin >> n >> u >> v;
    u--, v--;
    ll a, b;
    vvll e(n);
    REP(i, n - 1) {
        cin >> a >> b;
        a--, b--;
        e[a].push_back(b);
        e[b].push_back(a);
    }
    vll du = dijkstra(e, u), dv = dijkstra(e, v);
    if (dv[u] == 1 && e[u].size() == 1) {
        cout << 0 << endl;
        return 0;
    }

    ll res = dv[u] - 1;
    REP(i, n) {
        if (dv[i] >= du[i]) res = max(res, dv[i] - 1);
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 8816
#pragma region template
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vld = vector<ld>;
using vvld = vector<vld>;
using vvvld = vector<vvld>;
using vs = vector<string>;
using pll = pair<ll, ll>;
using vp = vector<pll>;
template <typename T>
using pqrev = priority_queue<T, vector<T>, greater<T>>;
#define rep(i, n) for (ll i = 0, i##_end = (n); i < i##_end; i++)
#define repb(i, n) for (ll i = (n)-1; i >= 0; i--)
#define repr(i, a, b) for (ll i = (a), i##_end = (b); i < i##_end; i++)
#define reprb(i, a, b) for (ll i = (b)-1, i##_end = (a); i >= i##_end; i--)
#define ALL(a) (a).begin(), (a).end()
#define SZ(x) ((ll)(x).size())
//*
constexpr ll MOD = 1e9 + 7;
/*/
constexpr ll MOD = 998244353;
//*/
constexpr ll INF = 1e+18;
constexpr ld EPS = 1e-12L;
constexpr ld PI = 3.14159265358979323846L;
constexpr ll GCD(ll a, ll b) { return b ? GCD(b, a % b) : a; }
constexpr ll LCM(ll a, ll b) { return a / GCD(a, b) * b; }
template <typename S, typename T>
inline bool chmax(S &a, const T &b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <typename S, typename T>
inline bool chmin(S &a, const T &b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
#ifdef OJ_LOCAL
#include "dump.hpp"
#else
#define dump(...) ((void)0)
#endif
template <typename T>
bool print_(const T &a) {
  cout << a;
  return true;
}
template <typename T>
bool print_(const vector<T> &vec) {
  for (auto &a : vec) {
    cout << a;
    if (&a != &vec.back()) {
      cout << " ";
    }
  }
  return false;
}
template <typename T>
bool print_(const vector<vector<T>> &vv) {
  for (auto &v : vv) {
    for (auto &a : v) {
      cout << a;
      if (&a != &v.back()) {
        cout << " ";
      }
    }
    if (&v != &vv.back()) {
      cout << "\n";
    }
  }
  return false;
}
void print() { cout << "\n"; }
template <typename Head, typename... Tail>
void print(Head &&head, Tail &&... tail) {
  bool f = print_(head);
  if (sizeof...(tail) != 0) {
    cout << (f ? " " : "\n");
  }
  print(forward<Tail>(tail)...);
}
#pragma endregion

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(20);
  int n, k;
  cin >> n >> k;
  if(k > (n+1)/2){
    print(-1);
    return 0;
  }
  vvi ans;
  if(n%2){
    int cnt = 2*n;
    for(int i = 0, j = 2*n-(n+1)/2; i < j; i += 2, j--){
      ans.emplace_back(vi{i, j, cnt});
      cnt++;
    }
    for(int i = 1, j = 2*n-1; SZ(ans) < n; i += 2, j--){
      ans.emplace_back(vi{i, j, cnt});
      cnt++;
    }
    rep(i, n)rep(j, 3) ans[i][j] += k;
    print(ans);
  }else{
    int cnt = 2*n;
    ans.emplace_back(vi{0, n, cnt});
    cnt++;
    for(int i = 1, j = n*3/2; i < j; i += 2, j--){
      ans.emplace_back(vi{i, j, cnt});
      cnt++;
    }
    for(int i = 2, j = 2*n-1; SZ(ans) < n; i += 2, j--){
      ans.emplace_back(vi{i, j, cnt});
      cnt++;
    }
    rep(i, n)rep(j, 3) ans[i][j] += k;
    print(ans);
  }
}


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

int main(){
	long long A;
	string B;
	cin >> A >> B;
	long long BB=0;
	BB+=(B[0]-'0')*100+(B[2]-'0')*10+(B[3]-'0');
	
	cout << A*BB/100 << endl;
	return 0;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define REP(i,n) for(int64_t i=0;i<(n);i++)
#define ALL(a)  (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define REV(c) reverse((c).begin(),(c).end())
#define YES cout << "YES" << endl;
#define NO cout << "NO" << endl;
#define Yes cout << "Yes" << endl;
#define No cout << "No" << endl;
#define COUTDOUBLE(d,i) cout << setprecision((i)) << (d) << endl;
#define VIN(n,v) for(int64_t i=0;i<(n);i++){cin >> (v).at(i);}

using namespace std;
typedef int64_t I;
typedef pair<I,I> P;
typedef vector<I> V;

I MOD = pow(10,9)+7;
I MAX = LONG_MAX;

// 最大公約数
I gcd(I a, I b) {
  return b != 0 ? gcd(b, a % b) : a;
}

// 最小公倍数
I lcm(I a, I b) {
  return a * b / gcd(a, b);
}

int ctoi(char c){
  return c - '0';
}

int main(){
  I n,a,b,c,d,e;
  cin >> n >> a >> b >> c >> d >> e;
  I mi = MAX;
  mi = min(a,mi);
  mi = min(b,mi);
  mi = min(c,mi);
  mi = min(d,mi);
  mi = min(e,mi);
  I t;
  if (n > mi){
    t = n / mi;
    if (n % mi != 0){
      t++;
    }
  }else{
    t = 1;
  }
  cout << t + 4 << endl;
  return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#define rep(i, n) for(int i=0;i<n;i++)
using namespace std;
int main(){
	int a;
	cin>>a;
	string s;
	cin>>s;
	if(a%2==1){
		cout<<"No"<<endl;
		return 0;
	}
	bool f=0;
	rep(i, a/2){
		if(s[i]!=s[a/2+i])
			f=1;
	}
	if(f==0)
		cout<<"Yes"<<endl;
	else
		cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
	int a;
	for (;;){
		cin>>a;
		if (a==0)break;
		int b[a]={0},rikuto=0,goukei=0;
		char c;
		
		while(goukei!=100){
			for (int B=0;B<a;B++){
				cin>>c;
				if (c=='M') b[B]++;
				if (c=='S'){
					b[B]++;
					rikuto+=b[B];
					b[B]=0;
				}
				if (c=='L'){
					b[B]++;
					b[B]+=rikuto;
					rikuto=0;
				}
				goukei++;
				if (goukei>=100) break;
			}
		}
		sort(b,b+a);
		for (int A=0;A<a-1;A++) cout<<b[A]<<" ";
		cout<<b[a-1]<<" "<<rikuto<<endl;
	}
	return 0;
}

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

using namespace std;

typedef long long ll;

const ll MOD = 1000000007;

const int MAX_N = 500;
ll num[MAX_N][MAX_N];
// start -> end
ll ans[MAX_N+1][MAX_N+1];

int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  int n, m, q; cin >> n >> m >> q;
  for(int i=0;i<m;i++){
    int l, r; cin >> l >> r;
    num[l-1][r-1]++;
  }
  for(int i=0;i<n;i++){
    for(int j=i;j<n;j++){
      if(num[i][j] == 0) continue;
      // cout << i << " " << j << endl;
      // cout << 0 << " " << j << " , " << i+1 << " " << j << endl;
      ans[0][j] += num[i][j];
      ans[i+1][j] += (-1)*num[i][j];
    }
  }

  // sum by i
  for(int i=0;i<n;i++){
    for(int j=1;j<n;j++){
      ans[i][j] += ans[i][j-1];
    }
  }
  // sum by j
  for(int j=0;j<n;j++){
    for(int i=1;i<n;i++){
      ans[i][j] += ans[i-1][j];
    }
  }
  for(int i=0;i<q;i++){
    int a, b; cin >> a >> b;
    cout << ans[a-1][b-1] << endl;
  }
}

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

int digit(int x){
    int keta=0;
    while(x){
        keta++;
        x /= 10;
    }
    return keta;
}

int main(){
    int n;
    cin >> n;
    int count=0;
    for(int i=1;i<=n;i++){
        if(digit(i) %2 == 1)count++;
    }
    cout << count << endl;
}

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

typedef long long  ll;

ll MOD = 1000000007;
ll INF = 10000000000000000;
double PI = 3.1415926535;

ll ceiling(ll a,ll b){
  if(a % b == 0){
    return a / b;
  }else{
    return (a / b) + 1;
  }
}

template<typename T>
void remove(std::vector<T>& vector, unsigned int index)
{
    vector.erase(vector.begin() + index);
}

using Graph = vector<vector<ll>>;

int main(){
  ll K;cin >> K;
  vector<ll> A(K);
  for(ll i = 0;i < K;i++){
    cin >> A[i];
  }
  reverse(A.begin(),A.end());
  ll min = 2;
  ll max = 3;
  for(ll i = 0;i < K;i++){
    if(i == 0){
      if(A[i] != 2){
        cout << -1 << endl;
        return 0;
      }
    }else{
      if(max < A[i]){
        cout << -1 << endl;
        return 0;
      }
      min = ceiling(min,A[i]) * A[i];
      if(min > max){
        cout << -1 << endl;
        return 0;
      }
      max = (max / A[i]) * A[i] + (A[i]-1);
    }
  }
  cout << min << ' ' << max << endl;
}

Measured memory_bytes: 1024
import math
from functools import reduce

k = int(input())
ans = 0

def gcd(*numbers):
    return reduce(math.gcd, numbers)

for a in range(1, k+1):
  for b in range(1, k+1):
    for c in range(1, k+1):
      ans += gcd(a, b, c)
      
print(ans)

Measured memory_bytes: 69456
#include<iostream>
#include<vector>
#include<string>
#include<map>
using namespace std;

string str[20];
vector<int> va[20];
map<string,string> piyo;
int n,m,p;

vector<int> formula(string s);

vector<int> factor(string s){
  if(s[0]!='('){
    string stri=piyo[s];
    for(int i=m-1;i>=0;--i){
      if(str[i]==stri){
	return va[i];
      }
    }
  }
  return formula(s.substr(1,s.size()-2));
}

vector<int> term(string s){
  int k=0;
  int size=s.size();
  for(int i=size-1;i>=0;--i){
    if(s[i]=='(')++k;
    if(s[i]==')')--k;
    if(s[i]=='*'){
      if(k==0){
	vector<int> left=formula(s.substr(0,i));
	vector<int> right=formula(s.substr(i+1,size-i-1));
	vector<int> res(n);
	if(left.size()==0)return left;
	if(right.size()==0)return right;
	for(int j=0;j<n;++j){
	  res[j]=left[j]+right[j];
	}
	return res;
      }
    }
    if(s[i]=='/'){
      if(k==0){
	vector<int> left=formula(s.substr(0,i));
	vector<int> right=formula(s.substr(i+1,size-i-1));
	vector<int> res(n);
	if(left.size()==0)return left;
	if(right.size()==0)return right;
	for(int j=0;j<n;++j){
	  res[j]=left[j]-right[j];
	}
	return res;
      }
    }
  }
  return factor(s);
}

vector<int> formula(string s){
  int k=0;
  int size=s.size();
  for(int i=0;i<size;++i){
    if(s[i]=='(')++k;
    if(s[i]==')')--k;
    if(s[i]=='+'||s[i]=='-'){
      if(k==0){
	vector<int> left=formula(s.substr(0,i));
	vector<int> right=formula(s.substr(i+1,size-i-1));
	if(left.size()==0)return left;
	if(right.size()==0)return right;
	for(int j=0;j<n;++j){
	  if(left[j]!=right[j]){
	    vector<int> res;
	    return res;
	  }
	}
	return left;
      }
    }
  }
  return term(s);
}

int main(){
  for(;;){
    cin>>n>>m>>p;
    if(n==0&&m==0&&p==0)break;
    int i;
    for(i=0;i<m;++i){
      cin>>str[i];
      int j;
      va[i].clear();
      for(j=0;j<n;++j){
	int v;
	cin>>v;
	va[i].push_back(v);
      }
    }
    string hoge;
    cin>>hoge;
    piyo.clear();
    for(i=0;i<p;++i){
      string str1,str2;
      cin>>str1>>str2;
      piyo[str1]=str2;
    }
    vector<int> res=formula(hoge);
    if(res.size()==0){
      cout<<"error"<<endl;
      continue;
    }
    for(i=m-1;i>=0;--i){
      for(int j=0;j<n;++j){
	if(res[j]!=va[i][j])goto bbb;
      }
      cout<<str[i]<<endl;
      goto aaa;
    bbb:;
    }
    cout<<"undefined"<<endl;
  aaa:;
  }
  return 0;
}

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

int main(void){
   int n;
   cin >> n;
   map<string,bool> mp;
   for(int i=0;i<n;i++){
       string s;
       cin >> s;
       if(mp[s]==false)mp[s] = true;
       else mp[s] = false;
   }
   int count = 0;
   for(auto itr = mp.begin(); itr != mp.end(); ++itr) {
       if(itr->second)count++;
   }
   cout << count << endl;
}


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

using namespace std;
typedef long long ll;
int n, m;
struct node{
    int S, E;
};
node arr[100005];
bool cmp(node &a, node &b){
    return a.E < b.E;
}

int main()

{
    ios_base::sync_with_stdio(false);
    cin >> n >> m;
    vector<pair<int, int> > v;
    int a, b;
    for(int i = 0; i < m; i ++){
        cin >> arr[i].S >> arr[i].E;
    }
    sort(arr, arr + m, cmp);
    int prev = arr[0].E;
    int ret = 1;
    for(int i = 1; i < m; i ++){
        if(arr[i].S >= prev){
            prev = arr[i].E;
            ret ++;
        }
    }
    printf("%d\n", ret);
    return 0;
}


Measured memory_bytes: 1024
import java.util.Scanner;


public class Main {

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

		int m = sc.nextInt();
		
		int l = sc.nextInt();
		
		//n：Aの縦 m：Aの横Bの縦 l：Bの横
		
		int[][] A = new int[n][m];
		int[][] B = new int[m][l];
		
		for(int i = 0;i < n;i++) {
			for(int j = 0;j < m;j++) {
				
				int a = sc.nextInt();
				
				
				A[i][j] = a;
				
				
			}
		}
		
		for(int k = 0;k < m;k++) {
			for(int p = 0;p < l;p++) {
				
				int b = sc.nextInt();
				
				B[k][p] = b;
				
				
			}
		}
		
		//Aの横とBの縦が同じことに注意する
		
		long sum = 0;
		long seki = 0;
		
		
		
		for(int q = 0;q < n;q++) {
			
			for(int r = 0;r < l;r++) {
				
				for(int s = 0;s < m;s++) {
					
					//sはAの横 rはBの縦 qはAの縦
					
					seki = A[q][s] * B[s][r];
					
					sum = sum + seki;
					
					
					
				}
				
				System.out.print(sum);
				
				sum = 0;
				if(r != l - 1) {
					System.out.print(" ");
				}
				
				
			}
			
			System.out.println("");
		}
		
		}



}



Measured memory_bytes: 53888
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <math.h>
#include <cassert>
#define rep(i,n) for(int i = 0; i < n; ++i )
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
// auto mod int
const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {if ((x += a.x) >= mod) x -= mod; return *this;}
  mint& operator-=(const mint a) {if ((x += mod-a.x) >= mod) x -= mod; return *this;}
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}

int main() {
  int n;
  cin >> n;
  vector<mint> p(n+1);
  p[0] = 1;
  rep(i,n) p[i+1] = p[i]*2;

  map<P,P> c; ll zero = 0;
  rep(i,n){
    ll a,b;
    cin >> a >> b;
    if(a==0&&b==0){
      ++zero;
      continue;
    }
    if(a==0) b /= abs(b);
    if(b==0) a /= abs(a);
    if(a!=0&&b!=0){
      ll m = gcd(abs(a),abs(b));
      a /= m; b /= m;
    }
    if(a<0||(a==0&&b<0)){ a*=-1; b*=-1; }
    if(b>0){
      c[P(a,b)].first++;
    }else{
      c[P(-b,a)].second++;
    }
  }
  mint ans = 1;
  for(auto i:c) ans *= p[i.second.first]+p[i.second.second]-1;
  ans -= 1;
  ans += zero;
  cout << ans << endl;
}


Measured memory_bytes: 20184
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <math.h>
#include <fstream>
#include <sstream>
using namespace std;

const unsigned long long BASE = 1e9 + 7;

int main()
{
    string a, b, c;
    cin >> a >> b >> c;
    cout << a[0] << b[1] << c[2] << endl;
    return 0;
}


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

#define fastIO ios::sync_with_stdio(false);cout.tie(0);cin.tie(0);
#define endl '\n'
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define MP make_pair
#define inf INT_MAX
#define minf INT_MIN

typedef long long int lli;

ofstream outfile;
ifstream infile;

int main()
{
    infile.open("input.txt");
    outfile.open("output.txt");

    long long int multiplier1 =1 , i, j, multiplier2 = 1, a, b, sum = 1;
    cin >> a >> b;

    if( a == b+1)
    {
        for(i = 1; i <= b; ++i)
        {
            multiplier1 *= i;
            multiplier1 %= 1000000007;

            multiplier2 *= i;
            multiplier2 %= 1000000007;
        }
        multiplier1 *= a;
        multiplier1 %= 1000000007;
        sum = multiplier1 * multiplier2;
        sum %= 1000000007;
        cout << sum;
    }
    else if( b == a+1)
    {
        for(i = 1; i <= a; ++i)
        {
            multiplier1 *= i;
            multiplier1 %= 1000000007;

            multiplier2 *= i;
            multiplier2 %= 1000000007;
        }
        multiplier2 *= b;
        multiplier2 %= 1000000007;
        sum = multiplier1 * multiplier2;
        sum %= 1000000007;
        cout << sum;
    }
    else if( a == b)
    {
        for(i = 1; i <= b; ++i)
        {
            multiplier1 *= i;
            multiplier1 %= 1000000007;

            multiplier2 *= i;
            multiplier2 %= 1000000007;
        }
        sum = multiplier1 * multiplier2;
        sum %= 1000000007;
        sum *=2;
        sum %= 1000000007;
        cout << sum;
    }
    else
    {
        cout <<0;
    }

}


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

int main(void){
    int n,k;
    scanf("%d%d",&n,&k);
    int d[k];
    for (int i=0; i<k; i++){
        scanf("%d",&d[i]);
    }
    for (int i=0; i<k; i++){
        if(n%10==d[i]){
            n++; 
            i=-1;
        } else if (n>=10 && (n/10)%10==d[i]) {
            n++;
            i=-1;
        } else if (n>=100 && (n/100)%10==d[i]){
            n++;
            i=-1;
        } else if (n>=1000 && (n/1000)%10==d[i]){
            n++;
            i=-1;
        } else if (n>=10000 && (n/10000)%10==d[i]){
            n++;
            i=-1;
        }
    }
    printf("%d\n",n);
	return 0 ;
}

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

int main() {
    int N; string S;
    cin >> N >> S;

    for(int i=0; i<S.size(); i++) {
        int c = (int)(S[i]-'A');
        if(c + N >= 26) c -= 26;
        int n = 'A' + c + N;
        cout << char(n);
    }
}

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

#define rep(i, s, n) for(int i = s; i < n; ++i)
#define rrep(i, n) for(int i = n - 1; i > -1; --i)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;
const long long INF = 1000000000;
const int MOD = 1000000007;
typedef long long ll;
typedef pair<int, int> P;

int main() {
    int n;
    cin >> n;
    vector<int> a(n), b(n), c(n - 1);
    int ans = 0;
    rep(i, 0, n){
        cin >> a[i];
    }
    rep(i, 0, n){
        cin >> b[i];
        ans += b[i];
    }
    rep(i, 0, n - 1){
        cin >> c[i];
    }
    rep(i, 0, n - 1){
        if(a[i] + 1 == a[i + 1]){
            ans += c[a[i] - 1];
        }
    }
    cout << ans << endl;

}


Measured memory_bytes: 256
import math
def ccw(p1,p2,p3):
    #print (p2[0]-p1[0])*(p3[1]-p2[1])-(p2[1]-p1[1])*(p3[0]-p2[0])>=0
    return (p2[0]-p1[0])*(p3[1]-p2[1])-(p2[1]-p1[1])*(p3[0]-p2[0])
while True:
    n=input()
    if n==0:
        break
    p=[0]*n
    for i in xrange(n):
        p[i]=map(float,raw_input().strip().split(","))
    P=min(p,key=lambda a:(a[1],a[0]))
    p.sort(key=lambda x:math.atan2(x[1]-P[1],x[0]-P[0]))
    #print n
    #print "\n".join(map(lambda x:"{},{}".format(x[0],x[1]),p))
    M=0
    i=1
    c_p=p[:]
    #print M,p
    while M<len(p)-1:
        if all([ccw(p[M-1],p[M],p[i])>=0 for i in xrange(M+1,len(p))]):
            M+=1
        else:
            p.remove(p[M])
        #print M,p
    print len(c_p)-len(p)
    #print len(p)
    #print "\n".join(map(lambda x:"{},{}".format(x[0],x[1]),p))

Measured memory_bytes: 4496
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))

mis = 0
if a[0] + b[1] != a[1] + b[0]:
    print("No")
    quit(0)
elif a[1] + b[2] != a[2] + b[1]:
    print("No")
    quit(0)
elif a[0] + b[2] != a[2] + b[0]:
    print("No")
    quit(0)
elif a[0] + c[1] != c[1] + a[0]:
    print("No")
    quit(0)
elif a[1] + c[2] != a[2] + c[1]:
    print("No")
    quit(0)
elif a[0] + c[2] != a[2] + c[0]:
    print("No")
    quit(0)
elif b[0] + c[1] != c[1] + b[0]:
    print("No")
    quit(0)
elif b[1] + c[2] != b[2] + c[1]:
    print("No")
    quit(0)
elif b[0] + c[2] != b[2] + c[0]:
    print("No")
    quit(0)

print("Yes")

Measured memory_bytes: 3064
#include <cstdio>
#include <map>

int main()
{
	std::map<int, long long> pcount;
	int N;
	scanf("%d", &N);

	for (int n = 1; n <= N; ++n)
    {
      int tmpn = n;
      for (int i = 2; i * i <= N; ++i)
      {
          while (tmpn % i == 0)
          {
            pcount[i]++;
            tmpn /= i;
          }
      }
	  if (tmpn != 1) pcount[tmpn]++;
    }
  long long ans = 1;
  for (auto &p : pcount)
  {
    ans = (ans * (p.second + 1)) % 1000000007;
  }
  printf("%d\n", ans);
  return 0;
}

Measured memory_bytes: 256
class BIT:
    def __init__(self,n):
        self.n = n
        self.tree = [0]*(n+1)

    def sum(self,x):
        sum = 0
        while(x>0):
            sum+=self.tree[x]
            x-=x&(-x)
        return sum

    def update(self,x,k):
        while(x<=self.n):
            self.tree[x]+=k
            x+=x&(-x)

    def build(self,a):
        for i in range(len(a)):
            k = a[i]
            x = i+1
            while(x<=self.n):
                self.tree[x]+=k
                x+=x&(-x)
class Query:
    def __init__(self, r,l, idx):
        self.l = l
        self.r = r
        self.idx = idx

def solve(case):
    n,q = map(int,input().split())
    c = list(map(int,input().split()))
    query = []
    for i in range(q):
        l,r = map(int,input().split())
        query.append(Query(r,l,i))

    query.sort(key = lambda x:x.r)
    bit = BIT(n)
    lastvis = [-1]*(n+1)
    ind = 0
    ans = [0]*q
    for i in range(n):
        if(lastvis[c[i]] != -1):
            bit.update(lastvis[c[i]]+1,-1)

        lastvis[c[i]] = i
        bit.update(i+1,1)
        while(ind<q and query[ind].r == i+1):
            ans[query[ind].idx] = (bit.sum(i+1) - bit.sum(query[ind].l-1))
            ind+=1

    print('\n'.join(str(ans[i]) for i in range(len(ans))))
    # for i in range(q):
    #     print(ans[i])
solve(1)


Measured memory_bytes: 258476
import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		new Main().run();
	}

	private void run() {
		Scanner scanner = new Scanner(System.in);
		while (true) {
			int n = scanner.nextInt();
			if (n == 0)
				break;
			List<Integer> list = new ArrayList<Integer>();
			for (int i = 0; i <= n; i++)
				list.add(scanner.nextInt());
			for(ListIterator<Integer>it = list.listIterator();it.hasNext();){
				int a = it.next();
				it.remove();
				if(slove(list)){
					System.out.println(a);
					break;
				}
				it.add(a);
			}
		}
	}

	private boolean slove(List<Integer> tmp) {
		int ans = tmp.get(1) - tmp.get(0);
		for (int i = 2; i < tmp.size(); i++)
			if (tmp.get(i) - tmp.get(i - 1) != ans)
				return false;
		return true;
	}
}

Measured memory_bytes: 36872
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define MOD 1000000007
#define rep(i,n) for(i=0;i<n;i++)
#define loop(i,a,n) for(i=a;i<n;i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define first F
#define second S

typedef vector<int> vi;
typedef pair<int,int> pii;

int main(void) {
  vi l(3);
  vi n(4,0);
  while(scanf("%d %d %d",&l[0],&l[1],&l[2])!=EOF){
    sort(all(l));
    if(l[0]+l[1]>l[2])n[0]++;
    else break;
    int hypo=l[0]*l[0]+l[1]*l[1];
    if(hypo==l[2]*l[2])n[1]++;
    else if(hypo>l[2]*l[2])n[2]++;
    else if(hypo<l[2]*l[2])n[3]++;
  }
  printf("%d %d %d %d\n",n[0],n[1],n[2],n[3]);
}

Measured memory_bytes: 3196
import sys
input=sys.stdin.readline
#input = open(sys.argv[1], "r").readline

def main():
    _ = int(input())
    H = list(map(int, input().split()))
    n = 0
    for i in range(len(H)):
        b = True
        for j in range(0,i):
            if H[i] < H[j]:
                b = False
                break
        if b:
            n += 1
    print(n)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define rep(i,n) for (int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
int main(){
  int n,m;
  while(scanf("%d%d",&n,&m)&&n&&m){
    int now=0,f[n],d[m],ans=-1;
    for(int i=0;i<n;i++)scanf("%d",&f[i]);
    for(int i=0;i<m;i++)scanf("%d",&d[i]);
    for(int i=0;i<m;i++){
      now+=d[i];
      if(now<0)continue;
      now+=f[now];
      if(now>=n-1){
        ans=i;
        break;
      }
    }
    printf("%d\n",ans+1);
  }
}

Measured memory_bytes: 1196
/* 
	Author: ankrypt
*/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define MOD 1000000007
#define ll long long int
#define u64 unsigned long long int
#define ff first
#define ss second
#define all(x) x.begin(), x.end() 
#define ub upper_bound
#define lb lower_bound
#define MAX_INT 100005
#define PI 3.141592653589793
#define trace1(x)                cerr<<#x<<": "<<x<<endl
#define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
#define go ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define fi(a, b, c, d) for(int a = b; a < c; a += d)
#define fl(a, b, c, d) for(ll a = b; a < c; a += d)
#define fei(a, b, c, d) for(int a = b; a <= c; a += d)
#define fel(a, b, c, d) for(ll a = b; a <= c; a += d)
#define quit exit(0)
#define mem(x, a) memset(x, a, sizeof x)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pcl pair<char, ll>
#define psl pair<string, ll>


ll N, M, A, B, C;
ll arr[MAX_INT], arr1[MAX_INT], data[MAX_INT];
vector<ll> V;
unordered_map<ll, ll> mp;
set<ll> s;
string S = "";
ll cases;

int main() {
	go;
	ll ans = 0;
    cin >> N;
    fei(i, 1, N, 1) {
    	cin >> arr[i];
    }
    ll cnt = 200005;
    ll lit = 1;
    while(cnt--) {
    	lit = arr[lit];
    	ans++;
    	if(lit == 2) {
    		break;
    	}
    }   
    if(lit != 2) {
    	ans = -1; 
    }
    cout << ans << "\n";
	return 0;
}
/*
	Powered by Buggy Plugin
*/




Measured memory_bytes: 4404
#include <iostream>
#include <vector>
#include <bits/stdc++.h>

using namespace std;
#define N_MAX 200000
#define input(d) cin >> d;
#define inputs(n,d) for(int i=0;i<n;i++) {cin >> d[i];}
#define inputxy(n,x,y) for(int i=0;i<n;i++) {cin >> x[i] >> y[i];}
#define output(d) cout << d << endl;
#define outputs(n,d) for(int i=0;i<n;i++) {cout << d[i] << endl;}
#define outputxy(n,x,y) for(int i=0;i<n;i++) {cout << x[i] << y[i] << endl;}
#define f0(i,n) for(int i=0;i<n;i++)
#define f(i,a,b) for(int i=a;i<b;i++)
#define l long
#define ll long long
#define s string

int main(){
    ll n,d,x,y,ans=0;
    string st;
    input(n);
    input(st);

    f0(i,n){
        if(st[i] == 'R'){
            d++;
        }
    }
    f0(i,d){
        if(st[i] == 'W'){
            ans++;
        }
    }
    

    output(ans);
    return 0;
}

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

typedef unsigned long long ULL;

int main()
{
  	ULL M, N;
  	std::cin >> N >> M;
  	std::vector<ULL> foodLovers(M);
  	for(ULL i = 0;i < N;i++)
  	{
        ULL a;
        std::cin >> a;
        while(a--)
        {
            ULL b;
            std::cin >> b;
            foodLovers[b - 1]++;
        }
  	}
  	std::sort(foodLovers.rbegin(), foodLovers.rend());
  	ULL Sum = 0;
  	for(ULL i = 0;i < M;i++)
  	{
  	    if(foodLovers[i] == 0)
  	        break;
  	    else if(foodLovers[i] == N)
  	        Sum++;
  	}
  	std::cout << Sum << std::endl;
  	return 0;
}

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

using namespace std;

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

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

	sort(p, p + n, greater < int >());
	p[0] /= 2;
	int sum = 0;

	for (int i = 0; i < n; i++) {
		sum += p[i];
	}
	cout << sum << endl;
	return 0;
}


Measured memory_bytes: 256
N,D = map(int, input().split())
distance = pow(D,2)

count = 0

for i in range(0,N):
    array = list(map(int, input().split()))
    d_point = pow(array[0],2) + pow(array[1],2)
    if distance >= d_point:
        count = count +1


print(count)

Measured memory_bytes: 9180
import math

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

# 最小の積載量は、最も重い荷物の重さ。または、全荷物の合計をトラック台数で割った数。
minP = max(max(W), math.ceil(sum(W) / k))
# 最大の積載量は、全荷物の合計
maxP = sum(W)

while minP < maxP:
    # 重さの最小値と最大値の半分を、積載量Pと仮定
    midP = (minP + maxP) // 2

    countTrack = 1
    calc = 0
    okFlag = True

    for w in W:
        calc += w
        
        # 積載量を超過した場合
        if calc > midP:
            # 載せずに次のトラックにまわす
            calc = w
            # トラックを1台増加
            countTrack += 1

        # トラックの最大台数を超えていたら、NG
        if countTrack > k:
            okFlag = False
            break

    # トラックの最大台数内で載せきれた場合
    if okFlag:
        # 最大値を狭めて再度処理
        maxP = midP
    else:
        # 最小値を狭めて再度処理
        minP = midP + 1

print(minP)


Measured memory_bytes: 9620
r,g,b,n=gets.chomp.split(' ').map(&:to_i)
count=0
num=[r,g,b].sort.reverse
a1=n/num[0]
(a1+1).times do |i|
 a2=n-num[0]*i
  a3=a2/num[1]
  (a3+1).times do |j|
    a4=a2-num[1]*j
    if a4%num[2] == 0
      count+=1
    end
  end
end
puts count

Measured memory_bytes: 1788
#include <deque>
#include <cstdio>
#include <string>
#include <iostream>
using namespace std;
int main(){
	string s;
	int k;
	cin >> s >> k;
	int n = s.size();
	deque<int> a;
	for (int i = 0; i < n; i++) a.emplace_back(s[i] - '0');
	int dp[n][k + 1][2];
	for (int i = 0; i < n; i++){
		dp[i][0][0] = 1;
		dp[i][0][1] = 0;
		for (int j = 1; j <= k; j++){
			dp[i][j][0] = 0;
			dp[i][j][1] = 0;
		}
	}
	dp[0][1][0] = a[0] - 1;
	dp[0][1][1] = 1;
	for (int i = 1; i < n; i++){
		if (a[i] == 0){
			for (int j = 1; j <= k; j++){
				dp[i][j][0] = dp[i - 1][j][0] + dp[i - 1][j - 1][0] * 9;
				dp[i][j][1] = dp[i - 1][j][1];
			}
		}else{
			for (int j = 1; j <= k; j++){
				dp[i][j][0] = dp[i - 1][j][0] + dp[i - 1][j][1] + dp[i - 1][j - 1][0] * 9 + dp[i - 1][j - 1][1] * (a[i] - 1);
				dp[i][j][1] = dp[i - 1][j - 1][1];
			}
		}
	}
	printf("%d\n", dp[n - 1][k][0] + dp[n - 1][k][1]);
}

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

int a[200005];
int main() {
	int n;
	cin >> n;
	for ( int i = 1; i <= n; ++i ) {
		cin >> a[i];
	}
	
	int m = 0;
	for ( int i = n; 0 < i; --i ) {
		for (int j = i + i; j <= n; j += i ) {
			a[i] ^= a[j];	
		}
		if(a[i])++m;
	}
	cout << m << endl;
	for ( int i = 1; i <= n; ++i ) {
		if(a[i]) cout << i << " ";
	}
	return 0;
}

Measured memory_bytes: 1792
#include<iostream>
#include<vector>
#include<cstdio>
#include<string>
#include<cmath>
#include<math.h>
#include<algorithm>
#include<string.h>
#include <iomanip>
#include <sstream>
using namespace std;

long long divnum(long long x){
  long long i=2;
  if(x < 2) return 1;
  else if(x == 2) return i;
  if(x%2 == 0) i+=2;
  if(x == 4) return 3;
  for(long long j = 3; j*j <= x; j += 1){
    if(x%j == 0){
      if(x == j) i++;
      else{
        i+=2;
        if(x == j*j) i--;
      }
    }
  }
  return i;
}

int main() {
  long long N;
  int ans = 0;

  cin >> N;

    for(long long  i = 1; i<= N; i++){
        long long  tmp = divnum(i);
        if(tmp == 8 && i%2 == 1) ans++;
    }
    cout << ans << endl;
}


Measured memory_bytes: 3592
#include <iostream>
#include<algorithm>
#include<cstring>
//#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define mp make_pair
#define nt _int128
#define inf (int)1e9

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll t;
	// cin >> t;
	t  = 1;
	while (t--)
	{
		ll n;
		cin >> n;
		ll arr[n][3];
		ll dp[n][3];
		memset(arr, 0, sizeof(arr));

		for (ll i = 0; i < n; i++)
		{
			cin >> arr[i][0] >> arr[i][1] >> arr[i][2];
			if (i == 0)
			{
				dp[0][0] = arr[i][0];
				dp[0][1] = arr[i][1];
				dp[0][2] = arr[i][2];
			}
		}
		for (ll i = 1; i < n; i++)
		{
			dp[i][0] = arr[i][0] + max(dp[i - 1][1], dp[i - 1][2]);
			dp[i][1] = arr[i][1] + max(dp[i - 1][0], dp[i - 1][2]);
			dp[i][2] = arr[i][2] + max(dp[i - 1][1], dp[i - 1][0]);
		}


		// cout << endl;
		// for (ll i = 0; i < n; i++)
		// 	cout << dp[i][0] << " " << dp[i][1] << " " << dp[i][2] << endl;
		// cout << endl;
		cout << max({dp[n - 1][0], dp[n - 1][1], dp[n - 1][2]} ) << endl;

	}
	return 0;
}


Measured memory_bytes: 4992
#include <bits/stdc++.h>
#define rep(i,a) for(int i=0;i<int(a);++i)
#define REP(i,a,b) for(int i=int(a);i<int(b);++i)
using ll = long long;
using itn = int;
using namespace std;
using Graph = vector<vector<int>>;
int GCD(int a, int b){
    return b ? GCD(b, a%b) : a;
}

int main() {
	ll N,M;
    cin>>N>>M;
    ll A[N],a[N+1]={};
    pair<ll,ll> change[M];
    rep(i,N) cin>>A[i];
    rep(i,M) cin>>change[i].second>>change[i].first;
    sort(A,A+N);
    sort(change,change+M);
    rep(i,N) a[i+1]=A[i]+a[i];
    ll ans=0,k=0;
    for(ll i=M-1; i>=0; i--){
        rep(j,change[i].second){
            if(k>=N) break;
            ans+=max(A[k++],change[i].first);
        }
    }
    for(int i=k; i<N; i++) ans+=A[i];
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3328
#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <algorithm>
#include <set>
#include <unordered_map>

using namespace std;

int main() {
  int c[4][4];
  for (int i=1; i<=3; i++) {
    for (int j=1; j<=3; j++) {
      cin >> c[i][j];
    }
  }

  // fix a1 = 0;
  for (int a2 = -100; a2 <= 100; a2++) {
    for (int a3 = -100; a3 <= 100; a3++) {
      int b1 = c[1][1];
      if (b1 != c[2][1] - a2 || b1 != c[3][1] - a3) {
        continue;
      }
      int b2 = c[1][2];
      if (b2 != c[2][2] - a2 || b2 != c[3][2] - a3) {
        continue;
      }
      int b3 = c[1][3];
      if (b3 != c[2][3] - a2 || b3 != c[3][3] - a3) {
        continue;
      }
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
}

Measured memory_bytes: 256
text = input()

text1 = text.replace(text[0], "")
try:
	text2 = text1.replace(text1[0], "")
except:
	text2 = "e"

if len(text) == 4 and len(text1) == 2 and len(text2) == 0:
  print("Yes")
else:
  print("No")


Measured memory_bytes: 2940