akhauriyash/Code-Regression huggingface dataset:
MOD = 1000000007

def pow(a, b):
    ret = 1
    while b > 0:
        if b%2 == 1:
            ret = ret*a%MOD
        a = a*a%MOD
        b //= 2
    return ret

def mul(s, e):
    ret = 1
    for i in range(s, e+1):
        ret = ret*i%MOD
    return ret

def fact(n):
    return mul(1, n)

def nCr(n, r):
    return mul(n-r+1, n) * pow(fact(r), MOD-2) % MOD

n, a, b = map(int, input().split())
ans = (pow(2, n) - 1 + MOD - nCr(n, a) + MOD - nCr(n, b)) % MOD
print(ans)


Measured memory_bytes: 3064
fun main() {
    val n = readLine()!!.toInt()
    val s = readLine()!!

    val x = s.toBigInteger(2)
    val bc = x.bitCount()
    val x1 = (x % (bc + 1).toBigInteger()).toInt()
    val x2 = if (bc > 1) (x % (bc - 1).toBigInteger()).toInt() else 0

    val ans = IntArray(n)
    var b1 = 1
    var b2 = 1

    for (i in (0 until n)) {
        b1 = if (i == 0) b1 else b1 * 2
        b1 %= bc + 1

        if (bc > 1) {
            b2 = if (i == 0) b2 else b2 * 2
            b2 %= bc - 1
        }

        val idx = n - i - 1
        if (s[idx] == '1' && bc <= 1) {
            ans[idx] = 0
            continue
        }

        var cnt = 1
        var xi = if (s[idx] == '1') {
            (x2 + (bc - 1) - b2) % (bc - 1)
        } else {
            (x1 + b1) % (bc + 1)
        }.toInt()

        while (xi > 0) {
            cnt++
            xi %= Integer.bitCount(xi)
        }

        ans[idx] = cnt
    }

    println(ans.joinToString("\n"))
}


Measured memory_bytes: 55588
#include <iostream>

using namespace std;

int main() {
    string s;
    cin>>s;
    int mx=0, cnt=0;
    int n=s.length();
    for(int i=0;i<n;i++)
    {
        if(s[i]=='R')
            cnt++;
        else
        {
            mx=max(mx,cnt);
            cnt=0;
        }
    }
    mx=max(cnt,mx);
    cout<<mx<<endl;
}

Measured memory_bytes: 3616
#include <bits/stdc++.h>
#define DUMP(x)  cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define IFOR(i, m, n) for(int i = n - 1; i >= m; i-- )
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define FOREACH(x,a) for(auto& (x) : (a) )
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
const ll INF = 1e18;
/* テンプレートここまで */

// int main() {
//   ll n; cin >> n;
//   vector<ll> a(n);
//   REP(i, n) cin >> a[i];
//   vector<int> b(n+1);
//   FOR(i, (n+1)/2, n+1) b[i] = a[i-1];

// }
typedef pair<ll,ll> P;

