akhauriyash/Code-Regression huggingface dataset:
import java.util.*;
public class Main {
    public static void main (String[] args) {
        Scanner s = new Scanner(System.in);
        int x;
        int a = s.nextInt();
        int b = s.nextInt();
        int c = s.nextInt();
        if (a > b) {
            x = a;
            a = b;
            b = x;
            if (b > c) {
                x = b;
                b = c;
                c = x;
                if (a > b) {
                    x = a;
                    a = b;
                    b = x;
                }
            }
        }else if (b > c) {
                x = b;
                b = c;
                c = x;
                if (a > b) {
                    x = a;
                    a = b;
                    b = x;
                }
            }
        System.out.println(a + " " + b + " " + c);
    }
}


Measured memory_bytes: 26144
#include <bits/stdc++.h>
using namespace std;
#define psi pair<string, int>
int main(){
    queue<psi> schedule_queue;
    int n, time, quantam, current_time = 0;
    string name;
    cin>>n>>quantam;
    for(int i = 0; i < n; ++i){
        cin>>name>>time;
        schedule_queue.push(make_pair(name, time));
    }
    while(!schedule_queue.empty()){
        psi item = schedule_queue.front();
        schedule_queue.pop();
        if(item.second>quantam){
            current_time += quantam;
            schedule_queue.push(make_pair(item.first, item.second-quantam));
        }
        else{
            current_time += item.second;
            cout << item.first << " " << current_time << endl;
        }
    }
    return 0;
}

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

#define rep(i, n) for (int i = 0; i < n; i++)
#define rep1(i, n) for (int i = 1; i <= n; i++)
#define show(a, n) rep(i,n) {cout<<a[i]<<' ';} cout<<endl;

using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<long long, long long> pll;

const int INF = 1 << 30;
const long long INFL = 1LL << 62;
const int MOD = 1000000007;
const int MAX = 100000;
const int N = 100000;

int x[N];

