akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#include<string.h>
int main(){
  int n;
  scanf("%d",&n);
  char s[n][11];
  for(int i=0;i<n;i++){
    scanf("%s",s[i]);
  }
  for(int i=1;i<n;i++){
    for(int j=0;j<n;j++){
      if(s[i][0] != s[i-1][strlen(s[i-1])-1]){
        printf("No");
        return 0;
      }
      if(strcmp(s[i],s[j]) == 0 && i!=j){
        printf("No");
        return 0;
      }
    }
  }
  printf("Yes");
  return 0;
}

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

const ll LINF = 1e18;
const int INF = 1e9;
const ll MOD = 1000000007;

int main(){

    int n, m, c;
    cin >> n >> m >> c;

    vector<vector<int>> a(n, vector<int>(m));
    vector<int> b(m);
    for(int i = 0; i < m; i++){
        cin >> b[i];
    }

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> a[i][j];
        }
    }

    int ans = 0;

    for(int i = 0; i < n; i++){
        int t = 0;
        for(int j = 0; j < m; j++){
            t += a[i][j] * b[j];
        }
        if(t + c > 0) ans++;
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <algorithm>

using ull = unsigned long long;
int main() {
	ull value, Y;
	scanf("%llu %llu", &value, &Y);

	int count = 0;
	while (value <= Y) {
		count++;
		value *= 2;
	}
	printf("%d\n", count);
}

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

namespace arc076_a
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] x = Console.ReadLine().Split().Select(int.Parse).ToArray();
            if (x.Max() - x.Min() > 1) Console.WriteLine(0);
            else
            {
                long ret1 = 1;
                for (int i = 1; i <= x[0]; i++)
                {
                    ret1 *= i;
                    ret1 %= 1000000007;
                }
                long ret2 = x.Max() == x.Min() ? 2 : 1;
                for (int i = 1; i <= x[1]; i++)
                {
                    ret2 *= i;
                    ret2 %= 1000000007;
                }
                long ret = ret1 * ret2;
                Console.WriteLine(ret % 1000000007);
            }
        }
    }
}

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

using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define MIN(a,b) ((a)>(b)? (b): (a))
#define MAX(a,b) ((a)<(b)? (b): (a))

const long long INF = 1LL << 60;
typedef unsigned long long ll;
const long long MOD = 1000000000 + 7;

