akhauriyash/Code-Regression huggingface dataset:
def solve():
    rec = [1000000] * 1000000
    rec[0] = 0
    odd_rec = rec.copy()

    for i in range(1, 181):
        t = i * (i + 1) * (i + 2) // 6
        for i, tpl in enumerate(zip(rec[t:t*3+1], rec), start=t):
            a, b = tpl
            b += 1
            if b < a:
                rec[i] = b
        if t % 2:
            for i, tpl in enumerate(zip(odd_rec[t:t*34+1], odd_rec), start=t):
                a, b = tpl
                b += 1
                if b < a:
                    odd_rec[i] = b

    import sys
    file_input = sys.stdin
    n = int(file_input.readline())
    while n:
        print(rec[n], odd_rec[n])
        n = int(file_input.readline())


solve()



Measured memory_bytes: 28996
import java.util.Scanner;

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

    long t = sc.nextLong();
    long a = sc.nextLong();
    long k = sc.nextLong();

    if (k >= t + a) {
      System.out.println("0 0");
      return;
    }

    String tRest;
    String kRest;
    if (t >= k) {
      tRest = Long.toString(t - k);
      kRest = Long.toString(a);
      System.out.println(tRest + " " + kRest);
    } else if (k > t && (k - t) > a) {
      System.out.println("0 0");
    } else if (k > t && a >= (k - t)) {
      kRest = Long.toString(a - (k - t));
      System.out.println("0 " + kRest);
    }
  }
}