int main() {
	int n,k;cin>>n>>k;
	int pi=-1;
	rep(i,n) {cin>>x[i];if(pi==-1&&x[i]>=0) pi=i;}
	if(pi==-1) {cout<<-x[n-k]<<endl;return 0;}
	int ans=INF;
	if(pi+k-1<=n-1) ans=min(ans,x[pi+k-1]);
	if(pi-k>=0) ans=min(ans,-x[pi-k]);
	for(int i=1;i<=k-1;i++){
		if(pi-i<0||pi+(k-i)-1>n-1) continue;
		ans=min(ans,-2*x[pi-i]+x[pi+(k-i)-1]);
		ans=min(ans,-x[pi-i]+2*x[pi+(k-i)-1]);
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 640
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
#include<queue>
#include<functional>
#include<map>
#include<set>
#include<cstring>
#include<string>
#include<stack>
#include<stdlib.h>
#include<math.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
typedef pair<int, char> pic;
typedef priority_queue<pii, vector<pii>, greater<pii> > RPQ;
#define mk make_pair
#define INF (1ll << 30ll)
#define INFL (1ll << 60ll)
#define mod 1000000007

int N, imos[1010][1010];

signed main(){
    cin >> N;
    for(int i = 0; i < N; i++){
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        imos[a][b]++;
        imos[c][d]++;
        imos[a][d]--;
        imos[c][b]--;
    }
    for(int i = 0; i < 1001; i++){
        for(int j = 0; j < 1001; j++){
            imos[i][j + 1] += imos[i][j];
        }
    }
    int ans = 0;
    for(int i = 0; i < 1001; i++){
        for(int j = 0; j < 1001; j++){
            imos[j + 1][i] += imos[j][i];
            ans = max(ans, imos[j][i]);
        }
    }
    cout << ans << endl;

    

    return 0;
}

/*


*/


Measured memory_bytes: 11004
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
ll a[N];
int main()
{
	int n, k;
	scanf("%d%d", &n, &k);
	for (int i = 0; i < n; i++) {
		scanf("%lld", a + i);
	}
	double ans = 0, tmp;
	for (int i = 0; i < k; i++) {
		ans += (a[i] + 1) / 2.0;
	}
	tmp = ans;
	int l = 0, r = k - 1;
	while (r < n - 1) {
		r++;
		tmp = tmp - (a[l] + 1) / 2.0 + (a[r] + 1) / 2.0;
		ans = max(ans, tmp);
		l++;
	}
	printf("%.8f\n", ans);
	return 0;
}

Measured memory_bytes: 1792
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <limits.h>
#include <math.h>
#include <time.h>
#include <stdarg.h>
#include <algorithm>
#include <iostream>

using namespace std;

int
main() {
  string a;
  cin>>a;

  string b;
  cin>>b;

  int n = 0;
  for (int i=0; i<3; i++)
    if (a[i] == b[i])
      n++;
  cout<<n<<endl;


  return 0;
}

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

int main() {
    int n, m;
    cin >> n;
    vector<string> s(n);
    rep(i, n) cin >> s[i];
    cin >> m;
    vector<string> t(m);
    rep(i, m) cin >> t[i];
    int ans = INT_MIN;
    int tmp;
    
    rep(i, n) {
        tmp = 0;
        
        rep(ii, n) {
            if (s[i] == s[ii]) {
                tmp++;
            }
        }
        
        rep(ii, m) {
            if (s[i] == t[ii]) {
                tmp--;
            }
        }
        
        ans = max(ans, tmp);
    }
    
    cout << max(ans, 0) << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define EPS 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LL long long
const int MOD = 1E9+7;
const int N = 100000+5;
const int dx[] = {-1,1,0,0,-1,-1,1,1};
const int dy[] = {0,0,-1,1,-1,1,-1,1};
using namespace std;
int a[N];
int main(){
    string str;
    cin>>str;
    
    int len=str.length();
    int cnt=0;
    for(int i=1;i<len;i++)
        if(str[i]!=str[i-1])
            a[++cnt]=max(i,len-i);

    int res=len;
    for(int i=1;i<=cnt;i++)
        res=min(res,a[i]);

    printf("%d\n",res);
    return 0;
}


Measured memory_bytes: 640
#include <stdio.h>

int main() {
  int n;
  scanf("%d", &n);
  int o[n];
  for (int i = 0; i < n; i++) {
    o[i] = 0;
  }
  int a;
  for (int i = 0; i < n - 1; i++) {
    scanf("%d", &a);
    o[a-1]++;
  }
  for (int i = 0; i < n; i++) {
    printf("%d\n", o[i]);
  }
  return 0;
}


Measured memory_bytes: 2512
package main

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

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func main() {
	defer flush()

	R := readInt()
	C := readInt()
	K := readInt()

	goods := make([][]int, R)
	for i := 0; i < R; i++ {
		goods[i] = make([]int, C)
	}
	for i := 0; i < K; i++ {
		r := readInt() - 1
		c := readInt() - 1
		v := readInt()
		goods[r][c] = v
	}

	dp := make([][][4]int, R)
	for i := 0; i < R; i++ {
		dp[i] = make([][4]int, C)
	}

	for i := 0; i < R; i++ {
		for j := 0; j < C; j++ {
			if j != C-1 {
				for k := 0; k < 4; k++ {
					dp[i][j+1][k] = max(dp[i][j+1][k], dp[i][j][k])
				}
				if goods[i][j] != 0 {
					for k := 0; k < 3; k++ {
						dp[i][j+1][k+1] = max(dp[i][j+1][k+1], dp[i][j][k]+goods[i][j])
					}
				}
			}
			if i != R-1 {
				for k := 0; k < 4; k++ {
					dp[i+1][j][0] = max(dp[i+1][j][0], dp[i][j][k])
				}
				if goods[i][j] != 0 {
					for k := 0; k < 3; k++ {
						dp[i+1][j][0] = max(dp[i+1][j][0], dp[i][j][k]+goods[i][j])
					}
				}
			}
		}
	}

	result := -1
	for k := 0; k < 4; k++ {
		result = max(result, dp[R-1][C-1][k])
	}
	if goods[R-1][C-1] != 0 {
		for k := 0; k < 3; k++ {
			result = max(result, dp[R-1][C-1][k]+goods[R-1][C-1])
		}
	}

	println(result)
}

const (
	ioBufferSize = 1 * 1024 * 1024 // 1 MB
)

var stdinScanner = func() *bufio.Scanner {
	result := bufio.NewScanner(os.Stdin)
	result.Buffer(make([]byte, ioBufferSize), ioBufferSize)
	result.Split(bufio.ScanWords)
	return result
}()

func readString() string {
	stdinScanner.Scan()
	return stdinScanner.Text()
}

func readInt() int {
	result, err := strconv.Atoi(readString())
	if err != nil {
		panic(err)
	}
	return result
}

var stdoutWriter = bufio.NewWriter(os.Stdout)

func flush() {
	stdoutWriter.Flush()
}

func println(args ...interface{}) (int, error) {
	return fmt.Fprintln(stdoutWriter, args...)
}


Measured memory_bytes: 375900
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define rrep(i,n) for(int i=1;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define dunk(a) cout << (a) << "\n"
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int inf = 1001001001;
const int mod = 1000000007;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	string s;
	cin >> s;
	int n = s.size();
	string ans = s[0] + to_string(n - 2) + s[n - 1];
	dunk(ans);
	return 0;
}


Measured memory_bytes: 256
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n = ni()
a1 = na()
a2 = na()

count_1 = 0
biggest = 0
for i in range(n):
    count_1 += a1[i]
    count = count_1
    count += sum(a2[i:])
    if biggest < count:
        biggest = count
print(biggest)


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

// clang-format off
#define forn(i, x, y) for(int i = x; i < y; i++)
#define IOS ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(NULL)
#define printVector(a) for(auto it = a.begin() ; it != a.end(); it++) {cout << *it << endl;}

using VI = vector<int>;
using VVI = vector<VI>;
// clang-format on

const long long MOD = 1000000007;

void add(int &a, int b)
{
  a += b;
  if (a >= MOD)
    a -= MOD;
}

int main()
{
  IOS;

  int H, W;
  cin >> H >> W;

  VVI dp(H, VI(W));
  dp[0][0] = 1;
  string line;
  forn(i, 0, H)
  {
    cin >> line;
    forn(j, 0, W)
    {
      if (line[j] == '#')
        continue;
      if (i > 0)
        add(dp[i][j], dp[i - 1][j]);
      if (j > 0)
        add(dp[i][j], dp[i][j - 1]);
    }
  }
  cout << dp[H - 1][W - 1] << endl;

  return 0;
}


Measured memory_bytes: 7136
#include <iostream>
#include <algorithm>

using namespace std;

int main(){
    string s; cin >> s;
    int ans=0;
    int t=0;
    for(auto c : s){
        if(c=='A' || c=='T' || c=='C' || c=='G') ++t;
        else{
            ans=max(ans, t);
            t=0;
        }
    }
    ans=max(ans, t);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
n, m = map(int, input().split())
yes = [False for i in range(n)]
negative = [0 for i in range(n)]
score = [0 for i in range(n)]
for i in range(m):
	problem, s = input().split()
	p = int(problem)
	if s=="AC" and not yes[p-1]:
		yes[p-1] = True
		score[p-1] = negative[p-1]
	else:
		negative[p-1] += 1
	

print(sum(yes), sum(score))

Measured memory_bytes: 5552
#include <iostream>
#include <string>

using namespace std;

int main(){
  string s;
  int a, b;
  cin >> s;
  a = stoi(s.substr(0,2));
  b = stoi(s.substr(2,2));
  if (1 <= a && a <= 12) {
    if (1 <= b && b <= 12) {
      cout << "AMBIGUOUS" << endl;
    } else {
      cout << "MMYY" << endl;      
    }
  } else if (1 <= b && b <= 12) {
    cout << "YYMM" << endl;
  } else {
    cout << "NA" << endl;
  }
  return(0);
}


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

int main(){
	cout << fixed << setprecision(12);

	int a, b;
	cin>>a>>b;

	cout<< a / b <<" ";
	cout<< a % b <<" ";
	cout<<(double)a / b <<endl;

	return 0;
}


Measured memory_bytes: 3288
#include <bits/stdc++.h>
#include <iostream>
#include <string>

using namespace std;

int main()
{
    int n;
    cin >> n;
    int D[n][2];
    int count = 0;

    for(int i=0; i<n; i++) {
        cin >> D[i][0] >> D[i][1];
    }
    
    for(int j=0; j<n; j++) {
        if (D[j][0] == D[j][1]) {
            count++;
            if(count == 3) {
                cout << "Yes" << endl;
                return 0;
            }
        } else {
            count = 0;
        }
    }

    cout << "No" << endl;

}

Measured memory_bytes: 3616
def resolve():
    N, W = map(int, input().split())    
    w_v = [list(map(int, input().split())) for _ in range(N)]  # [N][0:weight, 1:value]

    dp = [[0] * (W+1) for _ in range(N+1)] 

    for i in range(N):
        for j in range(W+1):
            w = w_v[i][0]
            v = w_v[i][1]
            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
            if j + w <= W:
                dp[i + 1][j + w] = max(dp[i][j] + v, dp[i + 1][j + w])
 
    print(dp[N][W])


if __name__ == "__main__":
    resolve()

Measured memory_bytes: 118512
def main():
    h, w, n = map(int, input().split())

    color_dict = {}
    for i in range(n):
        a, b = map(int, input().split())
        for j in range(a-2, a+1):
            for k in range(b-2, b+1):
                if 1 <= j <= h-2 and 1 <= k <= w-2:
                    color_dict[(j, k)] = color_dict.get((j, k), 0) + 1

    times = [0 for i in range(10)]
    for i in color_dict:
        times[color_dict[i]] += 1

    times[0] = (h-2) * (w-2) - len(color_dict)

    for i in times:
        print(i)


if __name__ == '__main__':
    main()


Measured memory_bytes: 151728
import sys
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N = int(readline())
    count = 0
    for _ in range(N):
        l, r = map(int, readline().split())
        count += r-l+1
    print(count)



if __name__ == '__main__':
    main()

Measured memory_bytes: 3060
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using P = pair<int, int>;
#define PI acos(-1)
#define Mod (int)1000000007
#define INFTY (int)INT_MAX
#define Rep(i, n) for (int i = 0; i < (int)(n); i++)
#define BitRep(i, n) for (int i = 0; i < (int)(1 << n); i++)
#define All(vec) vec.begin(), vec.end()
#define Sum(vec) accumulate(vec.begin(), vec.end(), 0)
#define Sort(vec) sort(vec.begin(), vec.end())
#define Reverse(vec) reverse(vec.begin(), vec.end())
#define Count(vec, x) count(vec.begin(), vec.end(), x)
#define Next_permutation(vec) next_permutation(vec.begin(), vec.end())
#define Find(S, s) S.find(s) != string::npos

int main() {
	int n;
	cin >> n;
	vector<int> A(n);
	Rep(i, n) cin >> A[i];
	int q;
	cin >> q;
	Rep(i, q) {
		int b, e, k;
		cin >> b >> e >> k;
		cout << count(A.begin() + b, A.begin() + e, k) << endl;
	}
	return 0;
}


Measured memory_bytes: 3104
a=[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

K=parse(Int,(readline()))
print(a[K])

Measured memory_bytes: 129060
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))

int main(){
	ll x,t;
	scanf("%lld%lld",&x,&t);
	printf("%lld",max(0,x-t));
}

Measured memory_bytes: 128
#include <iostream>
#include <string>

using namespace std;

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

    int n;
    cin >> n;

    int cnt[10][10] = {0};
    for (int i = 1; i <= n; i++) {
        string s = to_string(i);
        cnt[s[0]-'0'][s[s.length()-1]-'0']++;
    }

    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        string s = to_string(i);
        ans += cnt[s[s.length()-1]-'0'][s[0]-'0'];
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define maxn 75
using namespace std;
const int mod = 1e9+7;
int n,k,m,a[maxn],x[maxn],C[maxn*2][maxn*2],ans=1;
char s[maxn];
void dfs(int d,int l,int r,bool chose){
	if(chose){
		int R=1,B=1,S=0;
		for(int i=1;i<=k;i++){
			if(s[i]=='r') {if(R<=m) R++; else if(S) S--;}
			if(s[i]=='b') {if(B<R&&x[B]) S+=x[B++]-1; else if(S) S--;}
		}
		if(R>m&&(B>m||!x[B])&&!S){
			int ret=C[n-l+r][r];
			for(int i=d+1;i<=x[1];i++) S+=a[i],ret=1ll*ret*C[S][a[i]]%mod;
			ans=(ans+ret)%mod;
		}
	}
	if(d<0) return;
	int tm=m,tl=(d?2*d-1:1),tr=2*d+1;
	for(int i=0;l<=n;x[++m]=d,l+=tl+(l!=0),r+=tr+1,i++) 
		a[d]=i,dfs(d-1,l,r,i);
	m=tm;
}
int main()
{
	scanf("%d%d%s",&n,&k,s+1);
	for(int i=C[0][0]=1;i<150;i++) for(int j=C[i][0]=1;j<=i;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
	dfs(n,0,0,0);
	printf("%d\n",ans);
}

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

abc = []
m.times do 
    a, _ = gets.split
    c = gets.split.inject(0){|r, v| r | 1 << v.to_i - 1}
    abc << [a.to_i, c]
end

abc.sort_by!{|a, c| a}
r = 1 << n
dp = Array.new(r)
dp[0] = 0

abc.each do |a, c|
    (r - 1).downto(0) do |i|
        next if !dp[i]
        dp[i|c] = dp[i] + a if !dp[i|c] || dp[i|c] > dp[i] + a
    end
end

puts dp[-1] ? dp[-1] : -1

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

#define lli long long int
#define REP(i,s,l) for(lli i=s;i<l;i++)
#define DEBUG 0
#define INF (1LL<<50)
#define MOD 1000000007

int main(){
    int n; cin >> n;
    vector<int> b(100), a(n);
    for(int i=0; i<n-1; i++) cin >> b.at(i);
    int sum = b[0];
    for(int i=0; i<n-2; i++){
        sum += min(b[i],b[i+1]);
    }
    sum+=b[n-2];

    cout << sum << endl;
    return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;

class H
{
	public static void Main()
	{
		new K().Solve();
	}
}
class K
{
	const int Inf = 1073741789;
	int N, M, V;
	int[] us, vs, ws;
	List<int>[] es;
	HashSet<int> dead;
	int[] F()
	{
		var t = Console.ReadLine().Split();
		var L = t.Length;
		var I = new int[L];
		for (var i = 0; i < L; i++) I[i] = int.Parse(t[i]);
		return I;
	}
	public void Solve()
	{
		var I = F();
		N = I[0];
		M = I[1];
		us = new int[M];
		vs = new int[M];
		ws = new int[M];
		var cs = new SortedSet<int>[N];
		for (var i = 0; i < N; i++)
		{
			cs[i] = new SortedSet<int>();
			cs[i].Add(-1);
		}
		for (var i = 0; i < M; i++)
		{
			I = F();
			var a = us[i] = I[0] - 1;
			var b = vs[i] = I[1] - 1;
			var c = ws[i] = I[2] - 1;
			cs[a].Add(c);
			cs[b].Add(c);
		}
		var sep = new int[N + 1];
		for (var i = 0; i < N; i++) sep[i + 1] = sep[i] + cs[i].Count;
		dead = new HashSet<int>(sep);
		V = sep[N];
		var index = new Dictionary<int, int>[N];
		for (int i = 0, j = 0; i < N; i++)
		{
			index[i] = new Dictionary<int, int>();
			foreach (var c in cs[i]) index[i].Add(c, j++);
		}
		es = new List<int>[V];
		for (var i = 0; i < V; i++) es[i] = new List<int>();
		for (var i = 0; i < M; i++)
		{
			int a = us[i], b = vs[i], c = ws[i], u = index[a][c], v = index[b][c];
			es[u].Add(v);
			es[v].Add(u);
		}
		for (var i = 0; i < N; i++)
		{
			var l = sep[i];
			var k = sep[i + 1];
			for (var j = l + 1; j < k; j++)
			{
				es[j].Add(l);
				es[l].Add(j);
			}
		}
		var d = DijkstraFrom(0);
		Console.WriteLine(d[sep[N - 1]] == Inf ? -1 : d[sep[N - 1]]);
	}
	int[] DijkstraFrom(int from)
	{
		var d = new int[V];
		for (var i = 0; i < V; i++) d[i] = Inf;
		var queue = new PQ();
		d[from] = 0;
		queue.Enqueue(new P(from, 0));
		while (queue.Count > 0)
		{
			var p = queue.Dequeue();
			int u = p.First, tmp = d[u] + (dead.Contains(u) ? 1 : 0);
			if (d[u] < p.Second) continue;
			var k = es[u].Count;
			for (var i = 0; i < k; i++)
			{
				int v = es[u][i];
				if (d[v] > tmp) queue.Enqueue(new P(v, d[v] = tmp));
			}
		}
		return d;
	}
}
class PQ
{
	List<P> list = new List<P>();
	public int Count = 0;
	public void Enqueue(P x)
	{
		var k = x.Second;
		var pos = Count++;
		list.Add(x);
		while (pos > 0)
		{
			var p = (pos - 1) / 2;
			if (list[p].Second <= k) break;
			list[pos] = list[p];
			pos = p;
		}
		list[pos] = x;
	}
	public P Dequeue()
	{
		var value = list[0];
		var x = list[--Count];
		var k = x.Second;
		list.RemoveAt(Count);
		if (Count == 0) return value;
		var pos = 0;
		while (pos * 2 + 1 < Count)
		{
			var a = 2 * pos + 1;
			var b = 2 * pos + 2;
			if (b < Count && list[b].Second < list[a].Second) a = b;
			if (list[a].Second >= k) break;
			list[pos] = list[a];
			pos = a;
		}
		list[pos] = x;
		return value;
	}
}
class P
{
	public int First;
	public int Second;
	public P(int s = 0, int t = 0)
	{
		First = s;
		Second = t;
	}
}


Measured memory_bytes: 131772
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <stack>
#include <queue>
#include <cctype>
#include <complex>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <cassert>
#include <iomanip>

typedef long long ll;
using namespace std;



struct Slog{
	int pc;
	int time;
	int inout;
	
	Slog(){}
	Slog(int n, int t, int s) : pc(n), time(t), inout(s) {}
};

struct Slog2{
	int in;
	int out;
	
	bool operator< (const Slog2 &s) const{
		return (*this).in < s.in;
	}
};

struct Sstu{
	int num;
	vector<Slog> log;
	vector<Slog2> log2;
	
	Sstu(){}
	void MakeLog2(int N){
		vector<Slog2> list(N);
		for(int i=0;i<log.size();i++){
			if(log[i].inout == 1){
				list[log[i].pc-1].in = log[i].time;
				list[log[i].pc-1].out = log[i].time;
			}
			if(log[i].inout == 0){
				list[log[i].pc-1].out = log[i].time;
				log2.push_back(list[log[i].pc-1]);
			}
		}
		sort(log2.begin(), log2.end());
	}
	void print(){
		if(!log2.size()) return;
		cout<< " student_"<< num<< endl;
		for(int i=0;i<log2.size();i++){
			cout<< " "<< log2[i].in<< " "<< log2[i].out<< endl;
		}
	}

};

bool solve(){
	int N, M, r, q;
	cin>> N>> M;
	if(N==0 && M==0) return false;
	
	vector<Sstu> stu(M);
	for(int i=0;i<M;i++) stu[i].num = i+1;
	cin>> r;
	for(int i=0;i<r;i++){
		int t, n, m, s;
		cin>> t>> n>> m>> s;
		Slog in(n,t,s);
		stu[m-1].log.push_back(in);
	}
	for(int i=0;i<M;i++) stu[i].MakeLog2(N);
//	for(int i=0;i<M;i++) stu[i].print();
	
	cin>> q;
	for(int i=0;i<q;i++){
		int ans = 0;
		int ts, te, num;
		cin>> ts>> te>> num;
//		cout<< "  "<< ts<<" "<< te<<" "<< num<< endl;
		Sstu *s = &stu[num-1];
		bool on[1300];
		memset(on, false, sizeof(on));
		for(int j=0; j < s->log2.size(); j++){
			for(int t=s->log2[j].in; t<s->log2[j].out; t++) on[t] = true;
		}
		for(int t=ts;t<te;t++) if(on[t]) ans++;
		cout<< ans<< endl;
	}
	
	return true;
}

int main(){
	cout.setf(ios::fixed);
	cout.precision(10);
	while(solve());

	return 0;
}

 

Measured memory_bytes: 1864
class Dice(object):
    def __init__(self, name=None, *args):
        self.name = name
        self.args = args
        self.dic = {i + 1 : self.args[i] for i in range(6)}

    def roll(self,s):
        if s == 'N':
            (self.dic[1], self.dic[2], self.dic[5], self.dic[6]) = \
                (self.dic[2], self.dic[6], self.dic[1], self.dic[5])
        elif s == 'E':
            (self.dic[3], self.dic[6], self.dic[1], self.dic[4]) = \
                (self.dic[1], self.dic[3], self.dic[4], self.dic[6])
        elif s == 'W':
            (self.dic[4], self.dic[1], self.dic[3], self.dic[6]) = \
                (self.dic[1], self.dic[3], self.dic[6], self.dic[4])
        else: # s == 'S'
            (self.dic[2], self.dic[1], self.dic[5], self.dic[6]) = \
                (self.dic[1], self.dic[5], self.dic[6], self.dic[2])

    def ans(self):
            print(self.dic[1])

L = list(map(int, input().split()))
string = input()

dice = Dice('dice1',*L)

for i in range(len(string)):
    dice.roll(string[i])

dice.ans()


Measured memory_bytes: 5616
d, g = map(int, input().split())
lst = [list(map(int, input().split())) for i in range(d)]

def bitlist(n):
  res = []
  for i in range(2**n):
    pattern = []
    for j in range(n):
      if (i >> j) & 1:
        pattern.insert(0, True)
      else:
        pattern.insert(0, False)
    res.append(pattern)
  return res

res = 10000
pattern = bitlist(d)
for i in range(2**d):
  point = 0
  solve = 0
  for j in range(d):
    if pattern[i][j]:
      point += lst[j][0]*(j+1)*100 + lst[j][1]
      solve += lst[j][0]
  if point >= g:
    res = min(res, solve)
  else:
    yet = 0
    for k in range(d):
      if not pattern[i][k]:
        yet = k
    for l in range(lst[yet][0]-1):
      point += (yet+1)*100
      solve += 1
      if point >= g:
        res = min(res, solve)
        break
print(res)

Measured memory_bytes: 3188
#include <stdio.h>
int main(void){
	int k;
	int a, b;
	int flg = 0;
	scanf("%d", &k);
	scanf("%d", &a);
	scanf("%d", &b);
	for(int i=a; i<=b; i++){
		if(i%k == 0){
			flg = 1;
			break;
		}
	}
	if(flg == 0){
		printf("NG\n");
	}
	else {
		printf("OK\n");
	}
	return 0;
}

Measured memory_bytes: 1664
class Combination:                                      # 計算量は O(n_max + log(mod))
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max+1):                     # 階乗(= n_max !)の逆元を生成
            f = f * i % mod                             # 動的計画法による階乗の高速計算
            fac.append(f)                               # fac は階乗のリスト
        f = pow(f, mod-2, mod)                          # 階乗から階乗の逆元を計算。フェルマーの小定理より、　a^-1 = a^(p-2) (mod p) if p = prime number and p and a are coprime
                                                        # python の pow 関数は自動的に mod の下での高速累乗を行ってくれる
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):                   # 上記の階乗の逆元から階乗の逆元のリストを生成（＝ facinv ）
            f = f * i % mod
            facinv.append(f)
        facinv.reverse()


    def __call__(self, n, r):  # self.C と同じ
        if not 0 <= r <= n: return 0
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

##############################################################################################
import sys
input = sys.stdin.readline

mod = 10**9+7
N, K = map(int, input().split())

C = Combination(N, mod=mod)
for i in range(1,K+1):
    print((C(K-1,i-1)*(C(N-K-1,i-2) + 2*C(N-K-1,i-1) + C(N-K-1,i)))%mod if N!=K else int(i==1))



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

int main(){
  string S,T;
  cin >> S >> T;
  int count=0;
  for(int i=0;i<S.size();i++){
    if(S.at(i)!=T.at(i)){
      count++;
    }
  }
  cout << count << endl;
}

Measured memory_bytes: 3916
n = int(input())
a = list(map(int,input().split()))
rank_num = [[] for i in range(9)]
for i in range(n):
  if 1<=a[i]<=399:
    rank_num[0].append(a[i])
  if 400<=a[i]<=799:
    rank_num[1].append(a[i])
  if 800<=a[i]<=1199:
    rank_num[2].append(a[i])
  if 1200<=a[i]<=1599:
    rank_num[3].append(a[i])
  if 1600<=a[i]<=1999:
    rank_num[4].append(a[i])
  if 2000<=a[i]<=2399:
    rank_num[5].append(a[i])
  if 2400<=a[i]<=2799:
    rank_num[6].append(a[i])
  if 2800<=a[i]<=3199:
    rank_num[7].append(a[i])
  if 3200<=a[i]:
    rank_num[8].append(a[i])
 
ans = 0
for i in range(8):
  if rank_num[i]:
    ans = ans +1
 
min_ans = max(ans,1)
max_ans = ans +len(rank_num[8])
print(min_ans,max_ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define ALL(obj)   (obj).begin(),(obj).end()

#define debug(var)  do{std::cout << __LINE__ << "> " << #var << ": ";view(var);}while(0)
template<typename T> void view(T e){std::cout << e << std::endl;}
template<typename T> void view(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void view(const std::vector<std::vector<T> >& vv){ for(const auto& v : vv){ view(v); } }

using namespace std;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;

void Main() {
	int a, b; cin >> a >> b;
	if (a > 0 && b > 0) {
		cout << "Positive" << endl;
		return;
	} else if (a <= 0 && b >= 0) {
		cout << "Zero" << endl;
		return;
	} else {
		cout << ((b - a + 1) % 2 == 0 ? "Positive" : "Negative") << endl;
	}
}

int main() {
    cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(void)
{
	int n;
	int tefud[11];
	int hito;
	int ba;
	int i;
	char yama[101];
	
	while(1){
		
		cin>>n;
		
		if(n==0) break;
		
		for(i=1;i<=n;i++) tefud[i]=0;
		
		cin>>yama;
		
		hito=1; ba=0;
		for(i=0;i<100;i++){
			if(hito>n) hito=1;
			if(yama[i]=='M') tefud[hito]++;
			else if(yama[i]=='S'){
				ba+=tefud[hito]+1;
				tefud[hito]=0;
			}
			else if(yama[i]=='L'){
				tefud[hito]+=ba+1;
				ba=0;
			}
			hito++;
		}
		
		sort(tefud+1,tefud+n+1);
		
		for(i=1;i<=n;i++) cout<<tefud[i]<<" ";
		cout<<ba<<endl;
		
	}
	return 0;
}


Measured memory_bytes: 3116
n,x=map(int,input().split())
xlist= list(map(int,input().split()))
if n == 1:
  print(abs(xlist[0]-x))
  exit()
ylist = []
for i in range(n):
  ylist.append(abs(xlist[i]-x))
from functools import reduce
from math import gcd
print(reduce(gcd,ylist))

Measured memory_bytes: 20020
#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
#include <iostream>
using namespace std;

typedef long long ll;
const ll inf = 1e15;
ll mod = 1000000007;

int main() {
    int n;
    scanf("%d",&n);
    vector<int> b(n - 1,0);
    for (int i = 0; i < n - 1; i++) {
        scanf("%d",&b[i]);
    }
    int sum = 0;
    for (int i = 0; i < n - 1; i++) {
        if (i == 0) sum += b[i];
        else sum += min(b[i-1],b[i]);
    }
    sum += b[n-2];
    printf("%d\n",sum);
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Atcoder
{
    class Atcoderrrrrrr
    {
        static void Main(string[] args)
        {
            string[] s = Console.ReadLine().Split(' ');
            int N = int.Parse(s[0]);
            int M = int.Parse(s[1]);
            int X = int.Parse(s[2]);
            int Y = int.Parse(s[3]);

            int[] xs = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            int[] ys = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();

            string ans = "War";
            
            for(int i = X+1;i<=Y;i++){
                if(xs.Max()<i && i<=ys.Min()){
                    ans = "No War";
                }
            }
            Console.WriteLine(ans);
        }
    }
}


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

#define EPS (1e-10)
#define rep(i, a, b) for (int i = a; i < (int)(b); ++i)
#define rrep(i, a, b) for (int i = b - 1; i >= (int)(a); --i)
#define all(a) a.begin(), a.end()

using namespace std;
using ll = long long;
using vi = vector<int>;
using vb = vector<bool>;
using vll = vector<ll>;
using vd = vector<double>;
using vvi = vector<vi>;
using vvb = vector<vb>;

constexpr int MOD = 1000000007;
constexpr int TMAX = 3000;

struct Dish {
    int t, p;
    Dish(int t = 0, int p = 0) : t(t), p(p) {}
    Dish(const Dish& d) : t(d.t), p(d.p) {}

    bool operator<(const Dish& d) const { return (t != d.t ? t < d.t : p > d.p); }
};

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

    int n, t;
    cin >> n >> t;

    vector<Dish> in(n);
    rep(i, 0, n) { cin >> in[i].t >> in[i].p; }

    // Sort based on t.
    sort(all(in));

    vi dp(t, 0);
    int ans = 0;

    rep(i, 0, n) {
        ans = max(ans, dp.back() + in[i].p);
        rrep(j, in[i].t, t) { dp[j] = max(dp[j], dp[j - in[i].t] + in[i].p); }
    }

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

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

#define mp make_pair
#define pb push_back
#define st first
#define nd second

typedef long long ll;
typedef pair < int , int > pp;
const int mod = 1e9 + 7;
const int N   = 2e5 + 5;

ll A[N],X[N],M[N],n,k,i,p,a,x,ans;

int main(){
    scanf("%lld%lld",&n,&k);
    for(i=1;i<=n;i++){
        scanf("%lld%lld",&x,&a);
        X[i] = x;
        A[i] = a;
    }

    p = 0;
    for(i=1;i<n;i++){
        p += A[i];
        M[n-i] = p - X[i]*2;
    }

    for(i=n-1; i ;i--) M[i] = max(M[i] , M[i+1]);

    p = 0;
    for(i=n; i ;i--){
        p += A[i];
        ans = max(ans , p + X[i]-k + M[n-i+1]);
    }
    //////
    p = 0;
    for(i=n; i>1 ;i--){
        p += A[i];
        M[i-1] = p - (k-X[i])*2;
    }

    for(i=n-1; i ;i--) M[i] = max(M[i] , M[i+1]);

    p = 0;
    for(i=1;i<=n;i++){
        p += A[i];
        ans = max(ans , p - X[i] + M[i]);
    }

    cout << ans;
    return 0;
}

Measured memory_bytes: 3584
#include<iostream>
#include<cstring>

using namespace std;

int main()
{
    string S, T;

    cin >> S >> T;

    int len = S.size();
    int ans = 0;
    for (int i = 0; i <len ; i++)
        if (S[i] != T[i])
            ++ans;

    cout << ans;
}



Measured memory_bytes: 3836
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <cctype>
#define len length()
#define sz size()
#define rng(i, a, b) for(int i = a; i < b; i++)
#define rep(i, n) rng(i, 0, n)
#define srt(v) sort(v.begin(), v.end())
#define rev(s) reverse(s.begin(), s.end())
#define vi(a, n) vector<int> a(n)
#define vs(a, n) vector<string> a(n)
#define vc(a, n) vector<char> a(n)
#define psb(a) push_back(a)
#define ppb pop_back()
#define erc(S, i) S.erase(S.begin() + i)
#define ers(S, i, j) S.erase(S.begin() + i, S.begin() + j)
#define sp(n) cout << setprecision(n) << fixed
#define fst(s) s.at(0)
#define lst(s) s.at(s.len - 1)
using namespace std;

int cnt(vector<string> S,int x,int y){
    int H = S.sz;
    int W = S[0].len;
    int c=0;
    rng(i,-1,2){
        rng(j,-1,2){
            if((0<=x+i)&&(x+i<W)&&(0<=y+j)&&(y+j<H)){
                if(S[y+j].at(x+i)=='#') c++;
            }
        }
    }
    return c;
}

int main(){
    int H, W;
    cin >> H >> W;
    vs(S,H);
    rep(i,H) cin >> S[i];
    rep(i,H){
        rep(j,W){
            if(S[i].at(j)=='.'){
                S[i].at(j)=char(cnt(S,j,i)+'0');
            }
        }
    }
    rep(i,H) cout << S[i] << endl;
    return 0;
}

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

int main(){
  int N,i,sum=0;
  bool a = true;
  cin >> N;
  vector<int> v(N);

  for(i=0;i<N;i++)
  cin >> v.at(i);

  do{
    for(i=0;i<N;i++){
      if(v.at(i)%2){
        a = false;
        break;
      }
      else{
        v.at(i) = v.at(i)/2;
      }
    }
    if(a==true)
    sum++;
  }while(a==true);
  cout << sum << endl;
}


Measured memory_bytes: 256
open Batteries

let () =
  let find_opt f t =
    let rec loop = function
      | [] -> None
      | x :: l -> if f x then Some x else loop l
    in
    loop t
  in

  let a = Scanf.scanf "%s\n" (fun a -> a) in
  let input_char_list = BatString.to_list a in
  let all_chars = ['a';'b';'c';'d';'e';'f';'g';'h';'i';'j';'k';'l';'m';'n';'o';'p';'q';'r';'s';'t';'u';'v';'w';'x';'y';'z';] in

  let res =
    if (String.length a < 26)
    then (
      let hoge input_chars all_chars =
        let rec aux l = match l with
          | [] -> []
          | hd :: tl -> 
            (
              match (find_opt (fun x -> x = hd) input_chars) with
                Some x -> aux tl 
              | None -> [hd]
            )
        in
        aux all_chars
      in
      BatList.append input_char_list (hoge input_char_list all_chars) |> BatString.of_list
    )
    else (
      if (a = "zyxwvutsrqponmlkjihgfedcba")
      then ("-1")
      else (

        let rec loop l accum = match l with
          | hd1 :: hd2 :: tl ->
            if ((BatChar.code hd1) < (BatChar.code hd2))
            then
              loop (hd2 :: tl) (List.append accum [hd1])
            else
              let accum = List.append accum [hd1] in
              let accum = List.sort compare accum in
              let replacer = List.find (fun x -> x > hd2) accum in
              replacer :: tl
          | hd :: [] -> []
          | [] -> []
        in
        loop (List.rev input_char_list) [] |> 
        List.rev |>
        BatString.of_list
      )
    )
  in print_endline res


Measured memory_bytes: 1024
#[allow(unused_imports)]
use itertools::Itertools;
#[allow(unused_imports)]
use num::Integer;
#[allow(unused_imports)]
use proconio::derive_readable;
use proconio::fastout;
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::*;
#[allow(unused_imports)]
use std::cmp;

#[fastout]
fn main() {
  input! {
    a: i64,
    b: f64,
  }
  let b = (b * 100.0 + 0.5) as i64;

  println!("{}", a * b / 100);
}


Measured memory_bytes: 2152
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define badi_val 10e13
int main(){	
	ios_base::sync_with_stdio(false);
	    cin.tie(NULL);
	   	int sx , sy , tx , ty;
	   	cin >> sx >> sy >> tx >> ty;
	   	int dx = tx - sx;
	   	int dy = ty - sy;
	   	cout << string(dy,'U');
	   	cout << string(dx,'R');
	   	cout << string(dy,'D');
	   	cout << string(dx,'L');
	   	cout << 'L';
	   	cout << string(dy + 1,'U');
	   	cout << string(dx + 1,'R');
	   	cout << 'D';
	   	cout << 'R';
	   	cout << string(dy + 1,'D');
	   	cout << string(dx + 1,'L');
	   	cout << 'U';
		return 0; 
}

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

int a[500][500];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int k;
	cin>>k;
	if(k==1)
		return cout<<1<<endl<<1<<endl,0;
	int n = k;
	while(n%4!=0)	n++;
	for(int i=0;i<n/2;i++)
		for(int j=0;j<n/2;j++){
			a[i][j]=(i+j)%(n/2);
			if(i&1)	a[i][j]+=n/2;	
			if(a[i][j]>=k)	a[i][j]-=n/2;
		}
	cout<<n/2<<endl;
	for(int i=0;i<n/2;i++,cout<<'\n')
		for(int j=0;j<n/2;j++)
			cout<<a[i][j]+1<<' ';
}


Measured memory_bytes: 2176
/*
 * atcoder/abc138/c.cpp
 */

// C++ 14
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring> // memset
#include <cassert>
using namespace std;
#define ll long long
#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)
template <class T> ostream & operator << (ostream & out, vector<T> const & v) {
  for (auto &&a: v) out << a << " "; out << endl; return out;
}
template <class T> void dump(T &a) { cout << a << endl; }
void solve();
int main() { solve(); return 0; }


/*
 *      abc
 * 2   a   bc  b/4 c/4
 *       b   c
 */
void solve() {
  cout.precision(15); cout << fixed;
  int n;
  cin >> n;
  vector<double> A(n);
  loop(i,0,n) cin >> A[i];
  sort(A.rbegin(), A.rend());
  double total = 0.0;
  loop(i,0,n) {
    total += A[i] * (1/pow(2, min(n-1, i+1)));
  }
  cout << total << endl;
}


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

int main(){
    int n;
    cin >> n;
    vector<int> v(n);
    for(int i=0;i<n;i++) cin >> v[i];
    sort(v.begin(),v.end());
    cout << abs(v.front()-v.back()) << endl;;

    return 0;
}


Measured memory_bytes: 256
n = int(input())
ab = [list(map(int, input().split())) for _ in range(n)]

ab.sort(key=sum, reverse=True)

sol = 0

for i, x in enumerate(ab):
  if i % 2:
    sol -= ab[i][1]
  else:
    sol += ab[i][0]

print(sol)


Measured memory_bytes: 32224
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
using namespace std;

#define f first
#define s second
#define endl "\n"
#define pb push_back
#define  oo 0x3f3f3f3f
#define limit 1000000007
#define two pair<int,int>
#define mod(x,m) ((x%m+m)%m)
#define all(v) v.begin(),v.end()
#define max3(x,y,z) max(x,max(y,z))
#define min3(x,y,z) min(x,min(y,z))
#define fori(x,n) for(int i = x; i < n; i++)
#define forj(y,m) for(int j = y; j < m; j++)
#define fork(z,p) for(int k = z; k < p; k++)
#define fastio std::ios::sync_with_stdio(false)
#define watch(x) cout << (#x) << " is " << (x) << "\n"
#define input_from_file  freopen("input.txt", "r", stdin);

int main(){
   //input_from_file;
   fastio;
   int n,x; cin>>n>>x;
   vector<int> v(n);
   fori(0,n) cin>>v[i];
   int p = 0;
   int c = 1;
   fori(0,n){
     if(p+v[i] > x) break;
     c++;
     p += v[i];
   }
   cout<<c<<endl;
}


Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
mod = 1000000007

ans = 0
for i in range(60):
    cont = 0
    for j in range(n):
        if (a[j] >> i & 1):
            cont += 1
    now = cont * (n-cont) % mod
    for j in range(i):
        now  = now * 2 % mod
    ans += now
    ans %= mod
print(ans)

Measured memory_bytes: 122936
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    def main():
        X,Y=map(int,input().split())
        n=(-X+2*Y)/3
        m=(2*X-Y)/3

        # https://atcoder.jp/contests/abc156/submissions/11621672
        def modpow(a, b, mod=10 ** 9 + 7):
            ret = 1
            while b > 0:
                if b % 2 == 1:
                    ret = ret * a % mod
                a = a * a % mod
                b //= 2
            return ret
        
        
        def modcomb(n, c, mod=10 ** 9 + 7):
            if c > n - c:
                c = n - c
            u, d = 1, 1
            for i in range(c):
                u = u * (n - i) % mod
                d = d * (i + 1) % mod
            return u * modpow(d, mod - 2) % mod
        
        
        """mod = 10 ** 9 + 7
        n, a, b = map(int, input().split())
        ans = (modpow(2, n) - 1) % mod
        ans = (ans-modcomb(n, a)) % mod
        ans = (ans-modcomb(n, b)) % mod
        print(ans)"""
        
        # combどうしの積をとると余りがずれるので避ける！　普通のcombを計算して最後にmodをとって。
        
        # comb(n + k - 1, n) # 重複組み合わせkHn．k種類の箱にn個の玉        
        if n.is_integer() and m.is_integer() and n>=0 and m>=0:
            return modcomb(int(n+m),int(n))
        else: return 0
    print(main())
    
resolve()

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

#define rep(i,a,b) for(int i=a;i<b;i++)
#define repd(i,a,b) for(int i=a;i>=b;i--)
#define llrep(i,a,b) for(ll i=a;i<b;i++)
#define llrepd(i,a,b) for(ll i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
using namespace std;
void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60; const ll MOD = 1000000007;
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 (b < a) { a = b; return 1; } return 0; }
static const double pi = 3.141592653589793;

//---------------------------------------------------------------------------------------------------
vector<ll> edge[200000];
ll sirbe[200000];

void dfs(int n, int p) {
    fore(e, edge[n]) {
        if (e != p && sirbe[e] == 0) {
            // cout << e << " " << n << " " << p << endl;
            sirbe[e] = n + 1;
            dfs(e, n);
        }
    }
}

void _main(){
    ll N ,M; cin >> N >> M;
    rep(i, 0, N) {
        edge[i] = vector<ll>();
        sirbe[i] = 0;
    }
    rep(i, 0, M) {
        ll A, B; cin >> A >> B;
        A--; B--;
        edge[A].push_back(B);
        edge[B].push_back(A);
    }
    queue<ll> q; q.push(0); sirbe[0] = infl;
    while(!q.empty()){
        ll now = q.front();
        q.pop();
        // cout << " " << now << endl;
        fore(e, edge[now]) {
            if (e != now && sirbe[e] == 0) {
                // cout << e << " " << now + 1 << endl;
                sirbe[e] = now + 1;
                q.push(e);
            }
        }
    }
    bool res = true;
    rep(i, 1, N) {
        if (sirbe[i] == 0) res = false;
    }
    if (res) {
        cout << "Yes" << endl;
        rep(i, 1, N) {
            cout << sirbe[i] << endl;
        }
    }else{
        cout << "No" << endl;
    }
}


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

#define int long long
const double PI = 3.14159265358979323846;
typedef vector<int> vint;
typedef pair<int, int> pint;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

int N, C;
int D[33][33], c[550][550];
int iwa[3][33];
int idx[3][33];
signed main() {
    cin >> N >> C;
    for (int i = 0; i < C; i++) {
        for (int j = 0; j < C; j++) {
            cin >> D[i][j];
        }
        idx[0][i] = i;
        idx[1][i] = i;
        idx[2][i] = i;
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> c[i][j];
            c[i][j]--;
        }
    }
    for (int i = 0; i < C; i++) {
        for (int y = 0; y < N; y++) {
            for (int x = 0; x < N; x++) {
                iwa[(y + x) % 3][i] += D[c[y][x]][i];
            }
        }
    }
    sort(idx[0], idx[0] + C, [](int a, int b) { return iwa[0][a] < iwa[0][b]; });
    sort(idx[1], idx[1] + C, [](int a, int b) { return iwa[1][a] < iwa[1][b]; });
    sort(idx[2], idx[2] + C, [](int a, int b) { return iwa[2][a] < iwa[2][b]; });
    cerr << iwa[0][idx[0][0]] << endl;
    int ans = LLONG_MAX;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            for (int k = 0; k < 3; k++) {
                if (idx[0][i] == idx[1][j] || idx[0][i] == idx[2][k] || idx[1][j] == idx[2][k]) {
                    continue;
                }
                ans = min(ans, iwa[0][idx[0][i]] + iwa[1][idx[1][j]] + iwa[2][idx[2][k]]);
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 2432
s, k = input(), int(input())

sub_str = set()
for i in range(len(s)):
    for j in range(1, k+1):
        if i + j <= len(s):
            sub_str.add(s[i:i+j])

sub_lst = sorted(list(sub_str))
print(sub_lst[k-1])


Measured memory_bytes: 4592
#include <bits/stdc++.h>
using namespace std;
int W,a,b;
int main(){
  cin >> W >> a >> b;
  if(max(a,b)-min(a,b)-W>0) cout << max(a,b)-min(a,b)-W << endl;
  else cout << "0" << endl;
  return 0;
}


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

int main() {
  string S, T; cin >> S >> T;

  int start = -1;
  for (int i = 0; i < S.size(); i++) {
    int can = 0;
    for (int j = 0 + can; j < T.size(); j++) {
      if (S[i + can] == T[j] || S[i + can] == '?') {
        can++;
        if (can == T.size()) start = i;
        else continue;
      } else break;
    }
  }

  if (start >= 0) S.replace(S.begin() + start, S.begin() + start + T.size(), T);
  for (int i = 0; i < S.size(); i++) if (S[i] == '?') S[i] = 'a';

  if (start >= 0) cout << S << endl;
  else cout << "UNRESTORABLE" << endl;

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  cin>>n;
  vector<int>num(n),p(n),q(n);
  for(int i=0;i<n;i++)num[i]=i;
  for(int i=0;i<n;i++)cin>>p[i];
  for(int i=0;i<n;i++)cin>>q[i];
  int start=0;
  int last=0;
  int count=0;
  do{
    int counts=0;
    int countl=0;
      for(int i=0;i<n;i++){
        //cout<<num[i]+1<<p[i]<<q[i]<<endl;
        if(num[i]+1==p[i])counts++;
        if(num[i]+1==q[i])countl++;
      }
      count++;
      //cout<<counts<<" "<<countl<<" "<<count<<endl;
      if(counts==n)start=count;
      if(countl==n)last=count;
  }while(next_permutation(num.begin(),num.end()));
  cout<<abs(start-last)<<endl;
  return 0;
}
  

  


Measured memory_bytes: 3564
# -*- coding: utf-8 -*-
import sys

N, M = map(int, input().split())
s = []
g = []
for i in range(M):
    a, b = map(int, input().split())
    if a == 1 and b == N:
        print("POSSIBLE")
        sys.exit()
    if a == 1:
        s.append(b)
    elif b == N:
        g.append(a)

if len(set(s) & set(g)) != 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Measured memory_bytes: 21852
#include<iostream>
#include<algorithm>
#include<string>
#include<map>
#include<vector>
#include<set>
#include<iomanip>
#include<cmath>
using namespace std;
typedef long long ll;
typedef long long int llint;
typedef pair<ll, ll> pa;
#define MM 1000000000
#define MOD MM+7
#define MAX 101000
#define MAP 110
#define initial_value -1
#define MAX_T 1001
#define Pair pair<int,int>
#define chmax(a,b) (a<b ? a=b:0)
#define chmin(a,b) (a>b ? a=b:0)
#define INF (1 << 29) //536870912
const long double PI = acos(-1);
const ll DEP = 1e18;
int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};
int main(){
    int N; cin >> N;
    ll a[100001];
    ll ans = 0;
    for(int i = 0; i < N; i++){
        cin >> a[i];
    }
    for(int i = 0; i < N; i++){
        ans += (a[i]/2);
        a[i] = a[i] % 2;
        if(a[i] == 1 && i < N-1 && a[i+1] > 0){
            ans++;
            a[i+1]--;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 1024