int main(){
  ll n; cin >> n;
  multiset<ll> st;
  REP(i, n) st.insert(-1);
  REP(i, n){
    ll a; cin >> a;
    auto lb = st.lower_bound(a);
    lb--;
    st.erase(lb);
    st.insert(a);
  }
  ll ans = 0;
  FOREACH(x,st){
    if(x!=-1) ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 4992
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <utility>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <set>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1<<30; 
const int MOD = 1e9 + 7;
struct edge
{
    int to, cost, use;
    bool operator<(const edge &e) const { return cost > e.cost; }
};
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m;
    while(cin >> n >> m, n | m)
    {
        vector<P> G[n + 1];
        for(int i = 0; i < m; i++)
        {
            int a, b, c; cin >> a >> b >> c;
            G[a].push_back(P(b, c));
            G[b].push_back(P(a, c));
        }
        for(int u = 1; u <= n; u++)
        {
            for(int v = 0; v < G[u].size(); v++)
            {
                P p = G[u][v];
                if(p.second == 0) continue;
                for(int w = 0; w < G[p.first].size(); w++)
                {
                    P q = G[p.first][w];
                    if(q.second == 0 || q.first == u) continue;
                    G[u].push_back(P(q.first, 0));
                    //cout << u << " " << q.first << endl;
                }
            }
        }
        priority_queue<edge> que;
        vector<vector<int>> cost(n + 1, vector<int>(2, INF));
        que.push({1, 0, 0});
        cost[1][0] = 0;
        while(que.size())
        {
            edge e = que.top(); que.pop();
            for(int u = 0; u < G[e.to].size(); u++)
            {
                P p = G[e.to][u];
                if(p.second == 0 && e.use) continue;
                if(p.second == 0)
                {
                    if(cost[e.to][e.use] < cost[p.first][1])
                    {
                        cost[p.first][1] = cost[e.to][e.use];
                        que.push({p.first, cost[p.first][1], 1});
                    }
                }
                else
                {
                    if(cost[e.to][e.use] + p.second < cost[p.first][e.use])
                    {
                        cost[p.first][e.use] = cost[e.to][e.use] + p.second;
                        que.push({p.first, cost[p.first][e.use], e.use});
                    }
                }
            }
        }
        //for(int i = 1; i <= n; i++) cout << cost[i][0] << " "; cout << endl;
        //for(int i = 1; i <= n; i++) cout << cost[i][1] << " "; cout << endl;
        int ans = min(cost[n][0], cost[n][1]);
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 3152
n = gets.chop.to_i
 
min = n
(1..(n/2+1)).each do |i|
  a = i.to_s
  b = (n - i).to_s
  sum = a.split('').map(&:to_i).inject(:+) + b.split('').map(&:to_i).inject(:+)
  min = [min, sum].min
end
p min

Measured memory_bytes: 2044
#include<bits/stdc++.h>
using namespace std ;
#define ll long long
#define pb push_back
#define __ ios_base::sync_with_stdio(false); cin.tie(NULL);

int main() {
 //   __


    ll n  ;
    cin >> n ;
    vector<ll>v(n) ;
 //   cin >> n ;
    ll sum = 0 ;
    ll i;
    for (i = 0;  i< n; i++) {
        cin >> v[i] ;
    }
    sort(v.rbegin(),v.rend()) ;
    sum = v[0] ;
    n-- , n-- ;
    i=1 ;
    while(n) {
        sum+= v[i] ;
        n-- ;
        if (n) sum+=v[i] ,n-- ;
        i++ ;
    }
    cout << sum << endl ;
    return 0 ;
}


Measured memory_bytes: 4848
#include <stdio.h>
#include <string.h>

int main(void){
	char str[1000];
	int sum,n=0,count,i;
	while(1){
		sum=0;
		scanf("%s",str);
		if(str[0]=='0') break;
		count=strlen(str);
		for(i=0;i<count;i++){
			n=str[i]-'0';
			sum+=n;
		}
		printf("%d\n",sum);
	}
	return 0;
}

Measured memory_bytes: 536
#include<bits/stdc++.h>
using namespace std;
#define debug 1

int main() {
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	long n;
	string s;
	cin>>n>>s;
	long l=s.length();
	for(long i=0;i<l;++i) {
		s[i]+=n;
		if(s[i]>'Z')
			s[i]-=26;
	}
	cout<<s<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <iomanip>

int main() {
  double x1, x2, y1, y2;
  std::cin >> x1 >> y1 >> x2 >> y2;
  std::cout << std::fixed;
  std::cout << std::setprecision(8) << std::sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)) << "\n";
}


Measured memory_bytes: 3220
import numpy as np
N,M,X= map(int,input().split())
a = []
d = 0
e = False
f = []
z = 0
for i in range(N):
    a.append([])

for i in range(N):
    a[i]= [int(i) for i in input().split()]

for i in range(2 ** N):
    b = np.array([0 for _ in range(M + 1)])
    d = True
    for j in range (N):

        if ((i >> j) & 1):
            b = np.array(a[j]) + b
    z = z + 1
    for k in range(M):
        if b[k + 1] < X:
            d = False
    if d:
        f.append(b[0].tolist())
        e = True
if e:
    print(min(f))
else:
    print("-1")

Measured memory_bytes: 27296
from collections import Counter,OrderedDict

N=int(input())
a=list(map(int,input().split()))
d=OrderedDict(Counter(a))
e=list(d)
e.sort()

if len(d)>3:
    ans="No"
else:
    ans="No"
    if len(d)==1:
        if e[0]==0:
            ans="Yes"
    elif len(d)==2:
        if N%3==0:
            if e[0]==0 and d[0]==N//3 and d[e[1]]==2*N//3:
                ans="Yes"
    else:
        if N%3==0:
            if d[e[0]]==d[e[1]]==d[e[2]]:
                if e[0]^e[1]^e[2]==0:
                    ans="Yes"
                   
print(ans)


Measured memory_bytes: 29860
#include<iostream>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<utility>
#include<vector>
#include<cmath>
#include<cstdio>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define it ::iterator
#define all(in) in.begin(),in.end()
const double PI=acos(-1);
const double ESP=1e-10;
using namespace std;
int main(){
  int n;
  cin>>n;
  vector<double>a(n);
  vector<double>b(n);
  rep(i,n)cin>>a[i];
  rep(i,n)cin>>b[i];
  vector<double>in(n);
  rep(i,n)in[i]=abs(a[i]-b[i]);
  double x=0,y=0,c=0,d=0;
  rep(i,n){
    x+=in[i];
    y+=in[i]*in[i];
    c+=in[i]*in[i]*in[i];
    if(d<in[i])d=in[i];
  }
  y=sqrt(y);
  c=pow(c,1.0/3.0);
  printf("%.10f\n%.10f\n%.10f\n%.10f\n",x,y,c,d);
}

Measured memory_bytes: 1288
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> dx = {{-1, 0, 1, 2, 1, 0}, {0, -1, -1, 0, 1, 1}};
vector<vector<int>> dy = {{0, -1, -1, 0, 1, 1}, {-1, 0, 1, 2, 1, 0}};
int main(){
  while (1){
    int n;
    cin >> n;
    if (n == 0){
      break;
    }
    vector<int> x(n), y(n);
    vector<char> d(n);
    for (int i = 0; i < n; i++){
      cin >> x[i] >> y[i] >> d[i];
    }
    map<int, map<int, int>> mp;
    for (int i = 0; i < n; i++){
      mp[x[i]][y[i]] = i;
      if (d[i] == 'x'){
        mp[x[i] + 1][y[i]] = i;
      }
      if (d[i] == 'y'){
        mp[x[i]][y[i] + 1] = i;
      }
    }
    vector<vector<int>> E(n * 2);
    for (int i = 0; i < n; i++){
      for (int j = 0; j < 6; j++){
        int x2 = x[i] + dx[d[i] - 'x'][j];
        int y2 = y[i] + dy[d[i] - 'x'][j];
        if (mp.count(x2)){
          if (mp[x2].count(y2)){
            int id = mp[x2][y2];
            if ((x[i] + y[i]) % 2 == (x[id] + y[id]) % 2){
              E[i * 2].push_back(id * 2 + 1);
              E[i * 2 + 1].push_back(id * 2);
            } else {
              E[i * 2].push_back(id * 2);
              E[i * 2 + 1].push_back(id * 2 + 1);
            }
          }
        }
      }
    }
    vector<int> c(n * 2, -1);
    int cnt = 0;
    for (int i = 0; i < n * 2; i++){
      if (c[i] == -1){
        c[i] = cnt;
        queue<int> Q;
        Q.push(i);
        while (!Q.empty()){
          int v = Q.front();
          Q.pop();
          for (int w : E[v]){
            if (c[w] == -1){
              c[w] = cnt;
              Q.push(w);
            }
          }
        }
        cnt++;
      }
    }
    bool ok = true;
    for (int i = 0; i < n; i++){
      if (c[i * 2] == c[i * 2 + 1]){
        ok = false;
      }
    }
    if (ok){
      cout << "Yes" << endl;
    } else {
      cout << "No" << endl;
    }
  }
}


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

int main() {
	
	int n;
	cin >> n;
	pair<int, int> arr[n];
	for (int i=0; i<n; i++) {
		cin >> arr[i].first;
		arr[i].second = i;
	}
	
	sort(arr, arr+n);
	
	int res[n];
	for (int i=0; i<n; i++) {
		
		if (i < (n/2)) {
			res[arr[i].second] = arr[n/2].first;
		}
		else {
			res[arr[i].second] = arr[n/2-1].first;
		}
		
	}
	
	for (int i=0; i<n; i++) cout << res[i] << endl;
	
}


Measured memory_bytes: 4480
using System;

public class Program
{
	public static void Main(string[] args)
	{
		var ss = new StreamScanner();
		//---------------------------------
		//????????????int, double, string?????????????????£????????????

			var r = ss.Next<int>();
			var c = ss.Next<int>();
			int[,] matrix = new int[r,c];

			for (int i = 0; i < r; i++)
			{
				for (int j = 0; j < c;j++)
				{
					var num = ss.Next<int>();
					matrix[i, j] = num;
				}
			}

			for (int i = 0; i < r; i++)
			{
				int sumOfr = 0;
				for (int j = 0; j < c; j++)
				{
					sumOfr += matrix[i, j];
					Console.Write(matrix[i, j]+" "); 
				}
				Console.WriteLine(sumOfr);
			}
			int numOfSum = 0;
			for (int i = 0; i < c;i++)
			{
				int sumOfc = 0;
				for (int j = 0; j < r;j++)
				{
					sumOfc += matrix[j, i];
					numOfSum += matrix[j, i];
				}
				Console.Write(sumOfc + " ");
			}
			Console.WriteLine(numOfSum);

			//int x = ss.Next<int>();
			//double d = ss.Next<double>();
			//string s = ss.Next<string>();

			//?????°???????????????????????¨?????????????????????????????????????????????????´???????
			//int[] array = ss.Next<int>(10);
			//---------------------------------

	}
}
public class StreamScanner
{
	private readonly char[] _c = { ' ' };
	private int _index = -1;
	private string[] _input = new string[0];
	private readonly System.IO.StreamReader _sr = new System.IO.StreamReader(Console.OpenStandardInput());

	public T Next<T>()
	{
		if (_index == _input.Length - 1)
		{
			_index = -1;
			while (true)
			{
				string rl = _sr.ReadLine();
				if (rl == null)
				{
					if (typeof(T).IsClass) return default(T);
					return (T)typeof(T).GetField("MinValue").GetValue(null);
				}
				if (rl != "")
				{
					_input = rl.Split(_c, StringSplitOptions.RemoveEmptyEntries);
					break;
				}
			}
		}
		return (T)Convert.ChangeType(_input[++_index], typeof(T), System.Globalization.CultureInfo.InvariantCulture);
	}

	public T[] Next<T>(int x)
	{
		var ret = new T[x];
		for (var i = 0; i < x; ++i) ret[i] = Next<T>();
		return ret;
	}

	public T[][] Next<T>(int x, int y)
	{
		var ret = new T[y][];
		for (var i = 0; i < y; ++i) ret[i] = Next<T>(x);
		return ret;
	}
}

Measured memory_bytes: 10092
#include<stdio.h>

main(){
  int data[20];
  int i,n,p,ans;
  int temp=1;

  data[0]=1;
  for(i=1;;i++){
    temp*=4;
    data[i]=temp;
    if(temp>=1500000){
      data[i]=-1;
      break;
    }
  }

 
  while(1){
    scanf("%d", &n);
    if(n==-1) break;
    if(n==0){
      printf("0\n");
      continue;
    }

    for(i=0;;i++){
      if(data[i]==-1) break;
      if(n<data[i]){
	p=i;
	break;
      }
    }
    for(i=p-1;i>=0;i--){
      ans=n/data[i];
      n = n-data[i]*ans;
      printf("%d", ans);
    }
    printf("\n");
  }
  return 0;
}

Measured memory_bytes: 0
#include <algorithm>
#include <iostream>
#include <map>

using namespace std;

int main()
{
    int N, M;
    long ans = 0;
    cin >> N >> M;

    std::map<long, int> ab;

    long a, b;
    for (int i = 0; i < N; i++) {
        cin >> a >> b;
        auto it = ab.find(a);
        if (it != ab.end()) {
            it->second += b;
        }
        else {
            ab[a] = b;
        }
    }

    for (auto it = ab.begin(); it != ab.end() && M > 0; it++) {
        long c = min(M, it->second);
        ans += c * it->first;
        M -= c;
    }

    cout << ans << endl;

    return 0;
}

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

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

  int l = -1, r = -1;
  for (int i = 0; i < s.length() - 1; i++) {
    if (s.at(i) == s.at(i + 1)) {
      l = i + 1;
      r = i + 2;
      break;
    }
  }

  for (int i = 0; i < s.length() - 2; i++) {
    if (s.at(i) == s.at(i + 2)) {
      l = i + 1;
      r = i + 3;
      break;
    }
  }

  cout << l << " " << r << endl;
}

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

int main() {
    int L;
    cin >> L;
    double x = L * L * L / 27.0;
    printf("%.12f\n", x);
    return 0;
}

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

using namespace std;

int main() {
  int N;
  cin >> N;
  vector<int> cnt(5);
  for (int i = 0; i < N; i++) {
    string s;
    cin >> s;
    if (s[0] == 'M') cnt[0]++;
    if (s[0] == 'A') cnt[1]++;
    if (s[0] == 'R') cnt[2]++;
    if (s[0] == 'C') cnt[3]++;
    if (s[0] == 'H') cnt[4]++;
  }
  long long ans;
  for (int bits = 0; bits < (1 << 5); bits++) {
    int c = 0;
    for (int i = 0; i < 5; i++) {
      if (bits & (1 << i)) c++;
    }
    if (c != 3) continue;
    long long a = 1;
    for (int i = 0; i < 5; i++) {
      if (bits & (1 << i)) {
        a *= cnt[i];
      }
    }
    ans += a;
  }
  cout << ans << endl;

  return 0;
}
/* vim:set fdm=marker: */


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#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++)
using namespace std;

signed main(){

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; cin >> n;
    int a = n;
    set<int> d;
    if (n % 2 == 0){
        d.insert(2);
        while(n % 2 == 0) n /= 2;
    }
    for (int i = 3; i * i <= n; i += 2){
        if (n % i == 0){
            d.insert(i);
            while(n % i == 0) n /= i;
        }
    }
    if (n != 1) d.insert(n);

    for (auto itr = d.begin(); itr != d.end(); itr++){
        a = a * (*itr - 1) / *itr;
    }
    cout << a << endl;
    return 0;
}


Measured memory_bytes: 3212
#include<iostream>
#include<cmath>
#include<stdio.h>
#include<string.h>

using namespace std;

int n;
int x[25], y[25], r[25], c[25];
int over[25];			// i?????????????????????????????£??????????????????bit??§??¨???
char dp[1<<24];			// i(bit???????????¨???)??¨????????¶????????§????????????????????????????????§???
// ?¶???????????????????bit????????????

bool overlap(int i, int j)
{
  return pow(x[i] - x[j], 2) + pow(y[i] - y[j], 2) < pow(r[i] + r[j], 2);
}


int main(void)
{
  while(cin >> n, n)
    {
      memset(over, 0, sizeof(over));
      for(int i = 0; i < n; i++)
	{
	  cin >> x[i] >> y[i] >> r[i] >> c[i];
	  for(int j = 0; j < i; j++)
	    {
	      if(overlap(i, j))
		over[i] |= (1 << j);
	    }
	}
      memset(dp, -1, sizeof(dp));
      dp[0] = 0;		// ????????????????????????????????¶?????§???0
      int ans = 0;
      for(int i = 0; i < (1<<n); i++) // 0~(1<<n)??§??¨??¶??????????????????(n == 4??????16??¶??????4??????????????????????????????????????????or??????????????????????????????2?????????????????¶???????????¨??????)
	{
	  if(dp[i] == -1)	// ??¶???i?????°????????????
	    continue;
	  ans = max(ans, (int)dp[i]);
	  for(int j = 0; j < n; j++)
	    {			// ?????§?????????j????¶????????????? or ??????j???????????????????????¨????????????
	      if((i & (1<<j)) != 0 || ((~i) & over[j]) != 0)
		continue;
	      for(int k = j + 1; k < n; k++)
		{		// ??????j??¨??????k??????????????? or ?????§?????????k????¶????????????? or ??????k???????????????????????¨????????????
		  if(c[j] != c[k] || (i & (1<<k)) != 0 || ((~i) & over[k]) != 0)
		    continue;
		  int next = i | (1<<j) | (1<<k); // next = ??????j??¨k????????????????????¶???
		  dp[next] = max((int)dp[next], dp[i] + 2);
		}
	    }
	}
      printf("%d\n", ans);
    }
  return 0;
}

Measured memory_bytes: 17536
package main

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

func main() {
	var n, k int
	fmt.Scan(&n, &k)
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	as := make([]int, n)
	for i := range as {
		sc.Scan()
		as[i], _ = strconv.Atoi(sc.Text())
	}
	l := 0
	r := int(1e9 + 1)
	for r-l > 1 {
		m := (l + r) / 2
		var cnt int
		for i := range as {
			c := int((as[i] + m - 1) / m)
			cnt += c - 1
		}
		if cnt <= k {
			r = m
		} else {
			l = m
		}
	}
	fmt.Println(r)
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}


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

int main(void) {
	int X,A,B,m;
	cin >> X >> A >>B;
	for(int i = 0;X-(A+B*i) >=0; i++) {
	m = X - (A+B*i);
	}
	cout << m << endl;
	
return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();
        int K=sc.nextInt();
        char[] S=sc.next().toCharArray();
        S[K-1]=(char)((int)S[K-1]+32);
        System.out.println(new String(S));
    }
}


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