Measured memory_bytes: 23764
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
int n,cnt,t[N],ch[N][26],dp[N][26];
string a[N];
map<string,int>mp;
long long ans;
bool cmp(string a,string b)
{
	return a.size()!=b.size()?a.size()<b.size():a<b;
}
int main()
{
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		for(int k=0;k<26;k++)
			t[k]=0;
		for(int j=0;j<a[i].size();j++)
			t[a[i][j]-'a']++;
		int u=0;
		for(int k=0;k<26;k++)
		{
			if(t[k]==0)
				continue;
			ans+=dp[u][k];
		}
		if(a[i].size()==1)
			dp[u][a[i][0]-'a']++;
		for(int j=a[i].size()-1;j>=0;j--)
		{
			int x=a[i][j]-'a';
			if(ch[u][x]==0)
				ch[u][x]=++cnt;
			u=ch[u][x];
			t[x]--;
			for(int k=0;k<26;k++)
			{
				if(t[k]==0)
					continue;
				ans+=dp[u][k];
			}
			if(j==1)
				dp[u][a[i][0]-'a']++;
		}
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 187660
N = int(input())
K = int(input())
X = list(map(int, input().split()))

sum_len = 0
for i in range(len(X)):
    if X[i] < abs(K-X[i]):
        sum_len += X[i] * 2
    else:
        sum_len += abs(K-X[i]) * 2

print(sum_len)

Measured memory_bytes: 3060
//Author: kaiyu
#include <iostream>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <set>
#include <unordered_map>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <numeric>
#include <iomanip>
using namespace std;
typedef long long ll;
#define SZ(x) ((int)(x).size())
#define all(x)  x.begin(),x.end()
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define tt ll t;cin >> t;while(t--)
#define int3(x,y,z) ll x,y,z;cin >> x >> y >> z;
#define int2(x,y) ll x,y;cin >> x >>y;
#define int1(x) ll x;cin>>x;
#define  fio ios::sync_with_stdio(0);cin.tie(NULL);
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
//bool cmp(pair<string,int>p1,pair<string,int>p2) {
//    return p1.ss > p2.ss;
//}
//if (s1.find(s2) != std::string::npos) {
//   std::cout << "found!" << '\n';
//}


using namespace std;

int main() {
    fio
    int2(n,k)
    ll newN = abs(n-k);
    ll diff = n - newN;
    if(diff < 0) { //for N < K
        cout << n << endl;
        return 0;
    }
    if(newN == 0) { // for N == k
        cout << 0 << endl;
        return 0;
    }
    if(n == 0) {
        cout << 0 << endl;
        return 0;
    }
    if(n%k == 0) {
        cout << 0 << endl;
    }
    else{
            if(abs((n%diff) - k) < abs(n%diff)) {
                cout << abs(k-(n%diff)) << endl;
                return 0;
            }
            else{
                cout << n%diff << endl;
            }

    }



}





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

int main(){
    int a, b;
    double c, s, l, h;
    cin>>a>>b>>c;
    double pi=acos(-1.0);
    c=c*pi/180.0;
    s=(a*b*sin(c))/2.0;
    l=a+b+sqrt(a*a+b*b-2.0*a*b*cos(c));
    h=2.0*s/a;
    cout<<fixed<<setprecision(4)<<s<<endl<<l<<endl<<h<<endl;
    return 0;
}



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

#define int long long int
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define endl "\n"

int32_t main()
{ 

	double n;
	cin>>n;
	double cnt=0;
	for(int i=1;i<=n;i++)
	{
		if(i%2!=0)
			cnt++;
	}

	double ans;
	ans=cnt/n;
	cout<<fixed<<setprecision(10)<<ans<<endl;
	

	return 0;
}

Measured memory_bytes: 256
import java.lang.Math

fun main(args: Array<String>)
{
    val (n, d) = readNInts()
    val x = Array<MutableList<Int>>(n, {mutableListOf<Int>()})
    for(i in 1..n) {
        readNInts().forEach{ x[i-1].add(it) }
    }

    var ans = 0
    for (i in 0..n-1) {
        for (k in i+1..n-1) {
            val diff = IntArray(d)
            for (m in 0..d-1) {
                diff[m] = x[i][m] - x[k][m]
            }
            val sq = DoubleArray(d)
            for (m in 0..d-1) {
                sq[m] = Math.pow(diff[m].toDouble(), 2.0)
            }

            var sum = 0.0
            for(m in 0..d-1) {
                sum += sq[m]
            }

            val dist = Math.sqrt(sum)

            ans += if ((dist - (dist.toInt() / 1).toDouble()) != 0.0) 0 else 1
        }
    }

    println(ans)
}


// Read an integer
// Usage: val a = readInt()
private fun readInt() = readLine()!!.toInt()

// Read N integers separated by " "
// Usage: val (a, b, c) = readNInts()
private fun readNInts() = readLine()!!.split(" ").map(String::toInt)

// Read a string
// Usage: val a = readString()
private fun readString() = readLine()!!


Measured memory_bytes: 37824
#include<stdio.h>
#define MAX 101
int main(){
  int i,j,k,n,a,b,A[MAX],B[MAX][MAX];

  scanf("%d",&n);
  for(i=1; i<=n; i++)
    scanf("%d%d",&A[i-1],&A[i]);
 
  for(i=1; i<=n; i++)
    B[i][i] = 0;
 
  for(j=2; j<=n; j++){

    for(i=1; i<=n-j+1; i++){
      a = i + j -1;
      B[i][a] = 1000000;

      for(k=i; k<=a-1; k++){
	b = B[i][k] + B[k+1][a] + A[i-1]*A[k]*A[a];
	if(B[i][a] >= b)
	  B[i][a] = b;
      }
    }
  }
 
  printf("%d\n",B[1][n]);
   
  return 0;
}



Measured memory_bytes: 2056
a = [2,3,4,5,6,7,8,9,10,11, 12,13, 1]

alice, bob = map(int, raw_input().split())

if a.index(alice) > a.index(bob):
	print "Alice"

elif a.index(alice) < a.index(bob):
	print "Bob"
else:
	print "Draw"

Measured memory_bytes: 2568
check[30], c, n, a;
int main() {
  n = 0;
  while (1) {
    c = getchar_unlocked();
    if ('0' <= c && c <= '9')
      n = n * 10 + c - '0';
    else
      break;
  }

  int xor_sum = 0;
  for (int i = 0; i < n; i++) {
    a = 0;
    while (1) {
      c = getchar_unlocked();
      if ('0' <= c && c <= '9')
        a = a * 10 + c - '0';
      else
        break;
    }
    xor_sum ^= a;
    a = a ^ (a - 1);

    check[__builtin_popcount(a) - 1] = 1;
  }

  int ans = 0;
  for (int bit = 29; bit >= 0; bit--) {
    if (((1 << bit) & xor_sum) == 0) {
      continue;
    }
    int x = (1 << (bit + 1)) - 1;

    if (check[bit]) {
      xor_sum ^= x;
      ans += 1;
    }
  }

  if (xor_sum != 0) {
    printf("-1\n");
  } else {
    printf("%d\n", ans);
  }
}

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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int h, w;
  cin >> h >> w;
  
  vector<int> x(26);
  for (int i = 0; i < h * w; i++) {
    char a;
    cin >> a;
    x.at(a - 'a')++;
  }
  
  if (h % 2 == 0 && w % 2 == 0) {
    for (int i = 0; i < 26; i++) {
      if (x.at(i) % 4 != 0) {
        cout << "No\n";
        return 0;
      }
    }
    cout << "Yes\n";
    return 0;
  }
  else if (h % 2 == 1 && w % 2 == 1) {
    bool flag = false;
    for (int i = 0; i < 26; i++) {
      if (x.at(i) % 2 == 1) {
        if (flag) {
          cout << "No\n";
          return 0;
        }
        else {
          x.at(i)--;
          flag = true;
        }
      }
    }
    int count4 = 0;
    for (int i = 0; i < 26; i++) {
      if (x.at(i) >= 4) {
        count4 += x.at(i) / 4;
        x.at(i) %= 4;
      }
    }
    int count2 = 0;
    for (int i = 0; i < 26; i++) {
      if (x.at(i) >= 2) {
        count2 += x.at(i) / 2;
        x.at(i) %= 2;
      }
    }
    if (count4 >= (h / 2) * (w / 2)) {
      count4 -= (h / 2) * (w / 2);
      if (count4 * 2 + count2 >= (h / 2) + (w / 2)) {
        cout << "Yes\n";
        return 0;
      }
      else {
        cout << "No\n";
        return 0;
      }
    }
    else {
      cout << "No\n";
      return 0;
    }
  }
  else {
    int count4 = 0;
    for (int i = 0; i < 26; i++) {
      if (x.at(i) >= 4) {
        count4 += x.at(i) / 4;
        x.at(i) %= 4;
      }
    }
    int count2 = 0;
    for (int i = 0; i < 26; i++) {
      if (x.at(i) >= 2) {
        count2 += x.at(i) / 2;
        x.at(i) %= 2;
      }
    }
    if (count4 >= (h / 2) * (w / 2)) {
      count4 -= (h / 2) * (w / 2);
      if (count4 * 2 + count2 >= (h / 2) * (w % 2) + (w / 2) * (h % 2)) {
        cout << "Yes\n";
        return 0;
      }
      else {
        cout << "No\n";
        return 0;
      }
    }
    else {
      cout << "No\n";
      return 0;
    }
  }
}

Measured memory_bytes: 256
N = int(input())
A = [int(i) for i in input().split()]

dic = {}
S = 0
dic[0] = 1

for i in range(N):
    S += A[i]
    if S in dic:
        dic[S] += 1
    else:
        dic[S] = 1

number = 0

for i in dic:
    N = dic[i]
    number += N * (N - 1) / 2

print(int(number))


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

using namespace std;