int main(){
    char a,b;
    cin >> a >> b;
    if(a=='H'){
        cout << b << endl;
    }else{
        if(b=='H'){
            cout << "D" << endl;
        }else{
            cout << "H" << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 636
#include <stdio.h>
#include <string.h>
#define STR_SIZE 100
int add_bignum(char a[], char b[], char out[]) {
	int alen = strlen(a);
	int blen = strlen(b);
	if (alen >= 81 || blen >= 81) {
		return 0;
	}
	char buf[STR_SIZE] = "";
	--alen;
	--blen;
	int i, digit, tmp = 0;
	for (i = 0; i < 100; i++) {
		if (alen >= 0 && blen >= 0)
			digit = (int)a[alen] + (int)b[blen] - '0' - '0';
		else if (alen >= 0 && blen < 0)
			digit = a[alen] - '0';
		else if (alen < 0 && blen >= 0)
			digit = b[blen] - '0';
		digit += tmp;

		buf[i] = (char)((digit % 10) + '0');
		tmp = (char)(digit / 10) & 1;

		--alen;
		--blen;
		if (alen < 0 && blen < 0)
			break;
	}
	if (tmp) {
		buf[++i] = '1';
	}
	int clen = strlen(buf);
	if (clen >= 81) {
		return 0;
	}
	--clen;
	for (i = 0; clen >= 0; clen--, i++) {
		out[i] = buf[clen];
	}
	out[i] = '\0';
	return 1;
}
int main() {
	int n;
	char a[STR_SIZE], b[STR_SIZE], c[STR_SIZE];
	scanf("%d", &n);
	for (; n; n--) {
		scanf(" %100s %100s", a, b);
		if (!add_bignum(a, b, c)) {
			puts("overflow");
		} else {
			puts(c);
		}
	}
	return 0;
}

Measured memory_bytes: 588
/**
 *   author: r1933
**/
#include "bits/stdc++.h"

using namespace std;

#define all(x) x.begin(), x.end()
using i64 = long long;

constexpr int INF = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N, K;
  cin >> N >> K;
  if (N % 2 != 0) N += 1;
  int norm = N / 2;
  cout << (K <= norm ? "YES" : "NO") << "\n";
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <utility>
#include <iomanip>
using namespace std;
typedef long long ll;
const ll MOD = 1e9+7;
ll a[100000];
int main()
{
	int n;
	ll ans=0;
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>a[i];
	if(a[n-1]!=2)
	{
		cout<<-1<<endl;
		return 0;
	}
	ll l=1;ll r=1;
	for(int i=n-2;i>-1;i--)
	{
		ll tmpl,tmpr;
		tmpl=a[i+1]*l/a[i];
		if((a[i+1]*l)%a[i]!=0)
			tmpl++;
		tmpr=(a[i+1]*(r+1)-1)/a[i];
		if(tmpl>tmpr)
		{
			cout<<-1<<endl;
			return 0;
		}
		if(a[i]*tmpl<a[i+1]*l)
			tmpl=tmpr;
		l=tmpl;r=tmpr;
	}
	l=l*a[0];
	r=r*a[0]+a[0]-1;
	cout<<l<<" "<<r<<endl;
	return 0;
}

Measured memory_bytes: 1024
#include <iostream> 
#include <cstdio> 
#include <cstdlib>  
#include <algorithm> 
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <tuple>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include<iomanip>
#include<functional>
using namespace std;
typedef long long ll;


long long GCD(long long a, long long b) {
    if (b == 0) return a;
    else return GCD(b, a % b);
}


int main() {
    int n;
    cin >> n;
    int cnt = 0;
    for (int i = 1; i < n; i++) {
        for (int j = 1; j * i < n; j++) {
            int c = n - i * j;
            if (c + i * j == n) cnt++;
        }
    }
    cout << cnt << endl;
}


Measured memory_bytes: 3632
import java.io.{BufferedReader, InputStream, InputStreamReader, PrintWriter}
import java.util.StringTokenizer

import scala.collection.mutable
import scala.util.Sorting
import math.{abs, max, min}
import scala.collection.mutable.{ArrayBuffer, ListBuffer}
import scala.reflect.ClassTag

object Main {
  val MOD = 1000000007
  val out = new PrintWriter(System.out)
  def solve(): Unit = {
    val sc = new InputReader(System.in)
    val N = sc.nextInt()
    val A = map(N)(_ => sc.nextInt())
    val S = Array.ofDim[Int](100001)
    A.foreach(a => S(a) += 1)
    val ans = map(S.length - 2) { i =>
      S(i) + S(i + 1) + S(i + 2)
    }.max

  
    out.println(ans)
  }


  def main(args: Array[String]): Unit = {
    solve()
    out.flush()
  }


  class InputReader(val stream: InputStream) {
    private val reader = new BufferedReader(new InputStreamReader(stream), 32768)
    private var tokenizer: StringTokenizer = null

    def next: String = {
      while (tokenizer == null || !tokenizer.hasMoreTokens)
        tokenizer = new StringTokenizer(reader.readLine)
      tokenizer.nextToken
    }

    def nextInt(): Int = next.toInt
    def nextLong(): Long = next.toLong
    def nextChar(): Char = next.charAt(0)
  }

  private def rep(n: Int)(f: Int => Unit): Unit = (0 until n) foreach f

  private def map[@specialized A: ClassTag](n: Int)(f: Int => A): Array[A] = {
    val res = Array.ofDim[A](n)
    (0 until n) foreach (i => res(i) = f(i))
    res
  }

  private implicit class ArrayOpts[A](val as: Array[A]) extends AnyVal {
    def maxByOpt[B: Ordering](f: A => B): Option[A] = {
      if (as.nonEmpty) Some(as.maxBy(f)) else None
    }

    def grpBy[K](f: A => K): mutable.Map[K, ArrayBuffer[A]] = {
      val map = mutable.Map.empty[K, ArrayBuffer[A]]
      rep(a => map.getOrElseUpdate(f(a), ArrayBuffer()) += a)
      map
    }

    def rep(f: A => Unit): Unit = {
      as.indices foreach (i => f(as(i)))
    }

    def sumBy[B](f: A => B)(implicit num: Numeric[B]): B = {
      var sum = num.zero
      rep(a => sum = num.plus(sum, f(a)))
      sum
    }
  }

  private implicit class IterableOpts[A](val as: Iterable[A]) extends AnyVal {
    def sumBy[B](f: A => B)(implicit num: Numeric[B]): B = {
      as.foldLeft(num.zero)((acc, a) => num.plus(acc, f(a)))
    }
  }

}


Measured memory_bytes: 36612
import java.util.Scanner;

class Main {

	public static void main(String[] a) {
		// 入力
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int result[] = new int[n];
		for (int i = 0; i < result.length; i++) {
			result[i] = sc.nextInt();
		}
		sc.close();

		// 出力
		for (int j2 = 0; j2 < result.length; j2++) {
			System.out.print(result[j2]);
			if (j2 < result.length - 1) {
				System.out.print(" ");
			} else {
				System.out.println();
			}
		}
		for (int i = 1; i < result.length; i++) {
			int keep = result[i];
			int j = i - 1;
			while (j >= 0 && keep < result[j]) {
				result[j + 1] = result[j];
				j--;
				result[j + 1] = keep;
			}
			for (int j2 = 0; j2 < result.length; j2++) {
				System.out.print(result[j2]);
				if (j2 < result.length - 1) {
					System.out.print(" ");
				} else {
					System.out.println();
				}
			}
		}
	}
}

Measured memory_bytes: 25940
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include <math.h>

int main() {

    int arr[5];
    int k;
    scanf("%d %d %d %d %d %d", &arr[0], &arr[1], &arr[2], &arr[3], &arr[4], &k);

    if (arr[4] - arr[0] <= k) {
        puts("Yay!");
    } else {
        puts(":(");
    }

    return 0;

}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;

using ll = long long int;

int main() {
    // Input
    int N;
    ll K;
    vector<int> A;

    cin >> N >> K;
    A = vector<int>(N);
    rep(i, N) cin >> A[i];

    // Process
    int cnt = 0;
    vector<int> log;
    vector<int> visited(N, -1);

    log.emplace_back(1);
    while (visited[log[cnt] - 1] == -1) {
        visited[log[cnt] - 1] = cnt;

        const int newTown = A[log[cnt] - 1];
        log.emplace_back(newTown);
        cnt++;
    }
    int start = visited[log[cnt] - 1];
    int loop = cnt - start;

    int ans;
    if (K < cnt) {
        ans = log[K];
    } else {
        ll k = (K - start) % loop;
        ans = log[k + start];
    }

    // Output
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 5876
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n,m,q;cin>>n>>m>>q;
	int l,r;
	vector <int> adj[505];
	for(int i=0;i<m;i++)
	{
		cin>>l>>r;
		adj[l].push_back(r);
	}

	for(int i=1;i<=500;i++)
		sort(adj[i].begin(),adj[i].end());

	int ans;
	while(q--)
	{
		cin>>l>>r;
		ans=0;
		for(int i=l;i<=r;i++)
		{
			//cout<<i<<" "<<adj[i].size()<<endl;
			if(adj[i].size()!=0)
			{
				int idx=upper_bound(adj[i].begin(),adj[i].end(),r)-adj[i].begin();
				//cout<<idx<<endl;
				ans+=idx;
			}
		}
		cout<<ans<<endl;
	}

}

Measured memory_bytes: 2176
#include <stdio.h>

int main()
{
	int row, col, i, j, total = 0;
	scanf("%d %d", &row, &col);
	int data[row][col], colsum[row], rowsum[col];
	for (j = 0; j < col; j++) {
		rowsum[j] = 0;
	}
	for (i = 0; i < row; i++) {
		colsum[i] = 0;
		for (j = 0; j < col; j++) {
			scanf("%d", &data[i][j]);
		}
	}
	for (i = 0; i < row; i++) {
		for (j = 0; j < col; j++) {
			printf("%d ",data[i][j]);
			colsum[i] += data[i][j];
			rowsum[j] += data[i][j];
			total += data[i][j];
		}
		printf("%d\n", colsum[i]);
	}
	for (i = 0; i < col; i++) {
		printf("%d ", rowsum[i]);
	}
	printf("%d\n", total);
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
int main() {
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	if(a<=c&&b<=d){
		if(b-c<0){
			cout<<0<<endl;
		}
		else{
		cout<<b-c<<endl;
		}
	}
	else if(a>=c&&b>=d){
		if(d-a<0){
			cout<<0<<endl;
		}
		else{
		cout<<d-a<<endl;
		}
	}
	else if(a<=c&&b>=d){
		cout<<d-c<<endl;
	}
	else{
		cout<<b-a<<endl;
	}
}

Measured memory_bytes: 256
n = int(input())
w = [input() for i in range(n)]

def checkDuplication(wordList):
    if len(set(wordList)) == n:
        return True
    else :
        return False

def checkMatch(wordList):
    checkCount = 0
    for i in range(n-1):
        if wordList[i][-1] == wordList[i+1][0]:
            pass
        else:
            checkCount += 1
    
    if checkCount:
        return False
    else: 
        return True

if checkMatch(w) and checkDuplication(w):
    print('Yes')
else:
    print('No')


        

Measured memory_bytes: 3060
import java.util.*; import java.io.*; import java.math.*;
public class Main{
	//Don't have to see. start------------------------------------------
	static class InputIterator{
		ArrayList<String> inputLine = new ArrayList<String>(1024);
		int index = 0; int max; String read;
		InputIterator(){
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			try{
				while((read = br.readLine()) != null){
					inputLine.add(read);
				}
			}catch(IOException e){}
			max = inputLine.size();
		}
		boolean hasNext(){return (index < max);}
		String next(){
			if(hasNext()){
				return inputLine.get(index++);
			}else{
				throw new IndexOutOfBoundsException("There is no more input");
			}
		}
	}
	static HashMap<Integer, String> CONVSTR = new HashMap<Integer, String>();
	static InputIterator ii = new InputIterator();//This class cannot be used in reactive problem.
	static PrintWriter out = new PrintWriter(System.out);
	static void flush(){out.flush();}
	static void myout(Object t){out.println(t);}
	static void myerr(Object t){System.err.print("debug:");System.err.println(t);}
	static String next(){return ii.next();}
	static boolean hasNext(){return ii.hasNext();}
	static int nextInt(){return Integer.parseInt(next());}
	static long nextLong(){return Long.parseLong(next());}
	static double nextDouble(){return Double.parseDouble(next());}
	static ArrayList<String> nextStrArray(){return myconv(next(), 8);}
	static ArrayList<String> nextCharArray(){return myconv(next(), 0);}
	static ArrayList<Integer> nextIntArray(){
		ArrayList<String> input = nextStrArray(); ArrayList<Integer> ret = new ArrayList<Integer>(input.size());
		for(int i = 0; i < input.size(); i++){
			ret.add(Integer.parseInt(input.get(i)));
		}
		return ret;
	}
	static ArrayList<Long> nextLongArray(){
		ArrayList<String> input = nextStrArray(); ArrayList<Long> ret = new ArrayList<Long>(input.size());
		for(int i = 0; i < input.size(); i++){
			ret.add(Long.parseLong(input.get(i)));
		}
		return ret;
	}
	static String myconv(Object list, int no){//only join
		String joinString = CONVSTR.get(no);
		if(list instanceof String[]){
			return String.join(joinString, (String[])list);
		}else if(list instanceof ArrayList){
			return String.join(joinString, (ArrayList)list);
		}else{
			throw new ClassCastException("Don't join");
		}
	}
	static ArrayList<String> myconv(String str, int no){//only split
		String splitString = CONVSTR.get(no);
		return new ArrayList<String>(Arrays.asList(str.split(splitString)));
	}
	public static void main(String[] args){
		CONVSTR.put(8, " "); CONVSTR.put(9, "\n"); CONVSTR.put(0, "");
		solve();flush();
	}
	//Don't have to see. end------------------------------------------
	static void solve(){//Here is the main function
		int N = nextInt();
		ArrayList<Integer> list = nextIntArray();
		int count = 0;
		for(int i = 0; i < N; i++){
			if(list.get(i) % 2 == 1){
				count++;
			}
		}
		if(count % 2 == 0){
			myout("YES");
		}else{
			myout("NO");
		}
	}
	//Method addition frame start



	//Method addition frame end
}


Measured memory_bytes: 48204
#include <stdio.h>

int main(void){
	int N, L[200], i, j, temp;
	scanf("%d", &N);
	for (i = 0; i < N*2; i++){
		scanf("%d", &L[i]);
	}
	for (i = 0; i < 2*N-1; i++){
		for (j = N*2-1; j >i; j--){
			if (L[j] > L[j-1]){
				temp = L[j];
				L[j] = L[j-1];
				L[j-1] = temp;
			}
		}
	}
	temp = 0;
	for (i = 1; i < N*2; i += 2){
		temp += L[i];
	}
	printf("%d\n", temp);
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define name "test"
#define fi first
#define se second
#define ll long long
#define db double
#define pb push_back
#define wrln cout<<'\n';
#define ii pair<int,int>
#define li pair<long long,int>
#define iii pair<int,ii>

using namespace std;
const int N=2e3+100;

ll a[N][N],p[N],x,n,f[N],res;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if ( fopen(name".inp","r") )
    {
        freopen(name".inp","r",stdin);
        freopen(name".out","w",stdout);
    }
    string s;
    cin>>s;
    if (s[s.size()-1]=='s') cout<<s<<"es"; else cout<<s<<"s";
}


Measured memory_bytes: 3660
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<limits>
#include<set>
#include<deque>
#include<queue>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repe(i, n) for (int i = 0; i <= (int)(n); i++)
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define ANS cout << ans << endl
#define all(a) a.begin(),a.end()
#define SORT(a) sort(all(a))
#define REVERSE(a) reverse(all(a))
#define KOZYUN(a) sort(all(a),greater<int>())
#define int ll
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORe(i, m, n) for(int i = m;i <= n;i++)
#define VIin(a) for(int i=0; i<a.size(); i++) cin >> a[i]
#define OUT(a) cout << a << endl
#define IN(a) cin >> a
#define INT(a) int a; cin >> a
typedef vector<int> VI;
typedef vector<VI> VVI;
const int MOD=1e9+7;
const long long INF = 1LL << 60;
/*最大公約数*/int gcd(int x, int y) { return y ? gcd(y,x%y) : x;}
/*最小公倍数*/int lcm(int a, int b) { int g = gcd(a, b); return a / g * b; }
/*素数判定*/int isPrime(int n){if(n<2){return 0;}for(int i=2; i*i<=n; i++){if(n%i==0){return 0;}}return 1;}
/*約数列挙*/vector<int> getDivisor(int n){vector<int> v; for(int i=1; i*i<=n; i++){if(n%i==0){v.push_back(i);if(i!=n/i){v.push_back(n/i);}}}sort(v.begin(),v.end()); return v;}
//----------------------------------------------
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, k; cin >> n >> k;
	int ans = 0;
	while (n != 0) {
		n /= k; ans++;
	}
	ANS;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n); for(int i = 0;i < (int)(n);i++)
#define all(x) (x).begin(),(x).end()
typedef long long ll;
int main(){
    int A,B,M;
    cin >> A >> B >> M;
    int a[A],b[B];
    rep(i,A)cin >> a[i];
    rep(i,B)cin >> b[i];
    int minA = 100000;
    int minB = 100000;
    rep(i,A)minA = min(a[i],minA);
    rep(i,B)minB = min(b[i],minB);
    int ans = minA + minB;
    rep(i,M){
        int x,y,c;
        cin >> x >> y >> c;
        int price = a[x-1] + b[y-1] - c;
        ans = min(price,ans);
    }
    cout << ans << endl;
    return 0;
}

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

using namespace std;

const int N = 3e3 + 5, mod = 1e9 + 7;
int n, q, a[N], dp[N][N], inv2;

int binPow (int _a, int _m) {
    int ret = 1;
    for (; _m; _m >>= 1, _a = 1LL * _a * _a % mod) if (_m & 1) ret = 1LL * ret * _a % mod;
    return ret;
}

int main () {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    inv2 = binPow(2, mod - 2);

    cin >> n >> q;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) dp[i][j] = (a[i] > a[j]);

    for (int _ = 0; _ < q; ++_) {
        int x, y; cin >> x >> y;
        int tmpX[2][N], tmpY[2][N], tmp;
        for (int i = 1; i <= n; ++i) if (y != i) {
            tmpX[0][i] = 1LL * inv2 * (dp[x][i] + dp[y][i]) % mod;
            tmpX[1][i] = 1LL * inv2 * (dp[i][x] + dp[i][y]) % mod;
        }
        for (int i = 1; i <= n; ++i) if (x != i) {
            tmpY[0][i] = 1LL * inv2 * (dp[y][i] + dp[x][i]) % mod;
            tmpY[1][i] = 1LL * inv2 * (dp[i][y] + dp[i][x]) % mod;
        }
        tmp = 1LL * inv2 * (dp[x][y] + dp[y][x]) % mod;

        dp[x][y] = dp[y][x] = tmp;
        for (int i = 1; i <= n; ++i) if (y != i) dp[x][i] = tmpX[0][i], dp[i][x] = tmpX[1][i];
        for (int i = 1; i <= n; ++i) if (x != i) dp[y][i] = tmpY[0][i], dp[i][y] = tmpY[1][i];
    }

    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = i + 1; j <= n; ++j) ans = (ans + dp[i][j]) % mod;
    }
    while (q --) { ans = 2 * ans % mod; }

    cout << ans;

    return 0;
}