using namespace std;

template <long long Mod> struct ModInt { /* {{{ */
  long long v;
  constexpr ModInt(const long long x = 0) {
    v = x % Mod;
    if (v < 0) {
      v += Mod;
    }
  }
  constexpr ModInt operator+(const ModInt rhs) const { return ModInt(*this) += rhs; }
  constexpr ModInt operator-(const ModInt rhs) const { return ModInt(*this) -= rhs; }
  constexpr ModInt operator*(const ModInt rhs) const { return ModInt(*this) *= rhs; }
  constexpr ModInt operator/(const ModInt rhs) const { return ModInt(*this) /= rhs; }
  const ModInt &operator+=(const ModInt rhs) {
    v += rhs.v;
    if (v >= Mod) {
      v -= Mod;
    }
    return *this;
  }
  constexpr ModInt &operator-=(const ModInt rhs) {
    if (v < rhs.v) {
      v += Mod;
    }
    v -= rhs.v;
    return *this;
  }
  constexpr ModInt &operator*=(const ModInt rhs) {
    v = v * rhs.v % Mod;
    return *this;
  }
  constexpr ModInt &operator/=(ModInt rhs) {
    long long exp = Mod - 2;
    while (exp) {
      if (exp & 1) {
        *this *= rhs;
      }
      rhs *= rhs;
      exp >>= 1;
    }
    return *this;
  }
  friend ostream &operator<<(ostream &s, ModInt<Mod> m) {
    s << m.v;
    return s;
  }
  friend istream &operator>>(istream &s, ModInt<Mod> m) {
    s >> m.v;
    return s;
  }
}; /* }}} */