int main()
{
    int ans=-1;
    int a,b;
    cin >> a >> b;
    bool flg=true;
    for(int i=1;i<10001;i++){
        if(flg&&(i*8)/100==a&&i/10==b){
            ans=i;
            flg=false;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
N = int(input())
A = list(map(int,input().split()))
#アルゴリズム（動的計画法）で殴る解法
INF = float("inf")
dp = [[0,0] for _ in range(N+1)]
dp[0][1] = -INF
for i in range(N):
    dp[i+1][0] = max(dp[i][0]+A[i],dp[i][1]-A[i])
    dp[i+1][1] = max(dp[i][0]-A[i],dp[i][1]+A[i])
print(dp[N][0])

Measured memory_bytes: 25584
#include<bits/stdc++.h>
#define mins(a,b) a=min(a,b)
#define maxs(a,b) a=max(a,b)
 template < typename T > std::string to_string( const T& n )
  {
    std::ostringstream stm ;
    stm << n ;
    return stm.str() ;
  }
using namespace std;

const long long INF=9000000000000000;
int main(){
  long long a,b,c,d,n,x,y,ans=0;
  cin>>a>>b>>c>>d>>n;
  x=min(a*4,min(b*2,c));
  if(n==1)
    cout<<x<<endl;
  else{
    if(x*2<=d)
      cout<<x*n<<endl;
    else
      cout<<x*(n%2)+d*(n/2)<<endl;
  }
}

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

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


// std::vector Declaration
template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) {
   return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

// std::vector Initialization
template<typename T>
void fill_all(T& arr, const T& v) { arr = v; }
template<typename T, typename U>
void fill_all(T& arr, const U& v) { for (auto& i : arr) fill_all(i, v); }

// std::vector Debug
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
   os << "[";
   bool a = 1;
   for (auto e : v ) {
      os << (a ? "" : " "); 
      os << e;
      a = 0;
   }
   os << "]";
   return os;
}

// std::pair Debug
template<typename T, typename U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
   os << "(" << p.first << " " << p.second << ")";
   return os;
}

// std::set Debug
template<typename T>
ostream& operator<<(ostream& os, const set<T>& st) {
   os << "{";
   bool a = 1;
   for (auto e : st) {
      os << (a ? "" : " ");
      os << e;
      a = 0;
   }
   os << "}";
   return os;
}

// std::map Debug
template<typename T, typename U>
ostream& operator<<(ostream& os, const map<T, U>& mp) {
   os << "{";
   bool a = 1;
   for (auto e : mp) {
      os << (a ? "" : " ");
      os << e.first << ":" << e.second;
      a = 0;
   }
   os << "}";
   return os;
}

// std::tuple Debug
template<int N,class Tuple>
void out(ostream &os,const Tuple &t){}
template<int N,class Tuple,class H,class ...Ts>
void out(ostream &os,const Tuple &t){
   if(N)os<<" ";
   os<<get<N>(t);
   out<N+1,Tuple,Ts...>(os,t);
}
template<class ...Ts>
ostream& operator<<(ostream &os, const tuple<Ts...> &t){
   os<<"(";
   out<0,tuple<Ts...>,Ts...>(os,t);
   os<<")";
   return os;
}

// Debug
#define DUMP(x) cout<<#x<<" = "<<(x)<<endl

struct edge { int to, cost; };

const LL LINF = 1LL<<60;
const int IINF = 1<<30;
const LL MOD = 1e9+7;

int K, N;


void back(auto& v) {
   --v[v.size()-1];
   if (v[v.size()-1] == 0) {
      v.pop_back();
   } else {
      while (v.size() < N) {
         v.push_back(K);
      }
   }
}

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

   if (K % 2 == 0) {
      cout << K / 2;
      for (int i = 0; i < N-1; ++i) {
         cout << " " << K;
      }
      cout << endl;
      return 0;
   }

   vector<int> ans(N, K / 2 + 1);

   for (int i = 0; i < N/2; ++i) {
      back(ans);
   }

   for (int i = 0; i < ans.size(); ++i) {
      cout << ans[i] << (i == ans.size()-1 ? "\n" : " ");
   }

   return 0;
}


Measured memory_bytes: 3456
n = gets.to_i

minv = gets.to_i
maxv = -2000000000
(n-1).times do
  r = gets.to_i
  tmaxv = r - minv 
  maxv = tmaxv > maxv ? tmaxv : maxv
  minv = r < minv ? r : minv
end

puts maxv

Measured memory_bytes: 6092
#include <bits/stdc++.h>
using namespace std;
#define mem(a,n) memset(a,n,sizeof(a))
#define rep(i,a,n) for(int i=a;i<n;i++)
#define pb push_back
#define IO ios::sync_with_stdio(false)
#define fre freopen("in.txt","r",stdin)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
typedef long long ll;
const double PI=acos(-1.0);
const double eps=1e-8;
const int INF=0x3f3f3f3f;
const int MOD=1e8;
const int N=13;
const int dir[4][2]= {-1,0,1,0,0,-1,0,1};
vector<vector<int> >A;
int n;
int dfs(int i, int j)
{
    if (i == 2 || j == n)
        return 0;
    else if (i == 1 && j == n - 1)
        return A[i][j];
    else
        return max(dfs(i + 1, j), dfs(i, j + 1)) + A[i][j];
}
void init()
{
    int t;
    vector<int>X;
    while (cin >> n)
    {
        for (int i = 0; i < 2; i++)
        {
            for (int j = 0; j < n; j++)
            {
                cin >> t;
                X.push_back(t);
            }

            A.push_back(X);
            X.clear();
        }

        cout << dfs(0, 0) << endl;
        A.clear();
    }
}
int main()
{
    //fre;
    init();
    return 0;
}


Measured memory_bytes: 256
/*** author: yuji9511 ***/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using lpair = pair<ll, ll>;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i=(m);i<(n);i++)
#define rrep(i,m,n) for(ll i=(m);i>=(n);i--)
#define printa(x,n) for(ll i=0;i<n;i++){cout<<(x[i])<<" \n"[i==n-1];};
void print() {}
template <class H,class... T>
void print(H&& h, T&&... t){cout<<h<<" \n"[sizeof...(t)==0];print(forward<T>(t)...);}
ll dp[3010][3010] = {};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S,T;
    cin >> S >> T;
    ll ns = S.size(), nt = T.size();
    rep(i,0,ns){
        rep(j,0,nt){
            if(S[i] == T[j]){
                dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1);
            }else{
                dp[i+1][j+1] = max(dp[i+1][j+1], max(dp[i+1][j], dp[i][j+1]));
            }
        }
    }

    ll cs = ns, ct = nt;
    string ans = "";
    while(cs > 0 && ct > 0){
        if(dp[cs][ct] > dp[cs-1][ct] && dp[cs][ct] > dp[cs][ct-1]){
            ans += S[cs-1];
            cs--; ct--;
        }else{
            if(dp[cs][ct] == dp[cs-1][ct]){
                cs--;
            }else{
                ct--;
            }
        }
    }

    reverse(ans.begin(), ans.end());
    print(ans);
    

}