Measured memory_bytes: 35584
from math import gcd as g
#####segfunc#####
def segfunc(x, y):
    return g(x,y)
#################

#####ide_ele#####
ide_ele =0
#################

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

n=int(input())
a=list(map(int,input().split()))
seg=SegTree(a,segfunc,ide_ele)
ans=1
for i in range(n):
    p=seg.query(0,i)
    q=seg.query(i+1,n)
    ans=max(ans,g(p,q))
print(ans)








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

using ll = long long int;
using P = pair<int, int>;
using P3 = pair<ll,P>;
using PP = pair<P, P>;
constexpr int INF = 1 << 30;
constexpr ll MOD = ll(1e9) + 7;
constexpr int di[] = {0, 1, 0, -1};
constexpr int dj[] = {1, 0, -1, 0};
constexpr double EPS = 1e-8;

int solve(){
    string s;
    cin >> s;
    int n = s.size();
    bool ok = true;
    if(n%2){
        cout << "No" << endl;
        return 0;
    }
    for(int i=0;i<n;i+=2){
        ok &= s[i] == 'h' && s[i+1] == 'i';
    }
    cout << (ok ? "Yes" : "No") << endl;
    return 0;
}

int main(){
    solve();
    // while(solve()==0);
    // int t; cin >> t; for(;t>0;t--) solve();
    return 0;
}