const int mod = 1e9 + 7;
using modint = ModInt<mod>;

int main() {
  modint fact[100005];
  fact[0] = fact[1] = 1;
  for (int i = 2; i <= 100005; i++) {
    fact[i] = fact[i - 1] * i;
  }

  int N, M;
  cin >> N >> M;
  if (N > M) swap(N, M);
  modint ans;
  if (N == M) {
    ans = fact[N] * fact[M] * 2;
  } else if (N + 1 == M) {
    ans = fact[N] * fact[M];
  } else {
    ans = 0;
  }
  cout << ans << endl;

  return 0;
}
/* vim:set fdm=marker: */


Measured memory_bytes: 1024
// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;
using ll = long long int;
using int64 = long long int;
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const int INF = 1LL << 29;
const ll LONGINF = 1LL << 60;
const ll MOD = 1000000007LL;
 
int main() {
    int N; cin >> N;
    N %= 10;

    if(N == 2 or N == 4 or N == 5 or N == 7 or N == 9) {
        puts("hon");
    }
    if(N == 0 or N == 1 or N == 6 or N == 8) {
        puts("pon");
    }
    if(N == 3) {
        puts("bon");
    }
    return 0;
}


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

typedef long long ll;
using namespace std;

#define REP(i, n) for(ll i = 0; i < (ll)n; i++)
#define all(v) (v).begin(),(v).end()
#define UNIQUE(v) (v).erase( unique( all(v) ), (v).end() );
#define MOD 1000000007

int main(){
	ll h, w, m;	cin >> h >> w >> m;
	set<pair<int, int>> target;
	int sumH[h] = {0};
	int sumW[w] = {0};
	vector<int> cH;
	vector<int> cW;
	int mh, mw;
	REP(i, m){
		ll x, y;	cin >> x >> y;
		x--; y--;
		sumH[x]++;
		sumW[y]++;
		target.insert(make_pair(x, y));
	}

	mh = *max_element(sumH, sumH + h);
	mw = *max_element(sumW, sumW + w);
	REP(i, h){
		if( sumH[i] == mh )	cH.push_back(i);
	}
	REP(i, w){
		if( sumW[i] == mw )	cW.push_back(i);
	}

	REP(i, cH.size()) REP(j, cW.size()){
		if( target.find( make_pair(cH[i], cW[j]) ) == target.end() ){
			cout << mh + mw << endl;
			return 0;
		}
	}

	cout << mh + mw - 1 << endl;

	return 0;
}