Measured memory_bytes: 70784
#!/usr/bin/env python3
# スペース区切りの整数の入力
n, p = map(int, input().split())

def PrimeFactorization(n):
    ret = []
    for i in range(2,int(n**0.5)+1):
        if n % i != 0:
            continue
        exp = 0
        while(n%i==0):
            exp += 1
            n //= i
        ret.append([i, exp])
    
    if n != 1:
        ret.append([n,1])
    
    return ret

a = PrimeFactorization(p)

ret = 1
for i in range(len(a)):
    for j in range(a[i][1]//n):
        ret *= a[i][0]

print(ret)


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

using namespace std;

int main(){
    int N,X;
    int m[110];
    cin>>N>>X;
    for(int i=0;i<N;i++)cin>>m[i];
    int sum=0;
    for(int i=0;i<N;i++)sum+=m[i];
    sort(m,m+N);
    int sub=X-sum;
    int min=m[0];
    int ans=N;
    while(sub>=min){
        sub-=min;
        ans++;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define P pair<int,int>
#define int long long
#define mod (int)(1e9+7)
#define inf (int)(3e18)
#define all(v) v.begin(),v.end()
#define prique(T) priority_queue<T,vector<T>,greater<T>>
using namespace std;

template<class T> inline void chmax(T &a, T b) {
	a = std::max(a, b);
}
template<class T> inline void chmin(T &a, T b) {
	a = std::min(a, b);
}

int mod_pow(int x, int y, int m = mod) {
	int res = 1;
	while (y) {
		if (y % 2) {
			res *= x;
			res %= m;
		}
		x = x * x % mod;
		y /= 2;
	}
	return res;
}

int N, X, D;
int A[200005];
int L[200005], R[200005];
signed main() {
	cin >> N >> X >> D;
	if (D < 0) {
		X = X + D * (N - 1);
		D *= -1;
	} else if (D == 0) {
		if (X == 0)
			cout << 1 << endl;
		else
			cout << N + 1 << endl;
		return 0;
	}
	rep(i,N)
	{
		A[i] += X + i * D;
		A[i + 1] += A[i];
	}

	map<int, vector<P>> mp;
	mp[0].push_back( { 0, 0 });
	rep(i,N)
	{
		L[i] = A[i];
		R[i] = A[N - 1] - (i != N - 1 ? A[N - 1 - i - 1] : 0);
		int sur = abs(X) * (i + 1) % D;
		mp[sur].push_back( { L[i], R[i] });
	}
	int ans = 0;

	for (auto i : mp) {
		sort(all(mp[i.first]));
		int mx = -inf;
		rep(j,mp[i.first].size())
		{
			if (mp[i.first][j].first > mx || !j) {
				ans += (mp[i.first][j].second - mp[i.first][j].first) / D + 1;
			} else if (mp[i.first][j].second > mx) {
				ans += (mp[i.first][j].second - mx) / D;
			}
			chmax(mx, mp[i.first][j].second);
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 26752
import java.util.*;
public class Main
{
  public static void main(String args[])
  {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int m = sc.nextInt();
    int a[] = new int[m];
    int s=0;
    int v=-1;
    for(int i=0;i<m;i++)
    {
        a[i]=sc.nextInt();
        s+=a[i];
    }
    if(n>s)
    v=n-s;
    else if(n==s)
    v=0;
    else
    v=-1;
    System.out.println(v);
    
  }
}


Measured memory_bytes: 46416
#include <bits/stdc++.h>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define REP(i,n) for(ll i=0;i<n;i++)
#define FOR(i,n1,n2) for(ll i=n1;i<n2;i++)
#define bFOR(i,n1,n2) for(ll i=n1;i>=n2;i--)
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

typedef long long int ll;
typedef pair<ll,ll> Pi;
typedef tuple<ll,ll,ll> Tu;
const int INF=(ll)(1LL<<30)-1;
const double INFd=100000000000.0;
const double PI=3.14151926535;
const ll INFl=(ll)9223372036854775807/2;
const int MAX=10000;
const ll tMOD=(ll)1e9+7;
const ll MOD=(ll)998244353;
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;}
int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};
int mdx[8]={0,1,0,-1,1,1,-1,-1},mdy[8]={-1,0,1,0,1,-1,1,-1};


template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}
int r;
int main(){
	cin>>r;
	cout<<r*r<<endl;
	return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;
public class Main{
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int a = s.nextInt();
		int b = s.nextInt();
		int c = s.nextInt();
		boolean poor = false;
		if (!(a==b & b==c)) {
			if (a==b || b==c || a==c) {
				poor = true;
			}
		}
		if (poor) {
			System.out.println("Yes");
		}else{
			System.out.println("No");
		}

	}
}

Measured memory_bytes: 23892
let () = Scanf.scanf "%d %d %d %d" @@ fun a b c x ->
  Printf.printf "%d\n" @@ List.length @@ List.filter (( = ) x) @@
    List.concat @@ Array.to_list @@ Array.init (a + 1) @@ fun i ->
      List.concat @@ Array.to_list @@ Array.init (b + 1) @@ fun j ->
        Array.to_list @@ Array.init (c + 1) @@ fun k -> 500 * i + 100 * j + 50 * k

Measured memory_bytes: 8576
import java.util.Scanner;

public class Main{

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

        int perTime = (100 * (n - m)) + (1900 * m);
        int times = (int) Math.pow(2, m);
        System.out.println(perTime * times);
    }
}


Measured memory_bytes: 23252
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvi vector<vector<int> >
#define vvl vector<vector<ll> >
#define vll vector<ll>
#define rep(c, a, b) for(ll c=a;c<b;c++)
#define re(c, b) for(ll c=0;c<b;c++)
#define all(obj) (obj).begin(), (obj).end()
typedef long long int ll;
typedef long double ld;
using namespace std;

int main(int argc, char const *argv[]) {
  ll a, b;std::cin >> a >> b;
  std::cout << (a+b)%24 << '\n';
}


Measured memory_bytes: 256
// https://atcoder.jp/contests/abc083/tasks/arc088_a

#include <iostream>
#include <vector>
#include <array>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <algorithm>
#include <iomanip>

using namespace std;

int main (int argc, char* argv[]) {
	long long left, right;
	cin >> left >> right;

	int result = 0;
	while (left <= right) {
		left *= 2;
		result++;
	}
	cout << result << endl;
}


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

bool is_prime(int n){
    for(int i=2;i * i <= n;i++){
        if(n % i == 0)return false;
    }
    return true;
}
int main()
{
    ll a; cin >> a;
    for(int i=a;i<=100003;i++){
        if(is_prime(i)){
            cout << i << endl;
            break;
        }
    }
}

Measured memory_bytes: 256
from collections import defaultdict
import math

INF = 10 ** 6 + 1
is_prime = [1] * INF

def eratorasu():
    is_prime[0] = 0
    is_prime[1] = 0
    for i in range(2, INF):
        if is_prime[i] == 0:
            continue
        for j in range(i * 2, INF, i):
            is_prime[j] = 0
    return

def f(n):
    yakusu = []
    if is_prime[n]:
        yakusu.append(n)
    else:
        for i in range(2, int(n ** 0.5) + 1):
            if n % i == 0:
                yakusu.append(i)
                if i != n //i:
                    yakusu.append(n // i)
                break

    for i in yakusu:
        if i != 1:
            d[i] += 1

eratorasu()
d = defaultdict(int)
N = int(input())
A = list(map(int, input().split()))

tmp = A[0]
for i in range(1, N):
    tmp = math.gcd(tmp, A[i])
    f(A[i])

if tmp != 1:
    print('not coprime')
    exit()
eratorasu()
f(A[0])

for i, v in d.items():
    if v != 1:
        print('setwise coprime')
        exit()

print('pairwise coprime')


Measured memory_bytes: 222632
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstdlib>
#include<queue>
#include<set>
#include<cstdio>

using namespace std;

#define ll long long
#define rep(i, n) for(int i = 0; i < n; i++)
#define P pair<int, int>

typedef vector<int> vec;
typedef vector<vec> mat;

const ll mod = 1000000007;

int main(){
    int a, b;
    cin >> a >> b;
    int ans = max(0, a - 2 * b);
    cout << ans << endl;
}

Measured memory_bytes: 3624
#include<iostream>
#include<algorithm>
#include<math.h>
#include<string>
#include<tuple>
#include<vector>
#include<cstdlib>
#include<cstdint>
#include<stdio.h>
#include<cmath>
#include<limits>
#include<iomanip> 
#include<ctime>
#include<climits>
#include<random>
#include<queue>

using namespace std;
void Solve();

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout<<setprecision(20)<<fixed;
  Solve();
}


/****************************************\
| Thank you for viewing my code:)        |
| Written by RedSpica a.k.a. RanseMirage |
| Twitter:@asakaakasaka                  | 
\****************************************/

void Solve(){
  std::random_device rnd;
  std::mt19937 mt(rnd());
  std::uniform_int_distribution<> rand100(0,10000);
  double n;
    cin>>n;
  double ans=0.0;
  double m=30000000;
  for(int i=0;i<m;i++){
    int x=rand100(mt);
    int y=rand100(mt);

    double d1=sqrt(x*x+y*y);
    
    if(d1<=10000){
      ans+=1.0;
    }
  }
  cout<<ans/m*8*n<<"\n";
}

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


int main() {
  vector<char> a(3);
  vector<char> b(3);
  rep(i,3) cin >> a[i];
  rep(i,3) cin >> b[i];
  bool ans = false;
  if(a[0] == b[2] && a[1] == b[1] && a[2] == b[0]) ans = true;
  if(ans) cout << "YES" << endl;
  else cout << "NO" << endl;
  return 0;
}

Measured memory_bytes: 256
//Rextester.Program.Main is the entry point for your code. Don't change it.
//Compiler version 4.0.30319.17929 for Microsoft (R) .NET Framework 4.5

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

namespace Rextester
{
    public class Program
    {
        public static void Main(string[] args)
        {
            //Your code goes here
          var input = Console.ReadLine().Split();
          var a = int.Parse(input[0]);
          var b = int.Parse(input[1]);
          var c = int.Parse(input[2]);
            
            if ( b - a == c - b) {
                Console.WriteLine("YES");
            } else 
                Console.WriteLine("NO");

            }
            
    }
}

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

using namespace std;

int main()
{
	long long n, k;
	cin >> n >> k;
	
	vector<long long> h(n);
	for(long long i = 0; i < n; i++)
		cin >> h[i];
	
	sort(h.begin(), h.end());
	
	if(k >= n) {
		cout << 0;
		return 0;
	}
	
	long long ans = 0;
	for(long long i = 0; i < n - k; i++)
		ans += h[i];
	
	cout << ans;
}

Measured memory_bytes: 1792
#include <iostream>
#include <queue>
#include <string>
#include <algorithm>
#include <cstring>
#include <map>
#include <set>
#include <vector>
#include <numeric>
#include <deque> 
using namespace std;
 
int main() {
  int N;
  cin >> N;
  //int A[100];
  //memset(A,0,sizeof(A));
  bool result = true;
  for(int i=0;i<N;i++){
    int tmp = 0;
    cin >> tmp;
    if(tmp % 2 == 0 ){
      if( tmp % 3==0 || tmp % 5==0){
      } else {
        result = false;
        break;
      }
    }
  }
  
  if(result){
    cout << "APPROVED" << endl;
  } else {
    cout << "DENIED" << endl;
  }
  
  return 0;
}
 

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

const int N=1e5+10;
int a[N],p[N];
ll sum[N],ans[N];

int main()
{
    int n;
    scanf("%d",&n);
    for (int i=1;i<=n;i++) {
        scanf("%d",&a[i]);
        p[i]=i;
    }
    sort(p+1,p+n+1,[&](const int &i,const int &j){ return a[i]>a[j] || a[i]==a[j] && i<j; });
    ll now=0;
    int pos=1;
    int i=p[pos];
    ll sum=0;
    while (i) {
        while (pos<=n && p[pos]>=i) {
            sum+=a[p[pos]];
            ++pos;
        }
        ll tmp=1LL*(pos-1)*a[p[pos]];
        ans[i]+=sum-tmp;
        sum=tmp;
        i=p[pos];
    }
    for (int i=1;i<=n;i++) {
        printf("%lld\n",ans[i]);
    }
    return 0;
}

Measured memory_bytes: 2688
#include <iostream>
using namespace std;
int main(){

int x, y;
cin >> x >> y;
while (!(x == 0 && y == 0)){
	if (x < y) cout << x << " " << y << endl;
	else cout << y << " " << x << endl;
	cin >> x >> y;
}
return 0;
}


Measured memory_bytes: 2988
#include <bits/stdc++.h>
#include <algorithm>
#define rep(i, n) for (int i=0; i<n; ++i)
#define all(obj) (obj).begin(),(obj).end()
using namespace std;
typedef long long ll;
long long GCD(long long x, long long y) { return y ? GCD(y, x%y) : x; }

int main(){
    int N;
    cin >> N;
    int ans = 0;
    for(int i=1; i<=N; ++i){
        int n = to_string(i).length();
        if(n%2) ans++;
    }
    cout << ans << endl;
    return 0;
}


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

int main()
{
	int n,k;
	cin>>n>>k;
	int arr[n];
	
	for(int i=0;i<n;i++)
	cin>>arr[i];
	
	int dp[n];
	dp[0]=0;
	dp[1]=abs(arr[1]-arr[0]);
	for(int i=2;i<n;i++)
	{
		dp[i]=INT_MAX;
		for(int j=1;j<=k;j++)
		{
			if(i>=j)
			dp[i]=min(dp[i],abs(arr[i]-arr[i-j])+dp[i-j]);
		}
	}
	cout<<dp[n-1]<<"\n";
}

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

cnt=0
for _ in range(10**5):
    if a%2==1 or b%2==1 or c%2==1:
        print(cnt)
        exit()
    a,b,c=b//2+c//2,c//2+a//2,a//2+b//2
    cnt+=1
print(-1)


Measured memory_bytes: 9176
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <cstdlib>
#include <cstdio>
#include <iterator>
#include <functional>
#include <bitset>
#include <iterator>
typedef long long ll;
typedef long double ld;
using namespace std;
typedef pair<int,int> pii;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const int MAXN = 2e5+50;
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define f first
#define s second
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)
#define rep0(i,l,r) for(int i=l;i<r;++i
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
int lcm(int a, int b) { return a * (b / gcd(a, b)); }

void solve(){
 
    string str;
    cin>>str;
    for(int i=0;i<str.length();++i)
        str[i]='x';
    for(int i=0;i<str.length();++i)
       cout<<str[i];
   cout<<endl;  
}
int main(){
 
   ios::sync_with_stdio(false);
  cin.tie(0);
     solve();
}

Measured memory_bytes: 3656
#include <bits/stdc++.h>
#define ll long long int
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
template <class T1, class T2>void print(T1 a[], T2 n) { for (T2 i = 0; i < n; i++) { cout << a[i] << " ";} cout << endl;}
template <class T1, class T2>void print(vector<T1> a, T2 n) { for (T2 i = 0; i < n; i++) { cout << a[i] << " "; } cout << endl;}
ll modexpo(ll a, ll b, ll m) {if (b == 0) {return 1;} else if (a == 1) {return 1;} if (b % 2 == 0) {ll t = modexpo(a, b / 2, m); t = (t * t) % m; return t;} else {ll t = modexpo(a, b / 2, m); t = (t * t) % m; t = (t * a) % m; return t;}}



int main() {

	// taskkill /IM "cp.exe" /F
	fast
      /*
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
*/


	int n, k;
	cin >> n >> k;
	int a[n];
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	if (n == 1) {
		cout << 0;
		return 0;
	}
	int dp[n];

	dp[n - 1] = 0;

	for (int i = n - 2; i >= 0; i--) {
		dp[i] = INT_MAX;
		for (int j = i + 1; j < n && (j - i) <= k ; j++) {
			dp[i] = min(dp[i], dp[j] + abs(a[j] - a[i]));
		}
	}
	cout << dp[0];
}

Measured memory_bytes: 1024
#include <cstdio>

constexpr long long mod = 1000000007;
long long count[60];

int main()
{
  long long n;
  scanf("%lld", &n);
  for (long long i = 0; i < n; ++i)
  {
    long long a;
    scanf("%lld", &a);
    for (long long j = 0; j < 60; ++j)
    {
      if (a & (1LL << j))
      {
        count[j]++;
      }
    }
  }

  long long ans = 0;
  for (long long i = 0; i < 60; ++i)
  {
    ans = (ans + (1LL << i) % mod * count[i] % mod * (n - count[i]) % mod) % mod;
  }
  printf("%lld\n", ans);
  return 0;
}

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

using ld=long double;
const ld EPS=1e-9;
struct Vec{
    ld x,y,z;
};
Vec operator+(const Vec lhs,const Vec rhs){
    return Vec{lhs.x+rhs.x,lhs.y+rhs.y,lhs.z+rhs.z};
}
Vec operator-(const Vec lhs,const Vec rhs){
    return Vec{lhs.x-rhs.x,lhs.y-rhs.y,lhs.z-rhs.z};
}
bool operator==(const Vec lhs,const Vec rhs){
    return lhs.x==rhs.x && lhs.y==rhs.y && lhs.z==rhs.z;
}
Vec operator*(ld lhs,const Vec rhs){
    return Vec{lhs*rhs.x,lhs*rhs.y,lhs*rhs.z};
}

namespace std{
    ld myabs(Vec v){
        return sqrt(v.x*v.x+v.y*v.y+v.z*v.z);
    }
}

void solve(int n){
    vector<Vec> p(n),v(n);
    vector<ld> r(n),vr(n);
    for(int i=0;i<n;i++){
        cin>>p[i].x>>p[i].y>>p[i].z;
        cin>>v[i].x>>v[i].y>>v[i].z;
        cin>>r[i]>>vr[i];
    }

    priority_queue<pair<ld,pair<int,int>>,vector<pair<ld,pair<int,int>>>,greater<>> que;
    for(int i=0;i<n;i++){
        que.push(make_pair(r[i]/vr[i],make_pair(i,i)));
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<i;j++){
            Vec rv=v[j]-v[i];
            if(myabs(rv)<EPS) continue;
            ld lb=0;
            ld ub=min(r[i]/vr[i],r[j]/vr[j]);
            for(int k=0;k<100;k++){
                ld mid0=(lb*2+ub)/3;
                ld mid1=(lb+ub*2)/3;
                ld dist0=myabs(p[j]+mid0*rv-p[i]);
                ld dist1=myabs(p[j]+mid1*rv-p[i]);
                if(dist0<dist1){
                    ub=mid1;
                }
                else{
                    lb=mid0;
                }
            }
            lb=0;
            for(int k=0;k<100;k++){
                ld mid0=(lb*2+ub)/3;
                ld mid1=(lb+ub*2)/3;
                ld dist0=myabs(p[j]+mid0*rv-p[i])-(r[i]-vr[i]*mid0)-(r[j]-vr[j]*mid0);
                ld dist1=myabs(p[j]+mid1*rv-p[i])-(r[i]-vr[i]*mid1)-(r[j]-vr[j]*mid1);
                if(dist0<dist1){
                    ub=mid1;
                }
                else{
                    lb=mid0;
                }
            }
            lb=0;
            for(int k=0;k<=100;k++){
                ld mid=(lb+ub)/2;
                ld dist=myabs(p[j]+mid*rv-p[i])-(r[i]-vr[i]*mid)-(r[j]-vr[j]*mid);
                if(dist>0){
                    lb=mid;
                }
                else{
                    ub=mid;
                }
                if(k==100 && abs(dist)<EPS){
                    que.push(make_pair(lb,make_pair(i,j)));
                }
            }
            
        }
    }
    vector<ld> res(n,-1);
    
    while(!que.empty()){
        auto tmp=que.top(); que.pop();
        ld t=tmp.first;
        int idx0=tmp.second.first,idx1=tmp.second.second;
        if(res[idx0]==-1 && res[idx1]==-1){
            res[idx0]=t;
            res[idx1]=t;
        }
    }
    cout<<fixed<<setprecision(10);
    for(int i=0;i<n;i++){
        cout<<res[i]<<endl;
    }

    return;
}
int main(){
    int n;
    while(cin>>n,n){
        solve(n);
    }
    return 0;
}