Measured memory_bytes: 256
def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7

n = INT()
a = [MAP() for _ in range(n)]
dp = [[0,0,0] for _ in range(n+1)]

for i in range(n):
    for j in range(3):
        for k in range(3):
            if j==k:
                continue
            dp[i+1][k] = max(dp[i+1][k],dp[i][j]+a[i][k])

print(max(dp[n]))

Measured memory_bytes: 47368
#define _USE_MATH_DEFINES

#include <iostream>
#include <cstdio>
#include <memory>
#include <string>
#include <cstdlib>
#include <set>
#include <utility>
#include <vector>
#include <list>
#include <algorithm>
#include <regex>
#include <cmath>
#include <map>
#include <iterator>
#include <climits>
#include <numeric>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <queue>
#include <deque>
#include <stack>
#include <array>
#include <valarray>
#include <complex>
#include <random>
#include <functional>
#include <cassert>
#include <chrono>
#include <memory>

using namespace std;

#define int long long
//region TEMPLATE
////@formatter:off
#define double long double
typedef long long ll;
typedef unsigned long long ull;
template<typename T>void __read(T &a) { cin >> a; }
template<typename T, typename ... Args> void __read(T &a, Args &... args) { cin >> a;__read(args...);}
#define make(t, ...) t __VA_ARGS__; __read(__VA_ARGS__)
#define makev(a, n) VI a(n); FOR(n) cin >> a[i];
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define FORIT(p) for(auto it = p.begin(); it != p.end(); it++)
#define FOR(b) for(signed i = 0; i <(b); i++)
#define FORE(i, l, r) for(int i = (l); i < (r); i++)
#define NFOR(i, n) for(int i = (((int) n)-1); i >= 0; i--)
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
typedef pair<int, int> PII;
typedef pair<pair<int, int>, int> PPII;
constexpr ll M7 = 1000000007ll;
constexpr ll M9 = 1000000009ll;
constexpr ll MFFT = 998244353ll;
template<class T> void outv(T &a) { for (auto &x : a) cout << x << ' '; }
static mt19937 rnd(static_cast<unsigned>(chrono::steady_clock::now().time_since_epoch().count())); // NOLINT(cert-err58-cpp)
auto __fast_io__ = (ios_base::sync_with_stdio(false), cin.tie(nullptr)); // NOLINT(cert-err58-cpp,cppcoreguidelines-interfaces-global-init)
////@formatter:on
//endregion