Measured memory_bytes: 23852
//Δ_C
#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<bitset>
#include<cmath>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long LL;
typedef double DB;
const int N = 1e6+16;
char s[N];
int n,q,k,a[N];
void solve(){
	int i;
	LL x=0,y=0,z=0;
	for(i=1;i<=n;i=i+1){
		if(i>=k){
			if(s[i-k]=='D')
				x--,y-=a[i-1]-a[i-k];
		}
		if(s[i]=='D')
			x++;
		if(s[i]=='M')
			y+=x;
		if(s[i]=='C')
			z+=y;
	}
	cout<<z<<endl;
}
int main()
{
	int i;
	scanf("%d%s%d",&n,s+1,&q);
	for(i=1;i<=n;i=i+1)
		a[i]=a[i-1]+(s[i]=='M');
	while(q--){
		scanf("%d",&k);
		solve();
	}
	return 0;
}

Measured memory_bytes: 5120
#include<bits/stdc++.h>
#define mp make_pair
#define fr first
#define sd second
using namespace std;
typedef long long ll;
const int N = 1e3+1;

int n,a[N];

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	int pos=1;
	for(int i=1;i<=n;i++)
		if(abs(a[i])>abs(a[pos]))
			pos=i;
	printf("%d\n",2*n);
	if(a[pos]>=0)
	{
		printf("%d %d\n",pos,n);
		printf("%d %d\n",pos,n);
		for(int i=1;i<n;i++)
		{
			printf("%d %d\n",n,i);
			printf("%d %d\n",n,n);
		}
	}
	else
	{
		printf("%d %d\n",pos,1);
		printf("%d %d\n",pos,1);
		for(int i=n;i>1;i--)
		{
			printf("%d %d\n",1,i);
			printf("%d %d\n",1,1);
		}
	}
}


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

using namespace std;


int main()
{
	int n, m;
	char N[51][51], M[51][51];

	cin >> n >> m;

	for (int i = 0; i < n*n; i++) {
		cin >> N[i/n][i%n];
	}
	for (int i = 0; i < m*m; i++) {
		cin >> M[i/m][i%m];
	}

	int res = 0;
	for (int i = 0; i < n - m + 1; i++) {
		for (int j = 0; j < n - m + 1; j++) {
			int w = 1;
			for (int k = i; k < i+m; k++) {
				for (int l = j; l < j+m; l++) {
					if (N[k][l] != M[k-i][l-j]) {
						w = 0;
					}
				}
			}
			if (w == 1) {
				res = 1;
			}
		}
	}


	if (res == 1) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}

	return 0;
}



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

#define CK(N, A, B) (A <= N && N < B)
#define REP(i, a, b) for (int i = a; i < b; i++)
#define RREP(i, a, b) for (int i = (b - 1); a <= i; i--)
#define F first
#define S second
#define ll long long

const int INF = 1e9;
const long long LLINF = 1e18;

using namespace std;

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

/*==================================================*/

/*==================================================*/

int main() {
    int K, N;
    cin>>N>>K;
    int ans = 1;
    REP(i,0,N){
        if(ans * 2 >= ans + K){
            ans += K;
        }else{
            ans *= 2;
        }
    }
    cout<<ans<<endl;

    return 0;
}


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

#define LL long long

#define FOR(INDEX, START, END) for (int INDEX = (START); INDEX < (END); ++INDEX)
#define REP(INDEX, COUNT) for (int INDEX = 0; INDEX < (COUNT); ++INDEX)

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

	LL sum = 0;
	LL maxValue = 0;
	REP(i, N) {
		LL v;
		cin >> v;

		sum += v;
		maxValue = max(maxValue, v);
	}

	sum -= maxValue;

	if (maxValue >= sum) {
		cout << "No" << endl;
	}
	else {
		cout << "Yes" << endl;
	}


	return 0;
}