Measured memory_bytes: 3308
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys  # {{{
import os
import time
import re
from pydoc import help
import string
import math
from operator import itemgetter
from collections import Counter
from collections import deque
from collections import defaultdict as dd
import fractions
from heapq import heappop, heappush, heapify
import array
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy as dcopy
import itertools
# }}}

# pre-defined{{{
sys.setrecursionlimit(10**7)
INF = 10**20
GOSA = 1.0 / 10**10
MOD = 10**9+7
ALPHABETS = [chr(i) for i in range(ord('a'), ord('z')+1)]  # can also use string module
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def DP(N, M, first): return [[first] * M for n in range(N)]
def DP3(N, M, L, first): return [[[first] * L for n in range(M)] for _ in range(N)]
from inspect import currentframe
# }}}

def solve():
    s = input()
    if s == "ABC":
        print("ARC")
    else:
        print("ABC")

    return 0

if __name__ == "__main__":# {{{
    solve()

# vim: set foldmethod=marker: }}}


Measured memory_bytes: 75220
N, M, X, Y = map(int, input().split())
x = list(map(int, input().split()))
y = list(map(int, input().split()))
 
flag = 0
 
l = list(range(max(x)+1, min(y)+1))
 
for i in l:
  if X < i and i <= Y:
    flag = 1
    