int32_t main() {
    make(int, n);
    int sm = 0;
    for(int i = 0; i <= n; ++i){
        if (i % 3 != 0 && i % 5 != 0) sm += i;
    }
    cout << sm;
    return 0;
}

Measured memory_bytes: 3656
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cctype>
#include<iostream>
#include<stack>
#include<string>
#include<vector>
#include<queue>
#include<deque>
#include<algorithm>
#include<utility>
#include <map>
#include <set>

using namespace std;

#define REP(i,x) for(int i=0; i<(int)(x); i++)       // 0 <= i < x
#define REPS(i,x) for(int i=1; i<=(int)(x); i++)     // 0 < i <= x
#define RREP(i,x) for(int i=((int)(x)-1); i>=0; i--) // x > i >= 0
#define RREPS(i,x) for(int i=((int)(x)); i>0; i--)   // x >= i > 0
#define INF 100000000

typedef long long ll;
typedef pair<int, int> P;

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

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

    int a, b;
    a = n / 10;
    b = n % 1000;
    if(a % 111 == 0 || b % 111 == 0){
        cout << "Yes\n";
    }else{
        cout << "No\n";
    }

    return 0;
}



Measured memory_bytes: 256
#define _GLIBCXX_DEBUG//TLEの原因になるので注意！！！！！！！！！！！
#include<cmath>
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
vector<int> arr;
stack<int> st;
queue<int> qu;
queue<pair<int,int> > qu2;
priority_queue<int> pq;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define rep2(i,n) for(int i=1; i<=(int)(n); i++)
#define mins(x,y) x=min(x,y)
#define maxs(x,y) x=max(x,y)
typedef set<int> set_t;
typedef set<string> set_g;
typedef complex<double> xy_t;
static const int NIL = -1;
static const int INF = 1000000007;
#define mp make_pair
#define sz(x) int(x.xise())
#define mod 1000000007
#define reps(i,s,n) for(int i = s; i < n; i++)
//#define int long long

//cerrはコメントアウトしなくても通る//ただしTLEを引き起こすことがある

int a[100005];
deque<int> b;

int main(){
    int n;
    cin >> n;
    rep(i,n){
        cin >> a[i];
    }
    rep(i,n){
        if(i==0){
            b.push_back(a[i]);
        }else if(a[i]<=b[0]){
            b.push_front(a[i]);
            //sort(b.begin(),b.end());
        }else{
            int k=lower_bound(b.begin(),b.end(),a[i])-b.begin()-1;
            //cerr<<k<<endl;
            
            b[k]=a[i];
            //sort(b.begin(),b.end());
        }
        /*
        rep(i,b.size()){
            cerr<<b[i]<<' ';
        }
        cerr<<endl;
        */
    }
    int ans=b.size();
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 1024
#include"bits/stdc++.h"

using namespace std;

long long gcd(int x,int y)
{
    if(y>x) swap(x,y);
    if(y==0) return x;
    return gcd(y,x%y);
}

int main()
{
    int n;
    cin >> n;
    int t[n];
    int m=0;
    for(int i=0;i<n;i++){
        cin >> t[i];
        m=max(m,t[i]);
    }
    vector<int> v;
    for(int j=1;j<=m;j++)
        if(m%j==0){
            v.push_back(j);
        }
    v.push_back(m+10);
    long long sum=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<=(int)v.size()-1;j++){
            if(abs(t[i]-v[j])<=abs(t[i]-v[j+1])&&t[i]<=v[j]){
                sum+=abs(t[i]-v[j]);
                break;
            }
        }
    }
    cout <<sum << endl;
    return 0;
}




Measured memory_bytes: 3560
import java.util.Arrays;
import java.util.Scanner;

public class Main {

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

		int h[] = new int[300];
		int w[] = new int[300];
		int endIndex = 0;
		
		for (int i = 0; i < 300; i++) {
			h[i] = scan.nextInt();
			w[i] = scan.nextInt();

			if (h[i] == 0 && w[i] == 0) {
				endIndex = i;
				break;
			}
		}
		
		for (int i = 0; i < endIndex; i++) {
			for (int height = 0; height < h[i]; height++) {
				for (int width = 0; width < w[i]; width++) {
					System.out.print("#");
				}
				System.out.println();
			}
			System.out.println();
		}
		
		scan.close();
	}
}

Measured memory_bytes: 26656
#include "bits/stdc++.h"
using namespace std;

#define ASC(vec) vec.begin(), vec.end()		// 昇順ソート 例：sort(ASC(vec));
#define DESC(vec) vec.rbegin(), vec.rend()	// 降順ソート 例:sort(DESC(vec));
#define rep(i, n) for(i = 0; i < n; i++)

const int inf = (int)1e9 + 7;
const long long INF = 1LL << 60;

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

typedef long long ll;

