akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define ll int64_t
#define _GLIBCXX_DEBUG
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
//約数列挙(√N)
vector< int64_t > divisor(int64_t n) {
  vector< int64_t > ret;
  for(int64_t i = 1; i * i <= n; i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  sort(begin(ret), end(ret));
  return (ret);
}
//素因数分解(√N)
map< int64_t, int > prime_factor(int64_t n) {
  map< int64_t, int > ret;
  for(int64_t i = 2; i * i <= n; i++) {
    while(n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if(n != 1) ret[n] = 1;
  return ret;
}
//素数テーブル(NloglogN)
vector< bool > prime_table(int n) {
  vector< bool > prime(n + 1, true);
  if(n >= 0) prime[0] = false;
  if(n >= 1) prime[1] = false;
  for(int i = 2; i * i <= n; i++) {
    if(!prime[i]) continue;
    for(int j = i + i; j <= n; j += i) {
      prime[j] = false;
    }
  }
  return prime;
}
//二項係数(K)
template< typename T >
T binomial(int64_t N, int64_t K) {
  if(K < 0 || N < K) return 0;
  T ret = 1;
  for(T i = 1; i <= K; ++i) {
    ret *= N--;
    ret /= i;
  }
  return ret;
}
//二項係数テーブル(N^2)
template< typename T >
vector< vector< T > > binomial_table(int N) {
  vector< vector< T > > mat(N + 1, vector< T >(N + 1));
  for(int i = 0; i <= N; i++) {
    for(int j = 0; j <= i; j++) {
      if(j == 0 || j == i) mat[i][j] = 1;
      else mat[i][j] = mat[i - 1][j - 1] + mat[i - 1][j];
    }
  }
  return mat;
}
//unionfind
struct UnionFind {
  vector< int > data;
 
  UnionFind(int sz) {
    data.assign(sz, -1);
  }
 
  bool unite(int x, int y) {
    x = find(x), y = find(y);
    if(x == y) return (false);
    if(data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    return (true);
  }
 
  int find(int k) {
    if(data[k] < 0) return (k);
    return (data[k] = find(data[k]));
  }
 
  int size(int k) {
    return (-data[find(k)]);
  }
};

//memo cout << fixed << setprecision(桁数);//
int main(){
  double n,m,d;
  cin >> n >> m >>d;
  double a;
  if(d!=0)a=(2*(n-d)/(n*n))*(m-1);
  else a=((n-d)/(n*n))*(m-1);
  cout << fixed << setprecision(10);
  cout <<a <<endl;
}

Measured memory_bytes: 3792
N = int(input())
A = list(map(int,input().split(" ")))

'''
M A M A ... A M
1 1 2 2     N 1

 M A M A M A M
 1 1 2 2 3 3 1
 x
 a1-x
 a2-(a1-x) = a2-a1+x
 a3-(a    ) = a3-a2+a1-x x


'''
sum_g = sum(A[1::2])
sum_k = sum(A[::2])

M0 = (sum_k - sum_g)//2
M = [0]* N 
M[0] = M0
for i in range(0,N-1):
    M[i+1] = A[i]-M[i]
    n_before = M[i+1]

text = ""

for m in M:
    text += "{} ".format(m*2)

print(text[:-1])


Measured memory_bytes: 15212
#include<stdio.h>

int main () {
    int a, b, c;
    
    scanf("%d", &a);
    scanf("%d", &b);
    scanf("%d", &c);

  if ( a < b && b < c ) {
    printf("Yes\n");
} else { 
    printf("No\n");
}
    return 0;
}


Measured memory_bytes: 2140
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int count = 0;

void merge(int a[], int left, int mid, int right) {
  int i, j, k;
  int n1 = mid - left;
  int n2 = right - mid;
  int l[mid - left + 1];
  int r[right - mid + 1];
  for (i = 0; i < n1; i++) {
    l[i] = a[left + i];
  }
  for (i = 0; i < n2; i++) {
    r[i] = a[mid + i];
  }

  l[n1] = (int)INFINITY;
  r[n2] = (int)INFINITY;
  i = 0;
  j = 0;
  for (k = left; k < right; k++) {
    count++;
    if (l[i] <= r[j]) {
      a[k] = l[i];
      i = i + 1;
    } else {
      a[k] = r[j];
      j = j + 1;
    }
  }
}

void mergeSort(int a[], int left, int right) {
  int mid;
  if (left + 1 < right) {
    mid = (left + right) / 2;
    mergeSort(a, left, mid);
    mergeSort(a, mid, right);
    merge(a, left, mid, right);
  }
}


int main(void) {
  int i, j, k, n, l;
  int a[1000000] = {0};
  scanf("%d", &l);
  for (i = 0; i < l; i++) {
    scanf("%d", &a[i]);
  }

  mergeSort(a, 0, l);

  for (k = 0; k < l; k++) {
    printf("%d", a[k]);
    if (k < l - 1) {
      printf(" ");
    }
  }
  printf("\n%d\n", count);


  return 0;
}



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

#define ll long long

int const N = 301;

double n;

double dp[N][N][N];
bool vis[N][N][N];

double pound(int ones, int twos, int threes)
{
	if (ones == 0 && twos == 0 && threes == 0)
		return 0;
	
	if (vis[ones][twos][threes])
		return dp[ones][twos][threes];
	
	vis[ones][twos][threes] = 1;
	
	double s = (ones + twos + threes);
	double sum = n / s;
	
	if (ones)
	    sum += pound(ones - 1, twos, threes) * (ones / s);
	
	if (twos)
	    sum += pound(ones + 1, twos - 1, threes) * (twos / s);
	
	if (threes)
		sum += pound(ones, twos + 1, threes - 1) * (threes / s);
	
	return dp[ones][twos][threes] = sum;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int m[3] = {};
	cout << setprecision(9) << fixed;
	
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        int k;
        cin >> k;
        
        ++m[k - 1];
    }
    
    cout << pound(m[0], m[1], m[2]);;
    
    return 0;
}

Measured memory_bytes: 239872
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <algorithm>
#include <numeric>
#include <utility>
#include <random>
#include <chrono>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>

using namespace std;

using LL = long long;
using ULL = unsigned long long;
using PII = pair<int, int>;
using PIL = pair<int, LL>;
using PLL = pair<LL, LL>;
// const int mod = 1e9 + 7;
// const int mod = 998244353;

inline void quickread() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

int a[2000];
int n, x, y;

inline void work() {
    cin >> n >> x >> y;
    for (int i = 1; i < n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            int dist = min(j - i, abs(i - x) + abs(j - y) + 1);
            ++a[dist];
        }
    }
    for (int i = 1; i < n; ++i) {
        cout << a[i] << "\n";
    }
}

int main() {
    // freopen("input.txt", "r", stdin);
    quickread();
    work();
    return 0;
}

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

int main(){
  int n;
  int a;
  int max;
  int min;
  long long sum;
  cin >> n;
  for(int i=0; i<n; i++){
    cin >> a;
    if(i == 0){
      max = a;
      min = a;
      sum = a;
    } else{
      if(max < a)max = a;
      if(min > a)min = a;
      sum += a;
    }
  }
  cout << min << " "<< max << " " << sum << endl;
  return 0;
}

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

int main() {
   string s, t; cin >> s >> t;
   vector<string> ans;
   int l = s.size()-t.size()+1; //移動できる範囲

   for(int i = 0; i < max(0, l); i++) {
       string tmp = s;
       for (int j = 0; j < t.length(); j++) {
           if(i+j>s.size()-1) break; //インデックスをはみ出したら中止
           if(tmp[i+j]=='?' || tmp[i+j]==t[j]) tmp[i+j] = t[j]; //s[i+j]=='?' と s[i+j] == t[j] は t[j]にする 
           else break; // それ以外はダメ
           if(j==t.length()-1) {
               for(int k = 0; k < tmp.length(); k++) {
                   if(tmp[k] == '?') tmp[k] = 'a';//余ったs[i+j]=='?'を'a'にする
               }
               ans.push_back(tmp);
           }
       }
   }
   sort(ans.begin(), ans.end());
   cout << (ans.size() > 0 ? ans[0] : "UNRESTORABLE" ) << endl;
   return 0;
}

/*

テストケース１
?????
z

正解：aaaaz　（間違い：zaaaa）
*/

Measured memory_bytes: 3576
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define F first
#define S second

using namespace std;
typedef pair<int,int> P;
typedef vector<int> ivec;

const int MOD=998244353;
int INF=100100100100100;

int b[2010];
int dp[2010][4020];
int cb[3010];

int add(int a,int b){
  return (a+b)%MOD;
}
int prod(int a,int b){
  return (a*b)%MOD;
}

int beki(int a,int b)
{
	if(b==0)return 1;
	int x=beki(a,b/2);
	if(b%2==0)return (x*x)%MOD;
	else return (((a*x)%MOD)*x)%MOD;
}

int inv(int a)
{
	return beki(a,MOD-2);
}

void combi(int a,int b)
{
	int ret=1;
    cb[0]=1;
	for(int i=1;i<=b;i++)
	{
		ret=(((ret*(a+1-i))%MOD)*inv(i))%MOD;
      cb[i]=ret;
	}
	//return ret;
}



signed main(){
  string s;cin>>s;
  int n=s.length();
  rep(i,n){
    int ppp=s[i]-'0';
    if(i==0)b[0]=ppp;
    else b[i]=b[i-1]+ppp;
  }
  dp[0][0]=1;
  rep(i,n){
    rep(j,2*n){
      if(b[i]>j)(dp[i+1][j+1]+=dp[i][j])%=MOD;
      if(j+i+2>b[i])(dp[i+1][j]+=dp[i][j])%=MOD;
    }
  }
  int ans=0;
  combi(n+1,n+1);
  rep(i,b[n-1]+1){
    (ans+=prod(dp[n-1][i],cb[b[n-1]-i]))%=MOD;
  }
  cout<<ans<<endl;
  return 0;
}


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

int N;
int A[210];      

int main() {
    cin >> N;
    int sisuu;
    sisuu = log2(N);
    int beki = sisuu;
    int result = pow(2, beki);
    cout << result << endl;
}



Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll, ll> Pll;
#define rep(i,n) for(int (i) = 0; (i) < (int)(n); (i)++)
#define debug(var)  do{std::cout << #var << " : ";view(var);}while(0)
template<typename T> void view(T e){std::cout << e << std::endl;}
template<typename T> void view(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void view(const std::vector<std::vector<T> >& vv){ for(const auto& v : vv){ view(v); } }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
void Yes(){cout << "Yes" << endl;}
void No(){cout << "No" << endl;}
void YES(){cout << "YES" << endl;}
void NO(){cout << "NO" << endl;}
void err() {cout << -1 << endl;}
#define all(x) (x.begin(), x.end())

const int MOD = 1000000007;
const int INF = 1e9;

#define PI acos(-1);
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int ddx[8] = {1,1,1,-1,-1,-1,0,0};
int ddy[8] = {0,1,-1,0,1,-1,1,-1};


int main(){
    int a, b;
    cin >> a >> b;
    cout << max({a+b, a-b, a*b}) << endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>*/
 
#define pll              pair <long long,long long>
#define pb               push_back
#define ll               long long
#define ff               first
#define ss               second
#define D(x)             cerr<<#x " = "<<(x)<<endl
#define vll              vector <ll>
#define IOS              ios_base::sync_with_stdio(0); cin.tie(NULL);
#define endl             '\n'   
using namespace std;
int main()
{
    IOS
 	// freopen("input.txt","r",stdin);
 	// freopen("output.txt","w",stdout);
 	// freopen("error.txt","w",stderr);
 	ll n,a,b;
 	cin>>n>>a>>b;
 	ll wh=n/(a+b);
 	n%=(a+b);
 	cout<<wh*a+min(a,n)<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=505,INF=1e9;
int M[MAXN][MAXN];
int H,W,h,w;
int main()
{
	scanf("%d %d %d %d",&H,&W,&h,&w);
	if(H%h==0&&W%w==0)
	{
		printf("No\n");
		return 0;
	}
	printf("Yes\n");
	int k=(INF-1)/(h*w-1),f=0;
	f=k*(h*w-1)+1;
	f=-f;
	for(int i=1;i<=H;i++)
	{
		for(int j=1;j<=W;j++)
		{
			if(i%h==0&&j%w==0)
				printf("%d ",f);
			else
				printf("%d ",k);
		}
		printf("\n");
	}
}

Measured memory_bytes: 2816
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ln '\n';
int lim=1e6;
int inf=1e9+7;
ll solve(int k,vector<vector<ll> > &dp,int i,int n,int W,ll* v,int* w){
	if(k==W or i==n){
		return 0;
	}else if(dp[k][i]!=-1){
		return dp[k][i];
	}else{
		ll t1=solve(k,dp,i+1,n,W,v,w);
		ll ans=t1;
		if(w[i]+k<=W){
			ll t2=solve(k+w[i],dp,i+1,n,W,v,w);
			t2+=v[i];
			ans=max(ans,t2);
		}
		dp[k][i]=ans;
		return ans;
	}
}
int main()
{	
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n;cin>>n;
	int W;cin>>W;
	int w[n];ll v[n];
	for(int i=0;i<n;i++){
		cin>>w[i]>>v[i];
	}	
	vector<vector<ll> >dp(W,vector<ll>(n,-1));

	cout<<solve(0,dp,0,n,W,v,w)<<ln;
}

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

using namespace std;

#define REP1(i,n) for(int i=1, i##_len=(n); i<i##_len; ++i)
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define pow(x) x*x
#define ll long long
static const ll MAX = 1000000;
static const ll INFTY = 1e12;
static const ll MOD = 1000000007;

template < typename T > inline string toString( const T &a ) { ostringstream oss; oss << a; return oss.str(); };

struct edge {
    ll to, cost;
};

using Graph = vector<vector<int>>;
using _Graph = vector<vector<edge>>;


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

// 深さ優先探索
vector<bool> seen;
vector<int> colors;

int H, W, N;
int sx, sy, gx, gy; 
vector<vector<char>> field;
vector<vector<int>> dist;
//vector<pair<int, int>> gx, gy;
deque<pair<int, int>> que;

typedef vector<vector<int> > Matrix;

const int INF = 100000000;


int main() {

  ll N;
  cin >> N;
  vector<ll> S(N);
  string s;
  map<string, int> hin;

  REP(i, N){
    cin >> s;
    hin[s]++;
  }
  ll ans = 0;
  REP(i, hin.size()){
    ans++;
  }

  cout << ans << endl;



  
}


/*
                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
         pass System Test!
*/


Measured memory_bytes: 20336
import java.util.Scanner;

public class Main{

	static Scanner s = new Scanner(System.in);

	public static void main(String __[]){
		input();
		solve();
	}

	static int h, w, n, k, f[][];

	private static void input(){
		h = s.nextInt();
		w = s.nextInt();
		n = s.nextInt();
		k = s.nextInt();
		f = new int[h][w];
	}

	private static void solve(){
		int count=n;
		loop:
		for(int i = 0; i < h; i++){
			for(int j = 0; j < w; j++){
				if(i==h-1&&j==w-1) {
					f[i][j]=count;
					break loop;
				}

				f[i][j] = question(i, j, i, j);
				count-=f[i][j];
				if(count==0) break loop;
			}
		}

		long pow = 1, result = 0;
		for(int i = 0; i < h; i++){
			for(int j = 0; j < w; j++){
				result += f[i][j] * pow;
				result %= k;
				pow *= 2;
				pow %= k;
			}
		}

		answer(result);
	}

	private static final int question(int x1, int y1, int x2, int y2){
		System.out.printf("? %d %d %d %d\n", x1, y1, x2, y2);
		return s.nextInt();
	}

	private static final void answer(long a){
		System.out.printf("! %d\n", a);
	}
}


Measured memory_bytes: 38116
n = int(input())
line = list(map(int,input().split()))
print(*line)
for i in range(1,n):
    v = line[i]
    j = i-1
    while j>=0 and line[j]>v:
        line[j+1] = line[j]
        j -= 1
    line[j+1] = v
    print(*line)

Measured memory_bytes: 7980
#include <iostream>
#define N 100000
using namespace std;
int Search(int);
int Check(int);
int n,k,w[N];
int main(){
  int r,sum=0,i;
  cin >> n >> k;
  for(i=0;i<n;i++) cin >> w[i],sum+=w[i];
  r=Search(sum);
  cout << r << endl;
  return 0;
}
int Search(int right){
  int r,left=0,mid,flag=0;
  while(1){
    mid=(left+right)/2;
    r=Check(mid);
    if(r==0) left=mid;
    else if(r==1) right=mid; 
    if(left+1==right) break;
  }
  return right;
}
int Check(int m){
  int sum=0,cnt=0,i,j;
  for(i=0;i<n;i++){
    j=i;
    while(1){
      if(j <= n-1 && w[j]>m) return 0;
      if(j<=n-1&&sum+w[j]<=m){
	sum+=w[j];
	j++;
      }else break;
    }
    sum=0;
    i=j-1;
    cnt++;
  }
  if(cnt<=k) return 1;
  return 0;
}

Measured memory_bytes: 1548
//Relive your past life.
//Face your demons.
//The past is never dead,it is not even past.
//The memories are not only the key to the past but...also to the future.
//coded in Rusty Lake
#include<cmath>
#include<math.h>
#include<ctype.h>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<complex>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cwchar>
#include<cwctype>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#define ll   long long
#define pb   push_back
#define mp   make_pair
#define orz  1000000007
using namespace std;
int n,m;
ll ans;
int tt[200005],he[100005],nx[200005],_;
int b[100005],c[100005],X,Y,a[100005],f[100005],q[100005],Q;
void add(int x,int y){nx[++_]=he[x],he[x]=_,tt[_]=y;}
int dfs(int x,int y,int z){
    int s=z;
    for(int i=he[x];i;i=nx[i])if(tt[i]!=y)s+=dfs(tt[i],x,-z);
    ans+=abs(s);
    return s;
}
void ope(int x,int y){
    c[x]=-c[y],f[x]=y;
    for(int i=he[x];i;i=nx[i]){
        if(tt[i]!=y){
            if(c[tt[i]])Y=x,X=tt[i];
            else ope(tt[i],x);
        }
    }
}
void sol(int x){
    c[x]=1;
    for(int i=he[x];i;i=nx[i])if(!c[tt[i]])sol(tt[i]),a[x]+=a[tt[i]];
    ans+=abs(a[x]);
}
void sol2(int x){
    c[x]=1;
    for(int i=he[x];i;i=nx[i])if(!c[tt[i]])sol2(tt[i]),a[x]+=a[tt[i]];
    if(!b[x])ans+=abs(a[x]);
    else q[++Q]=a[x];
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y),add(y,x);
    }
    if(m==n-1){
        if(dfs(1,0,1))puts("-1");   
        else printf("%d\n",ans);
        return 0;
    }
    c[0]=-1;
    ope(1,0);
    if(c[X]==c[Y]){
        if(n&1){
            puts("-1");
            return 0;
        }
        int cnt=0;
        for(int i=1;i<=n;++i)a[i]=c[i],cnt+=a[i];
        a[X]-=cnt/2,a[Y]-=cnt/2;
        memset(c,0,sizeof(c));
        sol(1);
        printf("%lld\n",ans+abs(cnt/2));
        return 0;
    }
    for(int i=X;i!=Y;i=f[i])b[i]=1;
    for(int i=1;i<=n;++i)a[i]=c[i];
    memset(c,0,sizeof(c));
    sol2(1);
    if(a[1]){
        puts("-1");
        return 0;
    }
    q[++Q]=0;
    sort(q+1,q+Q+1);
    int x=q[(Q+1)/2];
    for(int i=1;i<=Q;++i)ans+=abs(q[i]-x);
    printf("%lld\n",ans);
    //system("pause");
    return 0;
}


Measured memory_bytes: 7296
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <bitset>
#include <utility>
#include <numeric>
#include <queue>
#include <stack>

using ll = long long;
using namespace std;

constexpr int MOD = 1e9 + 7;
constexpr ll MOD_LL = ll(1e9) + 7;

template<typename T>
map<T, T> prime_factor(T n) {
	map<T, T> res;
	
	for(T i = 2; i * i <= n; ++i) {
		while( n % i == 0 ) {
			res[i]++;
			n /= i;
		}
	}
	
	if( n != 1 ) res[n] = 1;
	
	return res;
}

int main(void) {
	ll n, p;
	cin >> n >> p;
	
	auto prf = prime_factor(p);
	
	ll ans = 1LL;
	for(auto x : prf) {
		if( x.second >= n ) {
			ans *= (ll)pow(x.first, x.second / n);
		}
	}
	
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> using vt = vector<T>;
template<class T> using vvt = vector<vt<T>>;
template<class T> using ttt = tuple<T,T>;
using tii = tuple<int,int>;
using vi = vector<int>;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define pb push_back
#define mt make_tuple
#define ALL(a) (a).begin(),(a).end()
#define FST first
#define SEC second
#define DEB cerr<<"!"<<endl
#define SHOW(a,b) cerr<<(a)<<" "<<(b)<<endl
#define DIV int(1e9+7)
const int INF = (INT_MAX/2);
const ll LLINF = (LLONG_MAX/2);
const double eps = 1e-8;
//const double PI = M_PI;  
inline ll pow(ll x,ll n,ll m){ll r=1;while(n>0){if((n&1)==1)r=r*x%m;x=x*x%m;n>>=1;}return r%m;}
inline ll lcm(ll d1, ll d2){return d1 / __gcd(d1, d2) * d2;}
 
/* Coding space */
template<class T>
struct BIT{
    vector<T> d;
    BIT(size_t n):d(n+1){}
    T sum(size_t i){T s{};for(++i;i>0;i-=i&-i)s+=d[i];return s;}
    T sum(size_t i,size_t j){return i?sum(j)-sum(i-1):sum(j);}
    void add(size_t i,T x){for(++i;i<d.size();i+=i&-i)d[i]+=x;}
};
int main(){
  int n; cin >> n;
  vi data(n+4);
  data[0] = 0;
  data[1] = 0;
  rep(i,n) cin >> data[i+2];
  data[n+2] = 0;
  data[n+3] = 0;
  BIT<int> cost(n+3);
  rep(i,n+3) cost.add(i,abs(data[i+1] - data[i]) ),cerr << cost.sum(i,i) << endl;
  rep(i,n){
      //cerr << cost.sum(0,i)  << " " << cost.sum(i+3,n+2) << " "<< abs(data[i+1] - data[i+3]) << endl;
      cout << cost.sum(0,i) + cost.sum(i+3,n+2) + abs(data[i+1] - data[i+3]) << endl;
  }
}


Measured memory_bytes: 2048
#include <stdio.h>
int main(void){
    // Your code here!
    int h1,m1;
    int h2,m2;
    int k;
    int tmp;
    
    scanf("%d%d%d%d%d",&h1,&m1,&h2,&m2,&k);
    
    tmp = h2*60+m2 - (h1*60+m1) - k;
    printf("%d\n",tmp);
    
    return 0;
}

Measured memory_bytes: 1732
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(1000000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in sys.stdin.readline().split()]


def gcd(n, m):
    if n % m == 0:
        return m
    else:
        return gcd(m, n % m)


def gcd_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = gcd(v, L[i])

    return v


def lcm(n, m):
    return (n * m) // gcd(n, m)


def lcm_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = lcm(v, L[i])

    return v

def comb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def bisearch(L, target):
    low = 0
    high = len(L) - 1
    
    while low <= high:
        mid = (low + high) // 2
        guess = L[mid]
        if guess == target:
            return True
        elif guess < target:
            low = mid + 1
        elif guess > target:
            high = mid - 1
    if guess != target:
        return False

# --------------------------------------------

dp = None


def main():
    A, B = list(map(int, input().split()))
    print(lcm(A, B))


main()


Measured memory_bytes: 5492
#include <stdio.h>
#include <set>

using namespace std;

int H, W;
char board[2005][2005];

int l_near[2005][2005];
int r_near[2005][2005];
int u_near[2005][2005];
int d_near[2005][2005];

int main()
{
	int ans = 0;

	scanf("%d %d", &H, &W);

	for (int i = 1; i <= H; ++i)
	{
		int current_l_near = 0;

		for (int j = 1; j <= W; ++j)
		{
			scanf(" %c", &board[i][j]);
			if (board[i][j] == '#') current_l_near = j;
			else l_near[i][j] = current_l_near;
		}
	}

	for (int i = 1; i <= H; ++i)
	{
		int current_r_near = W + 1;

		for (int j = W; j >= 1; --j)
		{
			if (board[i][j] == '#') current_r_near = j;
			else r_near[i][j] = current_r_near;
		}
	}

	for (int i = 1; i <= W; ++i)
	{
		int current_u_near = 0;

		for (int j = 1; j <= H; ++j)
		{
			if (board[j][i] == '#') current_u_near = j;
			else u_near[j][i] = current_u_near;
		}
	}

	for (int i = 1; i <= W; ++i)
	{
		int current_d_near = H + 1;

		for (int j = H; j >= 1; --j)
		{
			if (board[j][i] == '#') current_d_near = j;
			else d_near[j][i] = current_d_near;
		}
	}

	for (int i = 1; i <= H; ++i)
	{
		for (int j = 1; j <= W; ++j)
		{
			if (r_near[i][j] - l_near[i][j] + d_near[i][j] - u_near[i][j] - 3 > ans) ans = r_near[i][j] - l_near[i][j] + d_near[i][j] - u_near[i][j] - 3;
		}
	}

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

	return 0;
}

Measured memory_bytes: 66944
// In The Name Of Allah
#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e10;
typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pii;
const ll mod = 1e9 + 7;
 
 
void faster()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
 
const ll M = 500 + 10;
const ll N = 100 * 1000 + 10;

ll dp[N][2];
vector <int> adj[N];
bool vis[N];

void dfs(int v,int par)
{
	vis[v] = 1;
	if(adj[v].size() == 1 && adj[v][0] == par)
	{
		dp[v][0] = 1;
		dp[v][1] = 1;
		return;
	}
	for (auto u : adj[v])
	{
		if(u == par)
			continue;
		dfs(u, v);
	}
	ll w = 1, b = 1;
	for (int u : adj[v])
	{
		if(u != par)
		{
			w *= (dp[u][0] + dp[u][1]);
			w %= mod;
			b *= (dp[u][0]);
			b %= mod;
		}
	}
	dp[v][0] = w;
	dp[v][1] = b;
}
 
int main()	
{
	faster();
	int n;
	cin >> n;
	if(n == 1)
	{
		cout << 2 << endl;
		return 0;
	}
	for (int i = 0; i < n - 1; i++)
	{
		int v, u;
		cin >> v >> u;
		v--;
		u--;
		adj[v].push_back(u);
		adj[u].push_back(v);
	}
	dfs(0, -1);
	cout << (dp[0][0] + dp[0][1]) % mod << endl;
}

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


using namespace std;
const int N = 1e5 + 10;

struct Edge {
	int to , nex;
} e[N << 1];
int head[N] , ecnt;

void adde(int fr,int to) {
	e[++ecnt] = (Edge) {
		to , head[fr]
	};
	head[fr] = ecnt;
}

void addedge(int fr,int to) {
	adde(fr , to);
	adde(to , fr);
}

int dg[N] , n , m , cnt4 , cnt6 , res;

bool vis[N];
void dfs(int s,int fr,int t) {
	if (s == t) {
		res++;
		return;
	}
	if (vis[s]) return;
	vis[s] = true;
	for (int j = head[s]; j; j = e[j].nex) if (e[j].to != fr){
		dfs(e[j].to , s , t);
	}
}
int main() {
	scanf("%d%d",&n,&m);

	for (int i = 1; i <= m; i++) {
		int fr , to;
		scanf("%d%d",&fr,&to);
		addedge(fr , to);
		dg[fr]++;
		dg[to]++;
	}

	for (int i = 1; i <= n; i++) {
		if (dg[i] & 1) {
			return puts("No") , 0;
		}
		if (dg[i] == 4) {
			cnt4++;
		} else if (dg[i] >= 6) {
			cnt6++;
		}
	}

	if (cnt6 || cnt4 >= 3) {
		puts("Yes");
		return 0;
	}
	if (cnt4 != 2) {
		puts("No");
		return 0;
	}
	int s = -1, t = -1;

	for (int i = 1; i <= n; i++) {
		if (dg[i] == 4) {
			if (s == -1) s = i;
			else t = i;
		}
	}
	dfs(s , s , t);;
	if (res == 2) {
		puts("Yes");
	} else {
		puts("No");
	}
	return 0;
}

Measured memory_bytes: 3840
"use strict";
function Main(input) {
    let lines = input.split("\n");
    let Ln = lines[0].split(/\s/).map((v) => v - 0);
    let H = Ln[0], W = Ln[1];
    Ln = lines[1].split(/\s/).map((v) => v - 0);
    let h = Ln[0], w = Ln[1];
    let wh = new Array(W).fill(0).map(() => new Array(H).fill(0));
    for (let y = 0; y < h; y++) 
        for (let x = 0; x < W; x++) { wh[x][y] = 1; }
    for (let y = 0; y < H; y++) 
        for (let x = 0; x < w; x++) { wh[x][y] = 1; }
    let ans = 0;
    for (let y = 0; y < H; y++) 
        for (let x = 0; x < W; x++) { if (wh[x][y] == 0) ans += 1; }
    console.log(ans);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 7372
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author NikuKyabe
 */

#include "bits/stdc++.h"
using namespace std;
#define int long long
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define REP(i,n)  FOR(i,0,(n))
#define SP << " " <<


class BJudgeStatusSummary {
public:
	void solve(std::istream& in, std::ostream& out) {
    int n;
    in >> n;
    map<string, int> map;
    REP(i,n){
      string s;
      in >> s;
      map[s]++;
    }

    const string a[] = {"AC", "WA", "TLE", "RE"};
    for(string b : a){
      out << b SP "x" SP map[b] << endl;
    }
	}
};


signed main() {
  ios::sync_with_stdio(false);
  cout.tie(0);
  cout << fixed;
	BJudgeStatusSummary solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 3664
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
MOD = 10 ** 9 + 7
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()

    ans = pow(10, N, MOD) - (2 * pow(9, N, MOD) - pow(8, N, MOD))
    ans %= MOD
    print(ans)

if __name__ == '__main__':
    resolve()


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

int main(){
  long long n, k;
  cin >> n >> k;
  vector<long long> a(n);
  for(long long i = 0; i < n; i++) cin >> a.at(i);
  
  vector<long long> ans(n, -1);
  bool ok = true;
  long long cnt = 0;
  long long now = 0;
  while(ok){
    if(ans.at(now) == -1){
      ans.at(now) = cnt++;
      now = a.at(now)-1;
    }
    else ok = false;
  }
  
  long long l = cnt - ans.at(now);
  long long p = k;
  if(k >= cnt) p = k - l*((k-ans.at(now))/l);
  for(long long i = 0; i < n; i++){
    if(ans.at(i) == p){
      cout << i+1 << endl;
      break;
    }
  }
}

Measured memory_bytes: 6404
#include <stdio.h>

int main(void) {

  int n;
  int h, m, s;

  scanf("%d", &n);
  h = n / 3600;
  n -= 3600 * h;
  m = n / 60;
  s = n - 60 * m;
  printf("%d:%d:%d\n", h, m, s);

  return 0;
}



Measured memory_bytes: 2064
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>

using namespace std;

int n;
int a[100005];
map<int, int>mp;

int main(){
  cin >> n;
  
  for(int i = 0; i < n; ++i){
    cin >> a[i];
  }
  for(int i = 0; i < n; ++i){
    mp[a[i]]++;
  }
  int ans = 0;
  for(auto p : mp){
    int x = p.first;
    int y = p.second;
    if(y < x){
      ans += y;
    }else{
      ans += y - x;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 5120
use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {
        l: i32,
        r: i32,
        d: i32,
    }

    let mut ans: i32 = 0;
    for i in l..r + 1 {
        if i % d == 0 {
            ans += 1;
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 2140
#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define ll long long
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repeat(i,s,n) for(int (i)=s; (i)<(n); (i)++)
#define revrep(i,n) for(int (i)=(n)-1;i>=0; i--)

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout<<setprecision(std::numeric_limits<float>::max_digits10);
  string s;
  cin>>s;
  ll n=s.size();
  vector<ll> freq(26);
  rep(i,n) {
    freq[static_cast<int>(s[i]-'a')]++;
  }
  ll sm=0;
  rep(i,26) {
    sm+=freq[i]*(freq[i]-1)/2;
  }
  cout << 1+n*(n-1)/2-sm << endl;
  return 0;
}


Measured memory_bytes: 720
#include <stdio.h>
#include <stdbool.h>
#include <math.h>

int main(){
  int n;
  scanf("%d", &n);
  
  int a[100005];
  int v[100005] = {0};
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
    v[a[i]]++;
  }
  bool ok = true;
  if (n % 2 == 0) {
    for (int i = 1; i < n; i+=2) {
      if (v[i] != 2) {
        ok = false;
      }
    }
  }
  if (n % 2 == 1) {
    if (v[0] != 1) {
      ok = false;
    }
    for (int j = 2; j < n; j+=2) {
      if (v[j] != 2) {
        ok = false;
      }
    }
  }
    
  long long ans = 1;
  if (ok) {
  	for (int k = 0; k < n/2; k++) {
    	ans = (long long) (ans % (1000000000 + 7)) * 2;
  	}
  	ans = (long long) ans % (1000000000 + 7);
  	printf("%lld", ans);
  }
  else {
    ans = 0;
    printf("%lld", ans);
  }
  return 0;
}

Measured memory_bytes: 896
# -*- coding: utf-8 -*-
list=[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
a=int(input())
print(list[a-1])


Measured memory_bytes: 2940
//Daniel Grzegorzewski
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3")

#define MP make_pair
#define PB push_back
#define ST first
#define ND second

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef long long LL;

void init_ios() {
     ios_base::sync_with_stdio(0);
     cin.tie(0);
}

const int N = (int)1e5 + 3;
const int LG = 18;
const int SQ = 320;

int n, q, t, a[N], b[N], c[N], d[N], ed[N], in[N], out[N], h[N], par[N][LG], sum[N][LG];
int nr, re, hm[N], id[N];
PII cur[N], wyn[SQ][N];
bool vis[N];
VII child[N];

void dfs(int v) {
  vis[v] = true;
  in[v] = t++;
  for (int i = 1; i < LG; ++i) {
    par[v][i] = par[par[v][i-1]][i-1];
    sum[v][i] = sum[v][i-1]+sum[par[v][i-1]][i-1];
  }
  for (auto p: child[v])
    if (!vis[p.ST]) {
      h[p.ST] = h[v]+1;
      par[p.ST][0] = v;
      sum[p.ST][0] = d[p.ND];
      ed[p.ST] = p.ND;
      dfs(p.ST);
    }
  out[v] = t++;
}

bool anc(int u, int v) {
  if (u == 0)
    return true;
  return (in[u] <= in[v] && out[v] <= out[u]);
}

int lca(int u, int v) {
  if (anc(u, v))
    return u;
  for (int i = LG-1; i >= 0; --i) {
    while (i >= 0 && anc(par[u][i], v))
      --i;
    if (i >= 0)
      u = par[u][i];
  }
  return par[u][0];
}

int suma(int u, int v) {
  int dis = h[v]-h[u];
  int res = 0;
  assert(dis >= 0);
  assert(anc(u, v));
  for (int i = LG-1; i >= 0; --i)
    if (dis&(1<<i)) {
      res += sum[v][i];
      v = par[v][i];
    }
  return res;
}

void dfs2(int v) {
  vis[v] = true;
  if (h[v]%SQ == re) {
    for (int i = 1; i < n; ++i)
      wyn[nr][i] = cur[i];
    id[v] = nr++;
  }
  for (auto p: child[v])
    if (!vis[p.ST]) {
      cur[c[p.ND]].ST += d[p.ND];
      cur[c[p.ND]].ND++;
      dfs2(p.ST);
      cur[c[p.ND]].ST -= d[p.ND];
      cur[c[p.ND]].ND--;
    }
}

PII get(int v, int col) {
  PII res = {0, 0};
  while (v != 0 && h[v]%SQ != re) {
    if (c[ed[v]] == col)
      res = {res.ST+d[ed[v]], res.ND+1};
    v = par[v][0];
  }
  if (v)
    res = {res.ST+wyn[id[v]][col].ST, res.ND+wyn[id[v]][col].ND};
  return res;
}

int main() {
  init_ios();
  cin >> n >> q;
  for (int i = 1; i < n; ++i) {
    cin >> a[i] >> b[i] >> c[i] >> d[i];
    child[a[i]].PB({b[i], i});
    child[b[i]].PB({a[i], i});
  }
  dfs(1);
  for (int i = 1; i <= n; ++i) {
    ++hm[h[i]%SQ];
    vis[i] = false;
  }
  for (int i = 1; i < SQ; ++i)
    if (hm[i] < hm[re])
      re = i;
  dfs2(1);
  while (q--) {
    int x, y, u, v;
    cin >> x >> y >> u >> v;
    int z = lca(u, v);
    PII r1 = get(u, x);
    PII r2 = get(v, x);
    PII r3 = get(z, x);
    PII hm = {r1.ST+r2.ST-2*r3.ST, r1.ND+r2.ND-2*r3.ND};
    cout<<suma(z, u) + suma(z, v) - hm.ST + y*hm.ND<<"\n";
  }
}

Measured memory_bytes: 271488
#include <iostream>
#include <vector>
#include <bitset>
#include <utility>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
 
using namespace std;
typedef long long ll;
 
int main(){
  string s;cin >> s;
  cout << s[0] << s[1] << s[2] << endl;


  return 0;
}


Measured memory_bytes: 3628
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
using namespace std;
inline int read()
{
	int f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int stack[20];
template<typename T>inline void write(T x)
{
	if(x<0){putchar('-');x=-x;}
    if(!x){putchar('0');return;}
    int top=0;
    while(x)stack[++top]=x%10,x/=10;
    while(top)putchar(stack[top--]+'0');
}
template<typename T>inline void pr1(T x){write(x);putchar(' ');}
template<typename T>inline void pr2(T x){write(x);putchar('\n');}
const int MAXMASK=(1<<19);
const int MAXN=20;
const int MAXM=200005;
int a[MAXM],n,V,mx;
vector<pii> vec[MAXN];
int L[MAXN][MAXM],R[MAXN][MAXM],cnt;
void work(int x,int o)
{
	for(int i=1,nxt;i<=n;i=nxt+1)
	{
		nxt=i;while(nxt+1<=n&&a[nxt+1]-a[nxt]<=x)++nxt;
		for(int j=i;j<=nxt;j++)L[o][j]=i,R[o][j]=nxt;
		if(!o)++cnt;
	}
}
int f[MAXMASK],g[MAXMASK],num[MAXN][MAXMASK],bin[25];
int main()
{
	bin[1]=1;for(int i=2;i<=20;i++)bin[i]=bin[i-1]<<1;
	n=read();V=read();
	for(int i=1;i<=n;i++)a[i]=read();
	int temp=V;while(temp)work(temp,mx++),temp>>=1;
	if(cnt>mx+1){for(int i=1;i<=n;i++)puts("Impossible");return 0;}
	for(int i=1;i<=n;i++)L[mx][i]=R[mx][i]=i;
	memset(g,63,sizeof(g));g[0]=n+1;
	for(int i=1;i<bin[mx+1];i++)for(int j=1;j<=mx;j++)if(i&bin[j])
	{
		int pre=f[i^bin[j]];
		f[i]=max(f[i],R[j][pre+1]);
		if(pre==n)f[i]=n;
		pre=g[i^bin[j]];
		g[i]=min(g[i],L[j][pre-1]);
		if(pre==1)g[i]=1;
	}
	for(int i=1;i<=n;i=R[0][i]+1)
	{
		bool tf=false;
		for(int j=0;j<bin[mx+1];j++)
		{
			int lim1=L[0][i],lim2=R[0][i];
			if(f[j]>=lim1-1&&g[(bin[mx+1]-1)^j]<=lim2+1){tf=true;break;}
		}
		if(tf)for(int j=i;j<=R[0][i];j++)puts("Possible");
		else for(int j=i;j<=R[0][i];j++)puts("Impossible");
	}
	return 0;
}


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

int main(){

	int A, B, X, ans;;

	cin >> A >> B >> X;

	// 1リットルあたりの料金がBの方が安いとき
	if(A > 2*B ){
		if(X%500 == 0) ans = B * (X/500);
		else if(X%500 > 0) ans = B + B * (X/500);
	}

	// 1リットルあたりの料金がAの方が安いとき AND 端数が0.5リットル以上のとき,端数が0.5リットル以下のとき）
	if(A <= 2*B){
		if(X%1000 == 0) ans = A * (X/1000);
		else if(X%1000 > 500) ans = A + A * (X/1000);
		else ans = B + A * (X/1000);
	}

	//料金がAの方が安いとき
	if(A < B){
		if(X%1000 == 0) ans = A * (X/1000);
		else  ans = A + A * (X/1000);
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 3124
function Main(input) {
	input = input.split("\n");
	const N = parseInt(input[0])
	const As = input.slice(1).map(x => parseInt(x))
	var max = As[0] > As[1] ? 1 : 0
	var second = As[0] > As[1] ? 0 : 1
	As.forEach((e,i) => {
		if(As[max] < e){
			second = max
			max = i
		}else if(As[second] < e){
			second = i
		}
	})
	for(i=0; i < N; i++){
		if(i == max){
			console.log(As[second])
		}else{
			console.log(As[max])
		}
	}
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

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

using namespace std;

#define int long long
#define pb push_back
#define sz(el) (int)el.size()

int max(int &a, int b) {
    if (b > a) {
        a = b;
        return 1;
    }
    return 0;
}

const int inf = 1e18;
const int maxN = 1000 + 100;
const int mod = 1e9 + 7;

char a[maxN][maxN];
int dp[maxN][maxN];

signed main() {
    
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
   
    int h, w;
    cin >> h >> w;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> a[i][j];
        }
    }

    dp[0][0] = 1;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (a[i][j] != '#') {
                if (i - 1 >= 0 && a[i - 1][j] != '#') {
                    dp[i][j] += dp[i - 1][j];
                    dp[i][j] %= mod;
                }
                if (j - 1 >= 0 && a[i][j - 1] != '#') {
                    dp[i][j] += dp[i][j - 1];
                    dp[i][j] %= mod;
                }
            }
        }
    }
    
    cout << dp[h - 1][w - 1];
    
    return 0;
    
}


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

using namespace std;

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;

const int N = (int) 1e5 + 7;
int n, m, a[N];
bool ok[N];

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    ok[i] = 1;
  }
  for (int i = 1; i <= m; i++) {
    int x, y;
    cin >> x >> y;
    if (a[x] >= a[y]) {
      ok[y] = 0;
    }
    if (a[y] >= a[x]) {
      ok[x] = 0;
    }
  }
  int sol = 0;
  for (int i = 1; i <= n; i++) {
    sol += ok[i];
  }
  cout << sol << "\n";
  return 0;
}


Measured memory_bytes: 4124
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <cassert>
using namespace std;
typedef long long ll;
const int INF = 1<<30;
const ll MOD = 1e9+7;
const double EPS = 1e-9;


int main(int argc, const char * argv[]) {
  int N, K; cin >> N >> K;
  string S; cin >> S;
  
  int cnt = 0;
  for(int i=0; i<N; i++){
//    if(S[i] == 'L' && S[i+1] == 'L') cnt++;
//    if(S[i] == 'R' && S[i+1] == 'R') cnt++;
    if(S[i] == S[i+1]) cnt++;
  }
  cout << min(cnt+2*K, N-1) << endl;
  return 0;
}


Measured memory_bytes: 512
// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>   
#include<map>
#include<set>
#include<unordered_map>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(ll i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define FOR(i,a) for(auto i:a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
//#define int ll
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
#define mt make_tuple
typedef tuple<int,int,int,int> tp;
typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
//template<class C>constexpr int size(const C &c){return (int)c.size();}
//template<class T,size_t N> constexpr int size(const T (&xs)[N])noexcept{return (int)N;}
const double PI=acos(-1);
const double EPS=1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9+10;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
// top front right left back bottom
//front
void S(vector<int>&in){
  int tmp=in[1];
  in[1]=in[0];
  in[0]=in[4];
  in[4]=in[5];
  in[5]=tmp;
}
//right
void E(vector<int>&in){
  int tmp=in[2];
  in[2]=in[0];
  in[0]=in[3];
  in[3]=in[5];
  in[5]=tmp;
}
//turn
void T(vector<int>&in){
  int tmp=in[1];
  in[1]=in[2];
  in[2]=in[4];
  in[4]=in[3];
  in[3]=tmp;
}
int main(){
	int n;
	while(cin>>n,n){
		vector<vip>in(n);
		rep(i,n){
			int x,y;cin>>x>>y;
			vi t(6);
// top front right left back bottom
			cin>>t[3]>>t[2]>>t[1]>>t[4]>>t[5]>>t[0];
			string s;cin>>s;
			in[i].pb({t[5],{x,y}});
			rep(j,s.size()){
				if(s[j]=='R')E(t),x++;
				if(s[j]=='L')E(t),E(t),E(t),x--;
				if(s[j]=='F')S(t),y--;
				if(s[j]=='B')S(t),S(t),S(t),y++;
				rep(k,in[i].size())if(in[i][k].second==pii(x,y)){in[i][k].first=t[5];goto end;}
				in[i].pb({t[5],{x,y}});
				end:;
			}
		}
		int N=1<<n;
		vi dp(N,-inf);
		dp[0]=0;
		rep(i,N){
			map<pii,int>ma;
			rep(j,n)if(i&1<<j)rep(k,in[j].size())ma[in[j][k].second]=1;
			rep(j,n)if((i&1<<j)==0){
				int sum=0;
				rep(k,in[j].size())if(ma.count(in[j][k].second)==0)
					sum+=in[j][k].first;
				cmax(dp[i|1<<j],dp[i]+sum);
			}
		}
		cout<<dp[N-1]<<endl;
	}
}











Measured memory_bytes: 3284
fn main() {
    let n: i64 = read();
    println!("{}", (n / 2) + (n % 2));
}

use std::io::stdin;
use std::io::Read;
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
    let cin = stdin();
    let cin = cin.lock();
    let token: String = cin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef vector<vector<int>> Matrix;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()


int main(){
  int n;
  cin >> n;
  vector<int> l(n);
  rep(i, n) cin >> l[i];
  sort(ALL(l));
  int ans = 0;
  rep(i, n) rep(j, i) {
    int r = lower_bound(ALL(l), l[i]+l[j]) - l.begin();
    ans += max(0, r-i-1);
  }
  cout << ans << endl;
}


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

int main(){
  int A,B,C,D;
  cin >> A >> B >> C >> D;
  
  int Left, Right;
  Left = A+B;
  Right = C+D;
  
  if (Left > Right)
    cout << "Left" << endl;
  else if (Left < Right)
    cout << "Right" << endl;
  else if (Left == Right)
    cout << "Balanced" << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int maxN=(1e3)+5;

int n,m,a,b,S[maxN][maxN];
int main()
{
    cin>>n>>m>>a>>b;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            S[i][j]=1;

    for(int i=1;i<=b;i++)
        for(int j=1;j<=a;j++)
            S[i][j]=0;

    for(int i=b+1;i<=n;i++)
        for(int j=a+1;j<=m;j++)
            S[i][j]=0;

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            cout<<S[i][j];
        cout<<'\n';
    }

    return 0;
}


Measured memory_bytes: 5120
#include <iostream>
#include <algorithm>
#include <cmath>
#include <climits>
using namespace std;

using ll = long long;

int main() {

	int n;

	cin >> n;

	int minusCount = 0;
	ll minValue = LLONG_MAX;

	ll sum = 0;

	for (int i = 0; i < n; ++i) {
		ll a;
		cin >> a;

		if (a < 0)
			minusCount++;

		minValue = min(minValue, abs(a));
		sum += abs(a);
	}

	if (minusCount % 2 == 1)
		sum -= minValue * 2;

	cout << sum << endl;

	return 0;

}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)
int main(){
  int a,b,c,d;
  cin >> a >> b >> c >> d;
  int x = c - a;
  int y = d - b;
  cout << c - y << " " << d + x << " " << a - y << " " << b + x << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define F first
#define S second
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define Blue ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define rep(i,a,n) for(int i=a;i<n;++i)
typedef vector<int> vi;
typedef long long ll;
const int mod=1e9+7;
 
const int dx[]={1,-1,0,0},dy[]={0,0,1,-1};

void solve(){
	int n;
	cin>>n;
	for(int i=1;i<=9;i++){
		for(int j=1;j<=9;j++){
			if(i*j==n){
				cout<<"Yes";
				return;
			}
		}
	}
	cout<<"No";
 
}
 
 
int main(){
	Blue;
	int test=1;
	//cin>>test;
	while(test--)
		solve();
	return 0;
}

Measured memory_bytes: 3648
use std::env;
use std::io::*;
use std::str::*;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let s = stdin.bytes().map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect::<String>();
    s.parse::<T>().ok().unwrap()
}

fn main() {
    // main の引数
    /*
        引数なしのときargs.len() = 1;
    */
    let args: Vec<String> = env::args().collect();

    let a = read::<i32>();
    let b = read::<i32>();
    let h = read::<i32>();
    println!("{}", (a+b)*h/2);

}


Measured memory_bytes: 4352