Measured memory_bytes: 256
from collections import deque
N, Q = map(int, input().split())
G = [[] for _ in range(N)]
counter = [0]*N
for _ in range(N-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
for _ in range(Q):
    p, x = map(int, input().split())
    counter[p-1] += x
# print(G)
# print(counter)
seen = [0]*N
todo = deque([0])
seen[0] = 1
while todo:
    v = todo.pop()
    cost = counter[v]
    for nv in G[v]:
        if seen[nv]:
            continue
        seen[nv] = 1
        counter[nv] += cost
        todo.append(nv)

print(*counter)

Measured memory_bytes: 56168
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#define MOD1 1000000007
#define MOD2 998244353
#define LIMIT1 200002
#define LIMIT2 500002
typedef long long ll;
typedef long double ld;
typedef const void cv;
#define rep(i,n) for((i)=0;(i)<(n);(i)++)
#define per(i,n) for((i)=(n)-1;(i)>=0;(i)--)
#define max(a,b) ((a)>(b) ? (a) : (b))
#define min(a,b) ((a)<(b) ? (a) : (b))
#define zt(a,b) (max((a),(b))-min((a),(b)))
#define absl(v) labs((v))
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll nPr(int n,int r){ll i,result=1;rep(i,r){result*=(ll)(n-i);}return result;}
ll nCr(int n,int r){ll i,result=1;if(n<r) return 0;rep(i,min(r,n-r)){result*=(ll)(n-i);result/=(ll)(i+1);}return result;}
#define nHr(n,r) nCr((int)((n)+(r)+1),(int)(r))
#define sankaku(x) (((x)*((x)+1))/2)
int dx[8]={1,0,-1,0,1,-1,-1,1},dy[8]={0,1,0,-1,1,1,-1,-1};
int upint(cv *a, cv *b) { return *(int *)a < *(int *)b ? -1 : *(int *)a > *(int *)b ? 1 : 0; }
int downint(cv *a, cv *b) { return *(int *)a < *(int *)b ? 1 : *(int *)a > *(int *)b ? -1 : 0; }
int upchar(cv *left, cv *right) {return strcmp((char *)left,(char *)right);}
int downchar(cv *left, cv *right) {return strcmp((char *)right,(char *)left);}
void tmpInit(int *c,ll m) {ll i;rep(i,m) c[i]=i;}
ll modpow(ll a, ll n, ll mod) {
    ll res = 1;
    while (n > 0) {
        if (n & 1){
            res *= a; if(mod>=1) res %= mod;
        }
        a *= a; if(mod>=1) a %= mod;
        n >>= 1;
    }
    return res;
}
void initialize(){
    
}
std::stack<int> sta;
std::vector<int> tree[LIMIT1];
int dist[LIMIT1][2]={0};
int u,v;
void dfs(int p,int count,int i){
  dist[p][i]=count;
  for(int q : tree[p]){
    if(dist[q][i]==-1) dfs(q,count+1,i);
  }
}
int main(void){
  initialize();
  ll n,m,i,j,k,result=0;
  int a[LIMIT2]={0},b[LIMIT1]={0};
  char s[LIMIT1];
  
  scanf("%lld %d %d",&n,&u,&v);
  u--;
  v--;
  rep(i,n-1){
    scanf("%d %d",&a[i],&b[i]);
    a[i]--;
    b[i]--;
    tree[a[i]].push_back(b[i]);
    tree[b[i]].push_back(a[i]);
  }
  rep(i,n) rep(j,2) dist[i][j]=-1;
  rep(i,2){
    dfs(((i==0) ? (u) : (v)),0,i);
  }
  rep(i,n){
    if(dist[i][0]<dist[i][1]){
      result = max(result,dist[i][1]);
    }
  }
  printf("%lld",result-1);
  
  return 0;
}



Measured memory_bytes: 15360
from itertools import combinations_with_replacement
N,M,Q = map(int,input().split())
A = []
for i in range(Q):
    b = list(map(int,input().split()))
    A.append(b)

T = range(1,M+1)
K = list(combinations_with_replacement(T,N))

ans = 0
for line in K:
    total = 0
    for combi in A:
        if line[combi[1]-1] - line[combi[0]-1] == combi[2]:
            total += combi[3]
    ans = max(total,ans)

print(ans)

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

#define rep(i,n) for(int i=0; i<(n); ++i)
#define rrep(i,n) for(int i=1; i<=(n); ++i)
#define drep(i,n) for(int i=(n)-1; i>=0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define v(T) vector<T>
#define imposs {cout<<"-1\n";return 0;}
#define LL_MAX LLONG_MAX
#define LL_MIN LLONG_MIN

typedef unsigned int uint;
typedef long long int ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int,int> pii;
typedef vector<pii> vpii;
typedef set<int> si;
typedef multiset<int> msi;
template<typename T>string join(const v(T)&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>inline ostream& operator<<(ostream&o,const v(T)&v)
{if(sz(v))o<<join(v);return o;}

ll cnt[19][19];

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

  int N;
  cin >> N;
  vi A(N);
  rep(i,N) {
    string s;
    cin >> s;
    int a = 0;
    int b = 0;
    if (s.find('.') != string::npos) {
      int p = (int)s.find('.');
      int l = (int)s.size() - p - 1;
      a -= l;
      b -= l;
      s.erase(p, 1);
    }
    ll n;
    sscanf(s.c_str(), "%lld", &n);
    while(n%2==0) {
      n /= 2;
      ++a;
    }
    while (n%5==0) {
      n /= 5;
      ++b;
    }
    cnt[min(18,a+9)][min(18,b+9)]++;
  }
  ll ans = 0;
  rep(i,19) rep(j,19) srep(ii,18-i,19) srep(jj,18-j,19) {
    ll ad = (i==ii && j==jj) ? cnt[i][j] * (cnt[i][j]-1)
            : cnt[i][j] * cnt[ii][jj];
    ans += ad;
  }
  ans /= 2;
  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 3924
#include<iostream>
#include<map>
#include<algorithm>
using namespace std;

int main(){
  
  int q, com, x;
  string key;
  map<string, int> M;
  
  cin >> q;
  for(int i = 0;i < q;i++){
    cin >> com;
    
    if(com == 0){
      cin >> key >> x;
      M[key] = x;
    }else if(com == 1){
      cin >> key;
      cout << M[key] << endl;
    }
  }
  
  return 0;
}


Measured memory_bytes: 27856
#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()
#define rall(x) (x).rbegin(), (x).rend()
#define itn long long

typedef long long ll;
typedef pair<ll,ll> p;


int main()
{
  ll a, b;
  cin >> a >> b;
  if (a + b == 15)
  {
    cout << "+" << endl;
  }else if (a * b == 15){
    cout << "*" << endl;
  }else{
    cout << "x" << endl;
  }
}

Measured memory_bytes: 256
#include <stdio.h>

int main()
{
	int A, B, Ans;

	scanf("%d%d", &A, &B);
	if(B%A!=0)
	{
	    Ans=B/A+1;
	}
	else
	{
	     Ans=B/A;
	}
	
	printf("%d\n", Ans);
	return 0;
}



Measured memory_bytes: 2100
#include<bits/stdc++.h>
#include <array>
using namespace std;
#define rep(i, n) for(int i = 0; i < (n); i++)
using ULL = unsigned long long;
using UL = unsigned;
using LL = long long;

void Solve() {
	UL N; cin >> N;
	UL u, v; cin >> u >> v; u--; v--;
	vector<UL> E[100000];
	rep(i, N - 1) {
		UL a, b; cin >> a >> b; a--; b--;
		E[a].push_back(b);
		E[b].push_back(a);
	}
	UL U[100000] = {}, V[100000] = {};
	queue<pair<UL, UL>> q;

	q.push({ u, 1 });
	while (q.size()) {
		auto p = q.front(); q.pop();
		if (U[p.first]) continue;
		U[p.first] = p.second;
		for (UL nx : E[p.first]) {
			q.push({ nx, p.second + 1 });
		}
	}
	q.push({ v, 1 });
	while (q.size()) {
		auto p = q.front(); q.pop();
		if (V[p.first]) continue;
		V[p.first] = p.second;
		for (UL nx : E[p.first]) {
			q.push({ nx, p.second + 1 });
		}
	}
	rep(i, N) { U[i]--; V[i]--; }

	UL ans = 0;
	rep(i, N) {
		if (V[i] > U[i]) {
			if ((V[i] - U[i]) % 2 == 0)
				ans = max(ans, V[i] - 1);
			else
				ans = max(ans, V[i] - 1);
		}
	}
	cout << ans << endl;
}
int main() { Solve(); return 0; }


Measured memory_bytes: 6784
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <tuple>
#include <cmath>
#include <cstdio>
#include <cassert>
#include <functional>
#define _LIBCPP_DEBUG 0
using namespace std;

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

int main(void){
    long long a,b;
    cin >> a >> b;
    long long gcd_num=gcd(a,b);
    cout << a*b/gcd_num << endl;

}


Measured memory_bytes: 3636
N, Q = map(int, input().split())
S = input()
query = [list(map(int,input().split())) for _ in range(Q)]

cum_sum = [0,0]
tmp = 0
for i in range(1,N):
    if S[i-1] == "A" and S[i] == "C":
        tmp += 1
    cum_sum.append(tmp)
# print(cum_sum)

for q in query:
    print(cum_sum[q[1]] - cum_sum[q[0]])

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

using namespace std;

int main() {

    int n, m;

    cin >> n >> m;

    int a[n];
    float x = float(1)/float((4*m));
    int total = 0;
    int count = 0;

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

    for (int i = 0; i < n; i++)
    {
        if (a[i] >= float(total) * x) count++;
    }

    if (count >= m)
    {
        cout << "Yes";
    } else
    {
        cout << "No";
    }
    

    
    


    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void){
    int a,b,c;
    
    scanf("%d %d %d",&a,&b,&c);
    if(a<=c && b<=c){
        printf("%d\n",a+b);
    }else if(b<=a && c<=a){
        printf("%d\n",b+c);
    }else{
        printf("%d\n",c+a);
    }
    
    return 0;
}

Measured memory_bytes: 128
import java.util.InputMismatchException;
import java.util.Scanner;

class Main {
    public static void main(String[] args) {
	Scanner scan = null;
	try {
		scan = new Scanner(System.in);
		int a = scan.nextInt();
		int b = scan.nextInt();
		int c = scan.nextInt();
		if ((a < b) && (b < c)) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
	} catch (InputMismatchException e) {
		System.out.println("??????????????????????????????");
	} finally {
		scan.close();
	}
    }
}

Measured memory_bytes: 17160
#include<bits/stdc++.h>
using namespace std;
#define MAX_N 100005
#define MAX_M 100005
 
int n,m,ans;
int x[MAX_M],y[MAX_M],w[MAX_M];
vector<int> G[MAX_N];
vector<int> g[MAX_N];
vector<int> group[MAX_N];
int id[MAX_N];
bool visited[MAX_N];
vector<int> vd;
int dp[MAX_N];
int d[MAX_N];
 
bool dfs(int pos,int prev,int root){
  id[pos]=root;
  visited[pos]=true;
  group[root].push_back(pos);
  for(int i=0;i<(int)G[pos].size();i++){
    int to=G[pos][i];
    if(to==prev)continue;
    if(i&&to==G[pos][i-1])return true;
    if(visited[to])return true;
    if(dfs(to,pos,root))return true;
  }
  return false;
}
 
bool check(){
  memset(visited,false,sizeof(visited));
  for(int i=0;i<n;i++)
    if(!visited[i]&&dfs(i,-1,i))return true;
 
  vector<int> deg(n);
  for(int pos=0;pos<n;pos++){
    for(int i=0;i<(int)g[pos].size();i++){
      int to=g[pos][i];
      deg[ id[to] ]++;
    }
  }
 
  queue<int> Q;
  for(int i=0;i<n;i++)
    if(deg[i]==0&&id[i]==i)
      Q.push(i);
   
  while(!Q.empty()){
    int root=Q.front();Q.pop();
    vd.push_back(root);
    for(int i=0;i<(int)group[root].size();i++){
      int pos=group[root][i];
      for(int j=0;j<(int)g[pos].size();j++){
        int to=g[pos][j];
        deg[ id[to] ]--;
        if(deg[ id[to] ]==0)Q.push(id[to]);
      }
    }
  }
  for(int i=0;i<n;i++)
    if(deg[i]>0)return true;
  return false;
}
 
int solve(int S){
  for(int i=0;i<(int)group[id[S]].size();i++){
    int pos=group[id[S]][i];
    d[pos]=-1;
  }
  queue<int> Q;
  Q.push(S);
  d[S]=0;
  while(!Q.empty()){
    int pos=Q.front();Q.pop();
    for(int i=0;i<(int)G[pos].size();i++){
      int to=G[pos][i];
      if(d[to]!=-1)continue;
      d[to]=d[pos]+1;
      Q.push(to);
    }
  }
  int res=S;
  for(int i=0;i<(int)group[id[S]].size();i++){
    int pos=group[id[S]][i];
    if(d[pos]+dp[pos]>d[res]+dp[res])res=pos;
    ans=max(ans,d[pos]+dp[S]);
    for(int i=0;i<(int)g[pos].size();i++){
      int to=g[pos][i];
      dp[to]=max(dp[to],d[pos]+dp[S]+1);
    }
  }
  return res;
}
 
int main(){
  scanf("%d %d",&n,&m);
  for(int i=0;i<m;i++){
    scanf("%d %d %d",&x[i],&y[i],&w[i]);
    x[i]--,y[i]--;
    if(w[i]==1){
      g[x[i]].push_back(y[i]);
    }
    if(w[i]==2){
      G[x[i]].push_back(y[i]);
      G[y[i]].push_back(x[i]);
    }
  }
  if(check()){
    printf("Infinite\n");
    return 0;
  }
  for(int i=0;i<(int)vd.size();i++){
    int root=vd[i];
    if(root==id[root])
      solve(solve(solve(root)));
  }
  printf("%d\n",ans);  
  return 0;
}

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

int prime(int x){
    int t = 1;
    for(int i = 2; i <= (int)sqrt(x); i++){
        if(x % i == 0){
            t = 0;
            break;
        }
    }
    if(x == 1){
        t = 0;
    }else if(x == 2){
        t = 1;
    }
    return t;
}

int main(void){

    int Q;

    scanf("%d", &Q);

    int c[100001];

    c[0] = 0, c[1] = 0;

    for(int i = 2; i <= 100000; i++){
        if(prime(i) == 1 && prime((i+1) / 2) == 1 && i % 2 == 1){
            c[i] = c[i-1] + 1;
        }else{
            c[i] = c[i-1];
        }
    }

    int l[Q], r[Q];

    for(int i = 0; i < Q; i++){
        scanf("%d%d", &l[i], &r[i]);
    }

    for(int i = 0; i < Q; i++){
        printf("%d\n", c[r[i]] - c[l[i]-1]);
    }

    return 0;
}

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

const double PI = acos(-1);
const double EPS = 1e-15;
using ll = long long;
using ull = unsigned long long;
const int inf = 2e9;
const ll INF = 2e18;
const ll MOD = 1e9+7;
const ll MOD1 = 998244353;
//typedef pair<int,int> P;

#define REP(i,n) for (int i = 0; i < (n); i++)
#define sz(s) (s).size()
#define pb push_back
#define fi first
#define se second
//#define mp make_pair

int pre;
int ans;
int a[100010];
int g1[100010];
int g2[100010];

int main(){
  /**入力**/
  int n;
  cin >> n;
  REP(i,n) {
    cin >> a[i];
  }
  g1[0] = a[0];
  for (int i = 1; i < n; i++) {
    g1[i] = __gcd(g1[i-1],a[i]);
  }
  g2[n-1] = a[n-1];
  for (int i = n-2; i >= 0; i--) {
    g2[i] = __gcd(g2[i+1],a[i]);
  }
  for (int i = 0; i < n; i++) {
    if (i == 0) ans = max(ans,g2[i+1]);
    else if (i == n - 1) ans = max(ans, g1[n-2]);
    else ans = max(ans, __gcd(g1[i-1],g2[i+1]));
  }
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 1408
#!/usr/bin/env python3
import sys
def input(): return sys.stdin.readline().rstrip()


def main():
    n=int(input())
    A=list(map(int, input().split()))
    counts=[0]*(10**6+5)
    for AA in A:
        counts[AA]+=1
    ans=0
    for i in range(1,10**6+5):
        if counts[i]>0:
            for j in range(i+i,10**6+5,i):
                counts[j]=-1
        if counts[i]==1:
            ans+=1
    print(ans)
        

        
    


if __name__ == '__main__':
    main()



Measured memory_bytes: 32244
n=int(input())
s=[]
for _ in range(n):
  s.append(input())
import collections
d=collections.Counter(s)
largest=max(list(d.values()))
ans=[]
for key in d.keys():
  if d[key]==largest:
    ans.append(key)
ans.sort()
for _ in range(len(ans)):
  print(ans[_])

    

Measured memory_bytes: 38856
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
inline long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }

vector<long long> enum_divisors(long long n) {
    vector<long long> res;
    for (long long i = 1LL; i * i <= n; i++) {
        if (n % i == 0) {
            res.emplace_back(i);
            if (i != n / i) res.emplace_back(n / i);
        }
    }
    sort(res.begin(), res.end());
    return res;
}

int main() {
    int n; cin >> n;
    vector<int> a(n);
    for (int &ai: a) cin >> ai;
    auto candy = enum_divisors(a[0]);
    auto tmp = enum_divisors(a[1]);
    candy.insert(candy.end(), tmp.begin(), tmp.end());
    long long ma = 0;
    for (auto x: candy) {
        int cnt = 0;
        for (auto ai: a) if (ai % x != 0) cnt++;
        if (cnt <= 1) ma = max(ma, x);
    }
    cout << ma << endl;
    return 0;
}

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

int main(){
    int n, l = 0, r = 0;
    scanf("%d", &n);
    deque<char> pt;
    char ch;
    rep(_, n){
        scanf(" %c", &ch);
        pt.push_back(ch);
        if(ch == '(') l++;
        else r++;
        if(r > l){
            pt.push_front('(');
            l++;
        }
    }
    if(l > r){
        rep(_, l - r) pt.push_back(')');
    }
    rep(i, pt.size()) printf("%c", pt[i]);
    printf("\n");
    return 0;
}

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

using namespace std;
#define pb push_back
#define mp make_pair

        long long mod=1000000007;
        long long dp[200010],prevv[200010],c[200010];

int main()
{
            int n;
            cin>>n;
            for(int i = 0;i<n;i++){
                cin >>c[i];
                c[i]--;
            }
            for( int i=0;i<=n;i++ ){
                prevv[i] = 0;
                dp[i]=0;
            }
            dp[0]=1;
            prevv[ c[0] ] = 1;
            for( int i  =1;i<n;i++ ){
                if( c[i] != c[i-1]  ) dp[i]= ( dp[i-1] + prevv[ c[i] ] )%mod;
                else dp[i] = dp[i-1];
           //     dp[i]%=mod;
                prevv[ c[i] ]= dp[i];
            }
                cout << dp[n-1]%mod <<endl;
                return 0;
}

/*
001
110
010
*/

/*
1001

0111
0100
0000
0011
*/













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

int main(){
  int N;
  cin >> N;
  int sum, dsun=0;
  for(int i=0;i<N;i++){
    int y;
    cin >> y;
    sum+=y;dsun+=y*y;
  }
  cout << (sum*sum-dsun)/2;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <deque>

using namespace std;

int main() {

	int n;
	cin >> n;

	deque<int> b;

	int temp;
	for (int i = 0; i < n; i++) {
		cin >> temp;
		if (i % 2 != 0) {
			b.push_front(temp);
		} else {
			b.push_back(temp);
		}
	}

	if (n % 2 == 0) {
		cout << b.front();
		b.pop_front();
		for (int i = 0; i < n - 1; i++) {
			cout << " " << b.front();
			b.pop_front();
		}
		cout << endl;
	} else {
		cout << b.back();
		b.pop_back();
		for (int i = 0; i < n - 1; i++) {
			cout << " " << b.back();
			b.pop_back();
		}
		cout << endl;
	}
	return 0;
}


Measured memory_bytes: 2944
#include<iostream>
#include<cctype>
#include<cstdio>
using namespace std;
int main(){
    char ch;
    while(1) {
        scanf("%c",&ch);
        if(isalpha(ch)){
            if(islower(ch)) printf("%c",toupper(ch));
            else printf("%c",tolower(ch));
        } else printf("%c",ch);
        if(ch == '\n')break;
    }
    
  
   
   
   
    return 0;
}

Measured memory_bytes: 1104
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
typedef long long ll;
typedef long l;
int return_max(int a,int b){
  if(a>b){
    return a;
  }else{
    return b;
  }
}

int return_min(int a,int b){
  if(a<b){
    return a;
  }else{
    return b;
  }
}

int main(void)
{
  int n;
  int a[150];
  scanf("%d",&n);
  for(int i=0;i<n;i++){
    scanf("%d",&a[i]);
  }
  int count=0;
  for(int i=0;i<n;i++){
    if((i+1)%2==1&&a[i]%2==1){
      count++;
    }
  }

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

  return 0;
}


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

using namespace std;

int main()
{
	int K, S;
	cin >> K >> S;

	int two_sum[3 * K + 1];
	memset(two_sum, 0, sizeof(two_sum));

	for (int i = 0; i <= K; i++)
		for (int j = 0; j <= K; j++)
			two_sum[i + j]++;

	int ans = 0;
	for (int k = 0; k <= K and k <= S; k++)
		ans += two_sum[S - k];

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(long long i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define REPS(i,n) FOR(i,1,n+1)
#define int long long
#define pb push_back
#define eb emplace_back
#define mp make_pair
const int MOD=1e9+7;
const int INF=1e15;

signed main(){
    int N;cin>>N;
    vector<int>A(N,0);
    REP(i,N)cin>>A[i];
    int a=A[N-1];
  	REP(i,N-1){
      	a=a^A[i];
    }
  	if(a==0)cout<<"Yes"<<endl;
  	else cout<<"No"<<endl;
}


Measured memory_bytes: 1024
import java.util.Scanner;


public class Main {

	
	public static void main(String[] args) {
		double debt = 100000;
		Scanner stdIn = new Scanner(System.in);
		int n = Integer.parseInt(stdIn.next());
		for (int i = 1; i <= n; i++) {
			debt += (debt * 0.05);
			int tmp = (int)(debt / 1000);
			if((debt/1000) != tmp) debt = ((tmp*1000) + 1000);
		}
		System.out.println((long)debt);
	}

}

Measured memory_bytes: 17288