if max(x) >= min(y):
  print('War')
elif flag == 0:
  print('War')
else:
  print('No War')

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) (int)((x).size())
#define debug(x) cout << #x << ":" << x << ' ';
#define debugg(x) cout << #x << ":" << x << ' ' << "\n";
#define endl "\n"
#define L(X) ((X)<<1)
#define R(X) (((X)<<1)|1)
#define M(X,Y) (((X)+(Y))>>1)

using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int MAXN = 1e5 + 5;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const long long int LLINF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-9;
const double PI = acos(-1);

template<typename T>   T max_self(T& a, T b) { if (a < b) a = b; return a; }
template<typename T>   T min_self(T& a, T b) { if (a > b) a = b; return a; }
template<typename T>   T add(T x, T y) { return ((x % MOD)  + (y % MOD)) % MOD;}
template<typename T>   T mul(T x, T y) { return ((x % MOD) * (long long)(y % MOD)) % MOD;}
template<typename T>   T sub(T x, T y) { return add(x, -y + MOD);}
template<typename T>   T gcd(T a, T b) { return b ? gcd(b, a % b) : a;}
template<typename T>   T lcm(T a, T b) { return a / gcd(a, b) * b;}
template<typename T>   vector<T> read(vector<T>& v, int n) {v.resize(n); for (auto &x : v)cin >> x;}
template<typename T>   void trav(vector<T> &v) {for (int i = 0 ; i < (int)v.size() ; ++i) {cout << v[i]; if (i != (int)v.size() - 1) cout << ' ';}}
int lg2(long long x)   {   return 64 - __builtin_clzll(x) - 1;	}
int lg2(int x)   {   return 32 - __builtin_clzll(x) - 1;	}