// 4,8方向に探索する際に用いる配列
//int dx[4] = { 0,  0, 1, -1 };
//int dy[4] = { 1, -1, 0,  0 };
//int dx[8] = { 1, 0, -1,  0, 1, -1, -1,  1 };
//int dy[8] = { 0, 1,  0, -1, 1,  1, -1, -1 };

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

	int cnt = 0;
	
	for (int i = 0; i < s.size(); i++)
	{
		if (s[i] == 'o') cnt++;
	}
	cout << 700 + cnt * 100 << endl;
}


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

struct Edge{
    int from, to;
    double dist, limit;
    Edge(int x, int y, double d, double c){
        from = x;
        to = y;
        dist = d;
        limit = c;
    }
};

bool operator<(const Edge &e1, const Edge &e2) {
    return e1.limit >= e2.limit;
}

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

const int MAX = 50;
const int INF = 1e9;
double dist[MAX][MAX][MAX]; // 一つ前の頂点、今の頂点、今の速度
Graph graph(MAX);

void dijkstra(int s) {
    priority_queue<Edge> que;
    for(int i = 0; i < MAX; i++){
        for(int j = 0; j < MAX; j++){
            for(int k = 0; k < MAX; k++){
                dist[i][j][k] = INF;
            }
        }
    }
    for(int i = 0; i < MAX; i++) dist[i][s][1] = 0.0;
    for(int i = 0; i < graph[s].size(); i++){
        Edge e = graph[s][i];
        que.push(Edge(s, e.to, 1, e.dist));
        dist[s][e.to][1] = (double)e.dist;
    }
    while (!que.empty()) {
        int prev = que.top().from;
        int cur = que.top().to;
        double vel = que.top().dist;
        double sum = que.top().limit;
        que.pop();
        if(dist[prev][cur][(int)vel] < sum) continue;
        for(int i = 0; i < graph[cur].size(); i++){
            Edge e = graph[cur][i];
            if(e.to == prev) continue;
            for(int add = -1; add <= 1; add++){
                int nxv = vel + add;
                if(nxv <= 0 || nxv > e.limit) continue;
                double tmp = sum + (double)e.dist / (double)nxv;
                if(dist[e.from][e.to][nxv] > tmp){
                    dist[e.from][e.to][nxv] = tmp;
                    que.push(Edge(cur, e.to, nxv, tmp));
                }
            }
        }
    }
}

int main(){
    int n, m;
    while(cin >> n >> m, n | m){
        for(int i = 0; i < MAX; i++) graph[i].clear();
        int s, g;
        cin >> s >> g;
        for(int i = 0; i < m; i++){
            int x, y;
            double d, c;
            cin >> x >> y >> d >> c;
            x--; y--;
            graph[x].push_back(Edge(x, y, d, c));
            graph[y].push_back(Edge(y, x, d, c));
        }
        dijkstra(s - 1);
        double ans = INF;
        for(int i = 0; i < MAX; i++) ans = min(ans, dist[i][g - 1][1]);
        if(ans == INF){
            cout << "unreachable" << endl;
        }else{
            cout << fixed << setprecision(10) << ans << endl;
        }
    }
    return 0;
}



Measured memory_bytes: 4656
fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());

    let n: usize = sc.read();
    let k: usize = sc.read();
    let mut a: Vec<usize> = sc.vec(n);
    for _ in 0..k {
        let mut acc: Vec<i64> = vec![0; n + 1];
        for i in 0..n {
            let d = a[i];
            if i >= d {
                acc[i - d] += 1;
            } else {
                acc[0] += 1;
            }
            if i + d + 1 <= n {
                acc[i + d + 1] -= 1;
            } else {
                acc[n] -= 1;
            }
        }

        let mut b = vec![0; n];
        let mut cur = 0;
        for i in 0..n {
            cur += acc[i];
            assert!(cur >= 0);
            b[i] = cur as usize;
        }

        a = b;
        if a.iter().all(|&a| a == n) {
            break;
        }
    }

    for i in 0..n {
        if i > 0 {
            sc.write(" ");
        }
        sc.write(a[i]);
    }
    sc.write("\n");
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> Self {
        Self(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write(s.to_string().as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


Measured memory_bytes: 6772
N = int(input())
A = list(map(int, input().split()))
A.sort()
X = A[-1]
X2 = (X + 1) // 2
dd = A[-1]
for i in range(N - 1):
    d = abs(X2 - A[i])
    if d < dd:
        dd = d
        Y = A[i]
print(X, Y)

Measured memory_bytes: 14428
#include <stdio.h>

int main(){
	float w;
	while(scanf("%f",&w)!=EOF){
		if(w<=48.00){
			printf("light fly\n");
		}else if(w>48.00&&w<=51.00){
			printf("fly\n");
		}else if(w>51.00&&w<=54.00){
			printf("bantam\n");
		}else if(w>54.00&&w<=57.00){
			printf("feather\n");
		}else if(w>57.00&&w<=60.00){
			printf("light\n");
		}else if(w>60.00&&w<=64.00){
			printf("light welter\n");
		}else if(w>64.00&&w<=69.00){
			printf("welter\n");
		}else if(w>69.00&&w<=75.00){
			printf("light middle\n");
		}else if(w>75.00&&w<=81.00){
			printf("middle\n");
		}else if(w>81.00&&w<=91.00){
			printf("light heavy\n");
		}else if(w>91.00){
			printf("heavy\n");
		}			
	}
	
	return 0;
}

Measured memory_bytes: 604
from functools import reduce
import sys

n, m = [int(i) for i in input().split(" ")]
student = []
checkpoint = []
for i in range(n):
    student.append([int(i) for i in input().split(" ")])
for i in range(m):
    checkpoint.append([int(i) for i in input().split(" ")])
    
def calc_dist(loc1, loc2):
    return abs(loc1[0]-loc2[0])+abs(loc1[1]-loc2[1])

dist_list = list(map(lambda s: [calc_dist(s, c) for c in checkpoint], student))
near_checkpoint = list(map(lambda d: d.index(min(d)), dist_list))
for x in near_checkpoint:
    print(x+1)

Measured memory_bytes: 3956
#include <iostream>
using namespace std;
int main(){int n,a,b,c,d,e,f,g,h,x,y,z,w;while(cin>>n,n){while(n--){cin>>a>>b>>c>>d>>e>>f>>g>>h;x = a*e - b*f - c*g - d*h;y = a*f + b*e + c*h - d*g;z = a*g - b*h + c*e + d*f;w = a*h + b*g - c*f + d*e;cout <<x<<" "<<y<<" "<<z<<" "<<w<<endl;}}}

Measured memory_bytes: 1160
from collections import deque

n, q = map(int, input().split())
deq = deque()

for i in range(n):
    name, time = input().split(); time = int(time)
    deq.append((time, name))

ans = []
cur = 0

while deq:
    time, name = deq.popleft()
    if time <= q:
        cur += time
        ans.append('%s %d' % (name, cur))
    else:
        cur += q
        deq.append((time - q, name))

print(*ans, sep='\n')



Measured memory_bytes: 13384
#include<stdio.h>
 int main(void)
 {
     char o;
     int A,B;
 
     scanf("%d %c %d",&A,&o,&B);
 
     if(o=='+') printf("%d\n",A+B);
     if(o=='-') printf("%d\n",A-B);
 
     return 0;
 }
 

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

int main() {

    int n, x;
    cin >> n >> x;
    vector<int> vec(n);
    int nokori = x;
    rep(i, n){
        cin >> vec.at(i);
        nokori -= vec.at(i);
    }
    sort(vec.begin(), vec.end());
    nokori /= vec.at(0);

    cout << n + nokori << endl;



}

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

public class Main {

	public static void main(String[] args) {

		String[] strs;
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))){

			String line = br.readLine();
			strs = line.split(" ");
		} catch (IOException e) {

			return;
		}
		int p = Integer.parseInt(strs[0]);
		int q = Integer.parseInt(strs[1]);
		int r = Integer.parseInt(strs[2]);

		int minTime = p + q;
		if (minTime > q + r) {

			minTime = q + r;
		}
		if (minTime > r + p) {

			minTime = r + p;
		}
		System.out.println(minTime);
	}
}