struct pair_hash{
	template<class T1, class T2>
	size_t operator() (const pair<T1, T2> &p) const {
		auto h1 = hash<T1>{}(p.first);
		auto h2 = hash<T2>{}(p.second);
		return h1 ^ h2;
	}
};

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

	ll a, b, k;
	cin >> a >> b >> k;

	cout << max(0LL, a - k) << ' ' << max(0LL, (a < k ? b - k + a : b)) << 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 < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)

#define MOD 1000000007

ll dp[10000000][4];

int main() {
    ll n;
    cin >> n;
    dp[0][0] = 1;
    rep(i, n) {
        dp[i + 1][0] = dp[i][0] * 8;
        dp[i + 1][1] = dp[i][0] + dp[i][1] * 9;
        dp[i + 1][2] = dp[i][0] + dp[i][2] * 9;
        dp[i + 1][3] = dp[i][1] + dp[i][2] + dp[i][3] * 10;
        rep(j, 4) {
            dp[i + 1][j] %= MOD;
        }
    }
    cout << dp[n][3] << endl;
    return 0;
}


Measured memory_bytes: 34696
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define RI(a) scanf("%d",&a)
#define RII(a,b) scanf("%d%d",&a,&b)
#define RIII(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#define ALL(a) a.begin(),a.end()
#define F first
#define S second
#define REP(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#ifdef leowang
#define debug(...) do{\
	fprintf(stderr,"%s - %d : (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
	_DO(__VA_ARGS__);\
}while(0)
template<typename I> void _DO(I&&x){cerr<<x<<endl;}
template<typename I,typename...T> void _DO(I&&x,T&&...tail){cerr<<x<<", ";_DO(tail...);}
#else
#define debug(...)
#endif
//}}}
const ll maxn=100005;
const ll maxlg=__lg(maxn)+2;
const ll INF64=8000000000000000000LL;
const int INF=2000000000;