Measured memory_bytes: 22996
fn is_connect(graph: &Vec<Vec<usize>>, a: usize, b: usize) -> bool {
    let n = graph.len();
    let mut queue = VecDeque::new();
    let mut used = vec![false; n];
    queue.push_back(0);
    used[0] = true;
    while let Some(cur) = queue.pop_front() {
        for &next in &graph[cur] {
            if (a, b) == (cur, next) || (b, a) == (cur, next) {
                continue;
            }
            if used[next] {
                continue;
            }
            used[next] = true;
            queue.push_back(next);
        }
    }
    used.into_iter().all(|b| b)
}

fn main() {
    let (n, m): (usize, usize) = readln();
    let mut graph = vec![Vec::new(); n];
    for i in 0..m {
        let (mut a, mut b): (usize, usize) = readln();
        a -= 1;
        b -= 1;
        graph[a].push(b);
        graph[b].push(a);
    }

    let mut answer = 0;
    for u in 0..n {
        for &v in &graph[u] {
            if u < v && !is_connect(&graph, u, v) {
                answer += 1;
            }
        }
    }
    println!("{}", answer);
}

// --- template ---
#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use std::collections::{HashMap, HashSet, VecDeque};

pub trait FromLn {
    fn fromln(s: &str) -> Self;
}
pub fn readln<T: FromLn>() -> T {
    let mut buf = String::new();
    let _ = ::std::io::stdin().read_line(&mut buf).unwrap();
    T::fromln(buf.trim())
}
pub fn readlns<T: FromLn>(n: usize) -> Vec<T> {
    let mut vs = vec![];
    for _ in 0..n {
        vs.push(readln());
    }
    vs
}
macro_rules! fromln_primitives {
    ($($t:ty),*) => { $(
        impl FromLn for $t {
            fn fromln(s: &str) -> $t {
                s.parse().unwrap()
            }
        }
    )* }
}
fromln_primitives!(
    String,
    bool,
    f32,
    f64,
    isize,
    i8,
    i16,
    i32,
    i64,
    usize,
    u8,
    u16,
    u32,
    u64
);
impl<T> FromLn for Vec<T>
where
    T: FromLn,
{
    fn fromln(s: &str) -> Vec<T> {
        s.split_whitespace().map(T::fromln).collect()
    }
}
impl FromLn for Vec<char> {
    fn fromln(s: &str) -> Vec<char> {
        s.chars().collect()
    }
}
macro_rules! fromln_tuple {
    ($($t:ident),*) => {
        impl<$($t),*> FromLn for ($($t),*) where $($t: FromLn),* {
            fn fromln(s: &str) -> ($($t),*) {
                let mut it = s.split_whitespace();
                let t = ($($t::fromln(it.next().unwrap())),*);
                assert_eq!(it.next(), None);
                t
            }
        }
    }
}
fromln_tuple!(A, B);
fromln_tuple!(A, B, C);
fromln_tuple!(A, B, C, D);
fromln_tuple!(A, B, C, D, E);
fromln_tuple!(A, B, C, D, E, F);


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,x,n) for(int i=x; i<(n); i++)
#define ALL(n) begin(n),end(n)
#define MOD (1000000007)
#define INF (1e9)
#define INFL (1e12)
 
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
template<class T>using arr=vector<vector<T>>;
template<class T>void pr(T x){cout << x << endl;}
template<class T>void prvec(vector<T>& a){rep(i, a.size()-1){cout << a[i] << " ";} cout << a[a.size()-1] << endl;}
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; }
 
int main()
{
    int i = 1;
    int k;
    while(1){
        cin >> k;
        if(k==0){
            pr(i);
            break;
        }
        i++;
    }
    return 0;}

Measured memory_bytes: 3640
N, M, X, Y = map(int, input().split())
x = list(map(int, input().split()))
y = list(map(int, input().split()))
a = 1
x.sort()
y.sort()
ans = -1
for i in range(X + 1, Y + 1):
    if x[-1] < i <= y[0]:
        ans = 1
if ans == 1:
    print("No War")
else:
    print("War")


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