int x;
int k;
int r[maxn];
int a[maxn];

int upper[maxn],lower[maxn];

int main()
{
	cin>>x>>k;
	REP(i,k) scanf("%d",r+i);
	int up=x,low=0;
	int pu=x,pl=0;
	int curt=0;
	for(int i=0;i<k;i++){
		if(i%2){
			pu+=r[i]-curt;pl+=r[i]-curt;
			if(pu>x){
				up=up-(pu-x);
				up=max(up,low);
				pu=x;
			}
		}
		else{
			pu-=r[i]-curt;pl-=r[i]-curt;
			if(pl<0){
				low=low-pl;
				low=min(low,up);
				pl=0;
			}
		}
		upper[i]=up;lower[i]=low;
		curt=r[i];
	}
	int std=low;
	int place=std;
	curt=0;
	for(int i=0;i<k;i++){
		if(i%2==0){
			place-=r[i]-curt;
			place=max(place,0);
		}
		else{
			place+=r[i]-curt;
			place=min(place,x);
		}
		curt=r[i];
		a[i]=place;
	}
	/*debug(std);
	REP(i,k) printf("%d%c",a[i]," \n"[i==k-1]);
	REP(i,k) printf("%d%c",upper[i]," \n"[i==k-1]);
	REP(i,k) printf("%d%c",lower[i]," \n"[i==k-1]);*/
	
	int q;
	cin>>q;
	REP(i,q){
		int t;int s;
		scanf("%d%d",&t,&s);
		
		if(t<=r[0]){
			printf("%d\n",max(0,s-t));
			continue;
		}
		
		int lf=0,ri=k;
		while(lf!=ri-1){
			int mid=(lf+ri)/2;
			if(r[mid]<=t) lf=mid;
			else ri=mid;
		}
		debug(lf);
		s=max(s,lower[lf]);s=min(s,upper[lf]);
		int tmp=a[lf]+s-std+(1-lf%2*2)*(t-r[lf]);
		printf("%d\n",max(min(tmp,x),0));
	}
	
	return 0;
}


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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF INT_MAX/3

ll n;
ll f[111][11];
ll p[111][12];

int main(){
	cin>>n;
  rep(i,n)rep(j,10)cin>>f[i][j];
  rep(i,n)rep(j,11)cin>>p[i][j];
  ll res=-1e16;
  rep(S,1<<10){
    if(S==0)continue;
    ll score=0;
    rep(i,n){
      int cnt=0;
      rep(j,10){
        if((S>>j)&1){
          if(f[i][j])cnt++;
        }
      }
      score+=p[i][cnt];
    }
    maxch(res,score);
  }
  cout<<res<<endl;
	return 0;
}


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

class Myon
{
    public Myon() { }
    public static int Main()
    {
        new Myon().calc();
        return 0;
    }

    Scanner cin;
    Func cin2;
    void calc()
    {
        cin = new Scanner();
        cin2 = new Func();
        int[] A=cin.ArrayInt(3,0);
        Array.Sort(A);
        Console.WriteLine(A[2]-A[0]);
        
    }
}



class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner()
    {
        s = new string[0];
        i = 0;
    }

    public string next()
    {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return next();
        i = 0;
        return s[i++];
    }

    public int nextInt()
    {
        return int.Parse(next());
    }
    public int[] ArrayInt(int N, int add = 0)
    {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextInt() + add;
        }
        return Array;
    }

    public long nextLong()
    {
        return long.Parse(next());
    }

    public long[] ArrayLong(int N, long add = 0)
    {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextLong() + add;
        }
        return Array;
    }

    public double nextDouble()
    {
        return double.Parse(next());
    }


    public double[] ArrayDouble(int N, double add = 0)
    {
        double[] Array = new double[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextDouble() + add;
        }
        return Array;
    }
}

class Answer
{
    public static void Int2DArrayAns(int[,]x,char c)
    {
        for(int i=0;i<x.GetLength(0);i++)
        {
            for(int j=0;j<x.GetLength(1)-1;j++)
            {
                Console.Write(x[i,j]);
                Console.Write(c);
            }
            Console.WriteLine(x[i,x.GetLength(1)-1]);
        }
    }//Answer.IntArrayAns(x);
    public static void Char2DArrayAns(char[,]x,char c)
    {
        for(int i=0;i<x.GetLength(0);i++)
        {
            for(int j=0;j<x.GetLength(1)-1;j++)
            {
                Console.Write(x[i,j]);
                Console.Write(c);
            }
            Console.WriteLine(x[i,x.GetLength(1)-1]);
        }
    }
}

class Func
{
    public long GCDLong(long a, long b)
    {
        while(a!=0)
        {
          long t=a;
          a=b%a;
          b= t;
        }
      
        return b;        
    }
}



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

int main(){
    long long h,count,tmp;
    cin >> h;
    count = 0;
    tmp = h;
    while(tmp>0){
        tmp/=2;
        count++;
    }
    long long ans = pow(2,count)-1;
    printf("%lld\n",ans);
    

}



Measured memory_bytes: 256