int main(){
    int n; cin >> n;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    ll res = 0;
    int right = 0;
    int sum = 0;
    for(int left = 0; left < n; ++left){
        while(right < n && ((sum ^ a[right]) == (sum + a[right]))){
            sum += a[right];
            ++right;
        }
        res += right - left;
        if(left == right) ++right;
        else sum -= a[left];
    }
    cout << res << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
int main(){
	long long int n,a,b;
	cin >> n >> a >> b;
	long long int s=a+b;
	long long int p=n/s;
	long long int q=n%s;
	long long int answer;
	long long int amari;
	if(q<a){
		amari=q;
	}
	else{
		amari=a;
	}
	answer=p*a+amari;
	cout << answer << endl;



}


	


Measured memory_bytes: 256
#include<cstdio>
int main(){
	int a,b,c,d;
	scanf("%d%d%d%d",&a,&b,&c,&d);
	if(a%c == 0 && b%d == 0){
		printf("No\n");
	}else{
		int mn = (a/c) * (b/d);
		int gae = a * b - (mn * c * d);
		int pls = (mn + gae) / gae;
		printf("Yes\n");
		for(int i=0;i<a;i++){
			for(int j=0;j<b;j++){
				if(i%c == (c-1) && j%d == (d-1)){
					printf("%d ",-((c*d-1)*pls+1));
				}else{
					printf("%d ",pls);
				}
			}
			printf("\n");
		}
	}
}

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

int main() {
   ll i,c=0; string a,b; cin>>a>>b;
   for(i=0;i<a.length();i++)
   {
       if (a[i]!=b[i]) {c++;}
   } cout<<c;
	return 0;
}

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

using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

#define REP(i, l, n) for(int i=(l), i##_len=(n); i<i##_len; ++i)
#define ALL(x) (x).begin(),(x).end()
#define pb push_back

ll gcd(ll a,ll b){return b ? gcd(b,a%b) : a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

char alpha[26] = {'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'};

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

int main(){
    int n; cin >> n;
    string s, t; cin >> s >> t;
    REP(i, 0, n){
        cout << s[i] << t[i];
    }
    cout << endl;
}

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

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

    long long ans = 0;
    int n = s.size();

    for (int x=0; x < 1<<(n-1); ++x){
        long long acc =0;
        for (int i=0; i<n; ++i){
            acc *= 10;
            acc += s.at(i) - '0';
            if((x & (1<<i))==0){
                ans += acc;
                acc = 0;
            } 
        }
        ans += acc;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
a, b, c, d, e, f = gets.split.map(&:to_i)

cntA = f / (100 * a)
cntB = f / (100 * b)
maxNodo = 0
maxWater = 0
maxSugar = 0

for numA in 1..cntA
	for numB in 0..cntB
		cntC = (a*numA+b*numB)*e / c
		cntD = (a*numA+b*numB)*e / d
		for numC in 0..cntC
			for numD in 0..cntD
				sugar = c*numC + d*numD
				break if sugar > e*(a*numA+b*numB)
				water = 100*a*numA + 100*b*numB
				break if (water + sugar) > f
				temp = 100.0*sugar/(water+sugar)
				if maxNodo <= temp
					maxNodo = temp
					maxWater = water
					maxSugar = sugar
				end
			end
		end
	end
end

print(maxWater+maxSugar, " ", maxSugar, "\n")

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


int main(){
	int n,m;
	cin>>n>>m;
	int res=0;
	
	for (int i=0; i<n; i++){
		int k;
		cin>>k;
		
		res+=(k>=m);
	}

	cout<<res<<endl;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<math.h>
#include<map>
#include<iomanip>
#include<functional>
#include<limits>
#include <unordered_map>
#include <numeric>
#include <array>
#include <queue>
#include <chrono>

using namespace std;
using  ull = unsigned long long int;

#define rep(i,n,m) for(long long int i=n;i<(long long int)(m);i++)
#define INF (1<<29)


int main() {


	int N;
	cin >> N;


	int ki = 0;
	int gu = 0;
	vector<int>num(N);
	rep(i, 0, N) {
		cin >> num[i];
		if (num[i] % 2 == 0)gu++;
		else ki++;
	}
	

	ull sum = (ull)pow(3, N);
	
	//if (ki == N)sum--;

	sum -= pow(2,gu);

	cout << sum << endl;
			

	return 0;
}



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

int main(){
  int n,m;
  cin>>n>>m;
  vector<vector<int>>jobs(m);
  rep(i,n){
    int a,b;
    cin>>a>>b;
    if(a>m) continue;
    jobs[m-a].push_back(b);
  }
  priority_queue<int>q;
  ll ans=0;
  for (int i=m-1;i>=0;--i){
    for(int b:jobs[i]){
      q.push(b);
    }
    if (!q.empty()){
      ans +=q.top();
      q.pop();
    }
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 5632
#include <cstdlib>
#include <iostream>
#include <vector>
using namespace std;
template <class T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}

const long long INF = 1LL << 60;

int main() {
  int N, K;
  cin >> N >> K;
  
  vector<long long> h(110000);
  for (int i = 0; i < N; ++i) cin >> h.at(i);

  vector<long long> dp(110000);
  for (int i = 0; i < 110000; ++i) dp.at(i) = INF;

  dp.at(0) = 0;

  for (int i = 0; i < N; ++i) {
    for (int j = 1; j <= K; ++j) {
      chmin(dp.at(i + j), dp.at(i) + abs(h.at(i) - h.at(i + j)));
    }
  }

  cout << dp.at(N - 1) << endl;
}

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

const int N = 1e5;

int n,m;
vector<int> adj[N+5];
vector<int> badj[N+5];
int deg[N+5];
queue<int> qx;
int he[N+5];

int main(){
   scanf("%d%d",&n,&m);
   for(int i=1;i<=m;i++){
      int x,y;
      scanf("%d%d",&x,&y);
      adj[x].push_back(y);
      badj[y].push_back(x);
      deg[x]++;
   }
   int ans = 0;
   for(int i=1;i<=n;i++){
      if(deg[i] == 0){
         qx.push(i);
         he[i] = -1;
      }
   }
   while(!qx.empty()){
      int nx = qx.front(); qx.pop();
      he[nx]++;
      ans = max(ans,he[nx]);
      for(int i=0;i<badj[nx].size();i++){
         int now = badj[nx][i];
         he[now] = max(he[now],he[nx]);
         deg[now]--;
         if(deg[now] == 0) qx.push(now);
      }
   }
   printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 11904