akhauriyash/Code-Regression huggingface dataset:
N = int(input())

l = 0
j = 0
r = N -1

print(0, flush=True)
a = input()
if a == 'Vacant':
  exit()
b = a
while r - l > 1:
  i = (r + l)//2
  print(i, flush=True)
  a = input()
  if a == 'Vacant':
    exit()
  if abs(i-j)%2 == 0:
    if a == b:
      if i > j:
        l = i
      else:
        r = i
    else:
      if i > j:
        r = i
      else:
        l = i
  else:
    if a == b:
      if i > j:
        r = i
      else:
        l = i
    else:
      if i > j:
        l = i
      else:
        r = i
      
  b = a
  j = i

print(l, flush=True)
a = input()
if a == 'Vacant':
  exit()
  
print(r, flush=True)


Measured memory_bytes: 62164
#include<iostream>
#include<iomanip>
#include<string>
#include<algorithm>
#include<vector>
#include<utility>
#include<tuple>
#include<map>
#include<queue>
#include<stack>
#include<deque>
#include<bitset>
#include<math.h>
using namespace std;
using ll = int64_t;
using Graph = vector<vector<int> >;
const ll M = 1000000007;

vector<pair<ll, ll> > prime_factorize(ll N) {
    vector<pair<ll, ll> > res;
    for (ll a = 2; a * a <= N; ++a) {
        if (N % a != 0) continue;
        ll ex = 0; // 指数

        // 割れる限り割り続ける
        while (N % a == 0) {
            ++ex;
            N /= a;
        }

        // その結果を push
        res.push_back(make_pair(a,ex));
    }

    // 最後に残った数について
    if (N != 1) res.push_back(make_pair(N,1));
    return res;
}

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

    const auto &res=prime_factorize(n);

    ll ans=0;
    for(auto p: res){
        ll tmp=1,cnt=1;
        while(tmp<=p.second){
            cnt++;
            tmp+=cnt;
        }
        cnt--;
        ans+=cnt;
    }
    cout << ans << endl;
}

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

using namespace std;
using ll = long long;

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)

int main() {
  int h, w, k;
  cin >> h >> w >> k;
  int s[h][w];
  rep(i, h) rep(j, w) {
    char c;
    cin >> c;
    s[i][j] = c - '0';
  }

  const int INF = 1001001001;
  int ans = INF;
  rep(t, 1 << (h - 1)) {
    int now = __builtin_popcount(t);
    vector<int> block(now + 1, 0);
    rep(c, w) {
      vector<int> temp(block.size(), 0);
      int cur = 0;
      rep(r, h) {
        temp[cur] += s[r][c];
        if (t >> r & 1) ++cur;
      }

      int mx = 0;
      for (auto v : temp) mx = max(mx, v);
      if (mx > k) {
        now = INF;
        break;
      }

      bool ok = true;
      rep(i, block.size()) if (block[i] + temp[i] > k) ok = false;
      if (ok) {
        rep(i, block.size()) block[i] += temp[i];
      } else {
        ++now;
        rep(i, block.size()) block[i] = temp[i];
      }
    }
    ans = min(ans, now);
  }

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


Measured memory_bytes: 256
N,M = map(int,input().split())
A = set(int(input()) for i in range(M))
dp=[0]*(N+1)
dp[0]=1
for i in range(1,N+1):
    dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
    if i in A:
        dp[i]=0
print(dp[N])

Measured memory_bytes: 11884
#include <cstdio>
#include <math.h>

using namespace std;

double co = cos(60.0*M_PI/180.0);
double si = sin(60.0*M_PI/180.0);

struct Point {double x, y;};


void koch(int n, struct Point p1, struct Point p2) {
	if (n==0) return;	//do nothing
	struct Point s,t,u;

	s.x = (2.0*p1.x+p2.x)/3.0;
	s.y = (2.0*p1.y+p2.y)/3.0;
	 
	t.x = (p1.x+2.0*p2.x)/3.0;
	t.y = (p1.y+2.0*p2.y)/3.0;

	u.x = (t.x-s.x)*co - (t.y-s.y)*si + s.x;
	u.y = (t.x-s.x)*si + (t.y-s.y)*co + s.y;

	koch(n-1,p1,s);
	printf("%.8f %.8f\n", s.x, s.y);
	
	koch(n-1,s,u);
	printf("%.8f %.8f\n", u.x, u.y);

	koch(n-1,u,t);
	printf("%.8f %.8f\n", t.x, t.y);

	koch(n-1,t,p2);
}

int main() {
	struct Point p1 = {0.0, 0.0};
	struct Point p2 = {100.0, 0.0};
	int n;
	scanf("%d\n",&n);
	printf("%f %f\n", p1.x,p1.y);

	koch(n, p1,p2);

	printf("%f %f\n", p2.x, p2.y);

	return 0;
}

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

// typedef
// -----------------------------------------------------------------------------
typedef long long ll;
typedef long double ld;

// container util
// -----------------------------------------------------------------------------
#define ALL(c)  (c).begin(),(c).end()
#define SZ(c) ((ll)(c).size())
#define MAX(c) *max_element(ALL(c))
#define MIN(c) *min_element(ALL(c))
#define SORT(c) sort((c).begin(),(c).end())

// repetition
// -----------------------------------------------------------------------------
#define FOR(i, a, b) for(ll i= (a); i < (ll)(b); ++i)
#define REP(i, n) FOR(i, 0, n)

// constant
// -----------------------------------------------------------------------------
const ll INF = 1e9;
const ll MOD = 1e9 + 7;
const double EPS = 1e-9;
const double PI = acos(-1.0);

// debug
// -----------------------------------------------------------------------------
#define DUMP(x)  cerr << #x << " = " << (x) << endl


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
    ll N; cin >> N;
    ll ans = N * (N - 1) / 2; 
    cout << ans << "\n";
}

Measured memory_bytes: 3556
import sys

for line in sys.stdin:
    a, b, e, c, d, f = map(int, line.split())
    det = a * d - b * c
    a11 = d / det
    a12 = - b / det
    a21 = - c / det
    a22 = a / det
    print("%.3f %.3f" % (round(a11 * e + a12 * f, 3), round(a21 * e + a22 * f, 3)))

Measured memory_bytes: 7588
package main

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

var sc = bufio.NewScanner(os.Stdin)

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func nextLine() string {
	sc.Scan()
	return sc.Text()
}

var grid [][]string

type alice struct {
	A int
	B int
}

type bob struct {
	C int
	D int
}

func main() {
	sc.Split(bufio.ScanWords)

	alice := alice{nextInt(), nextInt()}
	bob := bob{nextInt(), nextInt()}

	dt := 0

	if alice.A <= bob.C && bob.C <= alice.B && alice.A <= bob.D && bob.D < alice.B {
		dt = bob.D - bob.C
	} else if bob.C <= alice.A && alice.A <= bob.D && bob.C <= alice.B && alice.B <= bob.D {
		dt = alice.B - alice.A
	} else if alice.A <= bob.C && bob.C <= alice.B && alice.B <= bob.D {
		dt = alice.B - bob.C
	} else if alice.A <= bob.D && bob.D <= alice.B && bob.C <= alice.A {
		dt = bob.D - alice.A
	}

	fmt.Println(dt)

}


Measured memory_bytes: 640
import java.util.Scanner;

public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		
		int numbers = sc.nextInt();
		int point = sc.nextInt();
		
		int min = point - numbers + 1;
		int max = point + numbers - 1;
		
		for(int i = min;i <= max;i++) {
			System.out.print(i + " ");
		}
	}
}


Measured memory_bytes: 23252
#include <bits/stdc++.h>
using namespace std;
typedef long long int LL;

template <typename T>
ostream& operator <<(ostream& out, const vector<T>& vec) {
    out << "[";
    for (int x : vec) out << x << ", ";
    out << "]";
    return out;
}

#if DEBUG && !ONLINE_JUDGE
    ifstream input_from_file("input.txt");
    #define cin input_from_file
    #define dbg_var(x) clog << #x << ": " << x << endl;
#endif

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    LL N;
    cin >> N;
    LL M = 0;
    int sum = 0, i = 0;
    while(true) {
        if(M * 10 + 9 < N) {
            M = M * 10 + 9;
            sum += 9;
            ++i;
        } else {
            break;
        }
    }
    LL K = 1;
    while(i--) {
        K *= 10;
    }
    while(true) {
        if(M + K <= N) {
            M += K;
            ++sum;
        } else {
            break;
        }
    }
    cout << sum << '\n';
            
}


Measured memory_bytes: 256
#include<bitset>
#include<math.h>
#include<limits.h>
#include<iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include<sstream>
#include<list>
#include<queue>
#include<algorithm>
#include<functional>
#include<map>
#include<set>
#include<utility>
#include<initializer_list>
#include<tuple>
#include<regex>
using namespace std;
#define ull unsigned long long
#define ll long long
#define rep(i, n) for(int i=0;i<(int)(n);i++)
#define rep1n(i, n) for(int i=1;i<=(int)(n);i++)
#define all(t) t.begin(), t.end()
#define rall(t) t.rbegin(), t.rend()
#define mat(type, row, col, init) vector<vector<type>>(row, vector<type>(col, init));
#define Yes(cond) cout<<(cond? "Yes":"No")<<endl;
#define YES(cond) cout<<(cond? "YES":"NO")<<endl;
int main() {
	int n;
	cin >> n;
	map<string, int>s;
	rep(i, n) {
		string a;
		cin >> a;
		s[a]++;
	}
	int m;
	cin >> m;
	map<string, int>t;
	rep(i, m) {
		string a;
		cin >> a;
		t[a]++;
	}
	int ma = 0;
	for (auto v : s) {
		ma = max(ma, v.second - t[v.first]);
	}
	cout << ma;


	return 0;
}





Measured memory_bytes: 256
def main():
    N, M = map(int, input().split())
    E = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        E[a - 1].append(b - 1)
        E[b - 1].append(a - 1)
    C = [-1] * N
    C[0] = 0
    cur = set([0])
    while cur:
        nxt = set()
        for c in cur:
            for e in E[c]:
                if C[e] != -1:
                    continue
                C[e] = c
                nxt.add(e)
        cur = nxt
    print('Yes')
    print('\n'.join(str(i + 1) for i in C[1:]))
main()


Measured memory_bytes: 41928
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep_lr(i,l,r) for(int i=(l);i<(r);i++)
#define all(x) (x).begin(),(x).end()
#define V vector
typedef V<int> vi;
typedef V<vi> vvi;
typedef long long ll;
typedef pair<ll, ll> P;
typedef tuple<int, int, int> T;
constexpr int INF = INT_MAX >> 1;
constexpr ll LINF = 5000000000000000LL;
constexpr int MOD = 1000000007;

int main() {
	
	int n, k;
	cin >> n >> k;
	vi a(n);
	rep(i, n)cin >> a[i];

	ll l = 0;
	ll r = 1e10;

	while (r - l > 1) {

		ll c = (r + l) / 2;
		ll cnt = 0;

		rep(i, n)cnt += (a[i] + c - 1) / c - 1;

		if (cnt <= k)r = c;
		else l = c;
	}

	cout << r << endl;

}

Measured memory_bytes: 4044
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cstdio>
#include<vector>
using namespace std;
typedef long long ll;
int n,he;
ll a[1000009],b[1000009];
ll ans=0;
bool check(ll sum,ll k)
{
  he=1;
  for (int i=n;i>=1;i--)
  {
  	//if (sum==9) cout<<"!@"<<a[he]<<" "<<b[i]<<endl;
    if (a[he]*b[i]<=sum) {he++;continue;}
    if ((a[he]-sum/b[i])>k) return false;
    k-=a[he]-sum/b[i];
    he++;
  }
  return true;
}
int main()
{
  ll k;
  scanf("%d%lld",&n,&k);
  for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
  for (int i=1;i<=n;i++) scanf("%lld",&b[i]);
  sort(a+1,a+1+n); sort(b+1,b+1+n);
  //for (int i=1;i<=n;i++) cout<<a[i]<<" ";
 // cout<<endl;
 // for (int i=n;i>=1;i--) cout<<9/b[i]<<" ";
 // cout<<endl;
  ll l=0,r=0;
  r=b[n]*a[n];ans=r;
  while (l<=r)
  {
  	ll mid=(l+r)/(ll)2;
  	if (check(mid,k)) ans=mid,r=mid-1;
  	else l=mid+1;
  }
  printf("%lld\n",ans);
  return 0;
}

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

int main(){
	int k, n;
	cin >> k >> n;
	int a[n+1];
	a[0] = 0;
	int mx = 0;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		mx = max(mx, a[i]-a[i-1]);
	}
	mx = max (mx, k-a[n]+a[1]);
	cout << k-mx << "\n";
	return 0;
}


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

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;

ll MOD = 998244353;

class mint{
    ll n;
public:
    mint(ll m = 0){
        n = ((m % MOD) + MOD) % MOD;
    }
    bool operator==(const mint& m){
        return n == m.n;
    }
    mint operator-() const {
        return mint(-n);
    }
    mint& operator+=(const mint& m){
        n += m.n;
        if(n >= MOD) n -= MOD;
        return *this;
    }
    mint& operator-=(const mint& m){
        n += MOD - m.n;
        if(n >= MOD) n -= MOD;
        return *this;
    }
    mint& operator*=(const  mint& m){
        n *= m.n;
        n %= MOD;
        return *this;
    }
    mint operator+(const mint& m) const{
        mint res(*this);
        res += m;
        return res;
    }
    mint operator-(const mint& m) const{
        mint res(*this);
        res -= m;
        return res;
    }
    mint operator*(const mint& m) const{
        mint res(*this);
        res *= m;
        return res;
    }
    mint pow(ll t) const{
        if(t == 0) return mint(1);
        mint m = pow(t>>1);
        m *= m;
        if(t & 1 == 1) m *= *this;
        return m;
    }
    // for prime modulo
    mint inv() const{
        return pow(MOD-2);
    }
    mint& operator/=(const mint& m){
        (*this) *= m.inv();
        n %= MOD;
        return *this;
    }
    mint operator/(const mint& m) const{
        mint res(*this);
        res /= m;
        return res;
    }
    friend ostream& operator<<(ostream& os, const mint& m){
        os << m.n;
        return os;
    }
};

ll N,S;
ll A[3000];
mint dp[3050][3050];

int main(){
    cin >> N >> S;
    mint t = mint(1) / mint(2);
    for(int i=0;i<N;i++) cin >> A[i];
    dp[0][0] = mint(2).pow(N);
    for(int i=0;i<N;i++){
        for(int j=0;j<=S;j++){
            if(dp[i][j] == mint(0)) continue;
            dp[i+1][j] += dp[i][j];
            if(j+A[i]<=S){
                dp[i+1][j+A[i]] += dp[i][j] * t;
            }
        }
    }
    cout << dp[N][S] << endl;
    return 0;
}

Measured memory_bytes: 76336
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<limits>
#include<set>
#include<queue>
using namespace std;
#define int long  long int
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
typedef pair<int, int>P;
const int INF = 1e8;

signed main() {
	int a, b;
	cin >> a >> b;
	cout << a - 1 +(a <= b);
}

Measured memory_bytes: 256
/* When Talent doesn't work, Hard work beats Talent*/

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")

#include"bits/stdc++.h"

using namespace std;

#define Fast_D cout<<fixed<<setprecision(2);
#define FastIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

#define nl "\n"
#define sp " "
#define int long long
#define double long double
#define all(v) v.begin(),v.end()
#define scanstr(s) cin>>ws; getline(cin,s);

const double PI=3.141592653589793;

void solve()
{
	string s[3];
	for(int i=0;i<3;i++) cin >> s[i];
	for(auto &c : s) reverse(all(c));
	int cur=0;
	while(s[cur].size()>0)
	{
		int x=cur;
		cur=s[x].back() - 'a';
		s[x].pop_back();
	}
	char ans= 'A'+cur;
	cout << ans << nl;
}

int32_t main()
{
	FastIO;
	Fast_D;
	int T;
	T=1;
	while(T--)
	{
		solve();
	}
	return 0;
}


Measured memory_bytes: 3632
def bubble_sort(lis, len):
    flag = 1
    times = 0
    while flag:
        flag = 0
        for i in range(len - 1, 0, -1):
            if lis[i] < lis[i - 1]:
                ele = lis[i]
                lis[i] = lis[i - 1]
                lis[i - 1] = ele
                times += 1
                flag = 1
    return times


inputs = []
while True:
    try:
        inputs.append(input())
    except(EOFError):
        break

ln = int(inputs[0])
li = list(map(int, inputs[1].split()))

t = bubble_sort(li, ln)

print(*li)
print(t)



Measured memory_bytes: 5604
num_array = gets.chomp.split("").sort!.uniq
if num_array.length.odd?
  puts "No"
elsif (num_array.member?("S") && num_array.member?("N")) || (num_array.member?("E") && num_array.member?("W"))
  puts "Yes"
else
  puts "No"
end

Measured memory_bytes: 3836
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define f(i,a,b) for(int i=a;i<b;i++)
#define endl '\n'
#define spc " "
#define pb push_back
#define mp make_pair
#define mod 1000000007

int main(){
   //freopen("in.txt","r",stdin);
   //freopen("output.txt","w",stdout);
   ll a,b,c,k;
   cin>>a>>b>>c>>k;
   ll p=k;
   if(a>=k) cout<<min(k,a)<<endl;
   else{
   		if(b>=k) cout<<min(a,k)<<endl;
   		else {
   			p=p-b;
   			cout<<a-(p-a)<<endl;
   		}
   } 
}



Measured memory_bytes: 3588
#include <bits/stdc++.h>
#define ALL(A) (A).begin(), (A).end()
#define ll long long
#define rep(i, n) for (int i = 0; i < (n); i++)

using namespace std;

const ll mod = 1e9 + 7;
const ll INF = -1 * ((1LL << 63) + 1);
const int inf = -1 * ((1 << 31) + 1);

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    int N;
    cin >> N;
    vector<ll> P(N);
    rep(i,N)cin >> P[i];
    ll ans = 0;
    ll mn = inf;
    rep(i,N){
        if(P[i]<=mn){ans++;mn = P[i];}
    }
    cout << ans << endl;
}

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

int main()
{	
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  string s;
  cin>>s;
  int count=0;
  if(s=="RRR"){
  	count=3;
  }
  else if(s=="SSS"){
  	count=0;
  }
  else if(s=="RRS"){
  	count=2;
  }
  else if(s=="SRR"){
  	count=2;
  }
  else{
  	count=1;
  }
  
  cout<<count<<endl;
	return 0;
	
}

Measured memory_bytes: 3648
n, m, X, Y = map(int,input().split())
x = list(map(int,input().split()))
y = list(map(int,input().split()))

if X < Y and max(max(x), X) < min(y) and max(x) < min(min(y), Y):
  print("No War")
else:
  print("War")

Measured memory_bytes: 3060
#include<stdio.h>
int main(){
	int a,b,c,C=0,i;
	
	scanf("%d %d %d",&a,&b,&c);
	
	for(i=a;i<=b;i++){
		if(c%i==0) C=C+1;
	}
	printf("%d\n",C);

	return 0;
}

Measured memory_bytes: 1860
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;

int main(){
    int a, b, cnt = 0, reverse;
    cin >> a >> b;
    for(int j = a; j < b + 1; j++){
        int i = j;
        reverse = 0;
        while(i != 0){
            reverse = reverse * 10 + i % 10;
            i /= 10;
        }
        if(reverse == j) cnt++;
    }
    cout << cnt << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
int main(void){
	long long A,B,N,ans,buff1,buff2;
	int i;
	char str[10000000],buf[10000000];
 
	fgets(str, sizeof(str), stdin);
	A=strtoll(strtok(str ," "),buf,10);
	B=strtoll(strtok(NULL," "),buf,10);
	N=strtoll(strtok(NULL," "),buf,10);
  
  	if(N>=(B-1)){
 		buff1=A*(B-1)/B;
		buff2=0;
		buff2*=A;
      	ans=buff1-buff2;
    }else{
 		buff1=A*N/B;
		buff2=N/B;
		buff2*=A;
      	ans=buff1-buff2;
    }

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

	return 0;
}

Measured memory_bytes: 2140
#include <bits/stdc++.h>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep2(i,a,n) for(int i=a;i<n;i++)
#define been(ix) (ix).begin(),(ix).end()
using namespace std;
typedef long long ll; 
typedef vector<int> vi;
typedef vector<long long> vl;
const ll INFL = 1e18;
const int INF = 1001001001; 
typedef pair<int,int> P;
#define foreach(ix,i) for(auto& (ix) : (i))
typedef long double ld;
const int mod =1000000007;
int main(){
   int r;
   cin>>r;
   double pi = 3.141592;
   double ans = 2*r*pi;
   cout<<ans<<endl;
}


Measured memory_bytes: 3788
n, a, b, c = map(int, input().split())
l = [int(input()) for _ in range(n)]
INF = 10**9
def count(a_sum, b_sum, c_sum, cur):
  if cur == n:
    return (abs(a_sum -a) + abs(b_sum -b) +abs(c_sum -c)) -30 if min(a_sum, b_sum, c_sum) > 0 else INF
  else:
    ans1 = count(a_sum, b_sum, c_sum, cur+1)
    ans2 = count(a_sum+l[cur], b_sum, c_sum, cur+1) + 10 
    ans3 = count(a_sum, b_sum+l[cur], c_sum, cur+1) + 10
    ans4 = count(a_sum, b_sum, c_sum+l[cur], cur+1) + 10
    return min(ans1, ans2, ans3, ans4)

print(count(0, 0, 0, 0))

Measured memory_bytes: 3064
using System;

class Problem
{
  public static void Main()
  {
    var inputs = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
    int X = inputs[0], A = inputs[1], B = inputs[2];
    if (B <= A) Console.WriteLine("delicious");
    else if (B - A <= X) Console.WriteLine("safe");
    else Console.WriteLine("dangerous");
  }
}


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


int main(){
	int R, C, r, c;
	cin >> R>> C>> r>> c;
	int blackSq =0;
	blackSq+= r*C;
	blackSq +=  c* (R-r);
	int whiteSq= (R*C)- blackSq;
	cout << whiteSq<< '\n'; 
}

Measured memory_bytes: 256
n, m = map(int, input().split())
dic = {}
for i in range(n):
	dic[i+1] = 0
for i in range(m):
	x, y = map(int, input().split())
	if x in dic:
		dic[x] += 1
	else:
		dic[x] = 1
	if y in dic:
		dic[y] += 1
	else:
		dic[y] = 1
for i,j in sorted(dic.items()):
	print (j)

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

vector<int> w, v;
vector<vector<int>> dp;

int main() {
	int n, W; cin >> n >> W; w.resize(n); v.resize(n);
	for (int i = 0; i < n; i++) cin >> w[i] >> v[i];
	dp.resize(2, vector<int>(n * 1000 + 2, 1 << 30));
	dp[0][0] = 0; for (int i = 1; i <= n; i++) {
		fill(dp[i & 1].begin(), dp[i & 1].end(), 1 << 30);
		dp[i & 1][0] = 0; for (int j = n * 1000; j > 0; j--) {
			dp[i & 1][j] = min({ dp[i & 1][j], dp[(i ^ 1) & 1][j], dp[i & 1][j + 1] });
			if (j >= v[i - 1]) dp[i & 1][j] = min(dp[i & 1][j], dp[(i ^ 1) & 1][j - v[i - 1]] + w[i - 1]);
		}
	}
	int res = upper_bound(dp[n & 1].begin(), dp[n & 1].end(), W) - dp[n & 1].begin();
	cout << res - 1 << '\n'; cin.ignore(2); return 0;
}

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


int main()
{
  ll n, k, q;
  cin >> n >> k >> q;
  vector<ll> a(n+1);
  
  for (ll i = 1; i <= n; ++i) {
    a[i] = 0;
  }
  for (ll i = 0; i < q; ++i) {
    ll j;
    cin >> j;
    ++(a[j]);
  }
  for (ll i = 1; i <= n; ++i) {
    if (k <= (q - a[i])) {
      cout << "No" << endl;
    } else {
      cout << "Yes" << endl;
    }
  }
  return 0;
}



Measured memory_bytes: 1408
#include <iostream>
#include<iomanip>
using namespace std;
int main(void)
{
   int a;
   int b;
   int d;
   int r;
 double f;
   cin>>a>>b;
   d=a/b;
   r=a%b;
   f=(double)a/(double)b;
   cout<<d<<" "<<r<<" "<<fixed<<setprecision(5)<<f;
   cout<<endl;
}


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

int main() {
    string s, t;
    cin >> s >> t;
    for(int i=0; i<s.length(); i++) {
        if(i==s.length()-1 && s.length()!=t.length()) cout << s[i];
        else cout << s[i] << t[i];
    }
    cout << endl;

    return 0;
}



Measured memory_bytes: 256
#include <algorithm>
#include <array>
#include <cassert>
#include <iostream>
#include <vector>
using namespace std;

template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { os << '{'; string sep; for (const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }
template<typename T, size_t size> ostream& operator<<(ostream &os, const array<T, size> &arr) { os << '{'; string sep; for (const auto &x : arr) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }

void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }

#ifdef NEAL_DEBUG
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif


const int BITS = 18;

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

    if ((S | T) != T) {
        cout << 0 << '\n';
        return 0;
    }

    vector<int> A;

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

        if ((a & S) != S || (a | T) != T)
            continue;

        A.push_back(a);
    }

    N = int(A.size());
    K = min(K, N);

    vector<vector<int64_t>> choose(N + 1, vector<int64_t>(N + 1, 0));

    for (int i = 1; i <= N; i++) {
        choose[i][0] = choose[i][i] = 1;

        for (int j = 1; j < i; j++)
            choose[i][j] = choose[i - 1][j] + choose[i - 1][j - 1];
    }

    vector<int64_t> up_to_K(N + 1, 0);

    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= K; j++)
            up_to_K[i] += choose[i][j];

    vector<int> freq(1 << BITS, 0);
    int64_t answer = 0;
    int overall = S ^ T;

    for (int mask = overall; ; mask = (mask - 1) & overall) {
        vector<int> ands(N);

        for (int i = 0; i < N; i++) {
            ands[i] = A[i] & mask;
            freq[ands[i]]++;
        }

        int64_t sum = 0;

        for (int i = 0; i < N; i++) {
            sum += up_to_K[freq[ands[i]]];
            freq[ands[i]] = 0;
        }

        answer += (__builtin_popcount(mask) % 2 == 0 ? +1 : -1) * sum;

        if (mask == 0)
            break;
    }

    cout << answer << '\n';
}


Measured memory_bytes: 4324
class Node():
    def __init__(self, key):
        self.key = key
        self.left = self.right = None
        
def insert(key):
    global root

    x = root
    y = None
    while x:x, y = x.left if key < x.key else x.right , x
    if y == None:root = Node(key)
    elif y.key < key:y.right = Node(key)
    else:y.left = Node(key)
        
        
def pre(node):
    if node == None:return
    print('',node.key, end = '');pre(node.left);pre(node.right)
    
def ino(node):
    if node == None:return
    ino(node.left);print('',node.key,end='');ino(node.right)

def find(node, key):
    if node == None:
        print('no');return
    if node.key == key:
        print('yes');return
    elif node.key > key:
        find(node.left, key)
    else:
        find(node.right, key)

def delete(node, key):
    x = node
    while x and x.key != key :
        x, y = x.left if key < x.key else x.right, x
    if x == None:
        return
    else:
        if key < y.key:f = 1
        else:f = 0
        if x.left == None and x.right == None:
            if f:y.left = None
            else:y.right = None
        elif x.right == None:
            if f:y.left = x.left
            else:y.right = x.left
        elif x.left == None:
            if f:y.left = x.right
            else:y.right = x.right
        else:
            a = x.right
            c = 0
            b = 1
            while a:a, b, c = a.left if a.left != None and a.right != None else a.left if a.left != None else None  , a, b
            if c == 1:
                b.left = x.left
                if f:y.left = b
                else:y.right = b
            else:
                c.left = b.right
                x.key = b.key
                
                
            
        
        
    

n = int(input())
root = None
for j in range(n):
    s, *i = input().split()
    if s[0] == 'i':insert(int(i[0]))
    elif s[0] == 'f':
        find(root, int(i[0]))
    elif s[0] == 'd':
        delete(root, int(i[0]))
    else:
        ino(root);print();pre(root);print()
        
    


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

using namespace std;


int A[200005];
int main() {
    int n, t;
    scanf("%d%d", &n, &t);
    for (int i = 0; i < n; ++i) scanf("%d", A + i);

    int maxP = 0;
    int minV = A[0];
    for (int i = 0; i < n; ++i) {
        maxP = max(maxP, A[i] - minV);
        minV = min(minV, A[i]);
    }

    minV = A[0];
    int res = 0;
    for (int i = 0; i < n; ++i) {
        if (A[i] - minV == maxP) res++;
        minV = min(minV, A[i]);
    }
    if (n == 1) res = 0;

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

    return 0;
}


Measured memory_bytes: 640
// C.cpp
#include <bits/stdc++.h>

using namespace std;

int main()
{
    long long prod, ans;
    scanf("%lld", &prod);
    ans = prod - 1;
    for (int i = 2; 1LL * i * i <= prod; i++)
        if (prod % i == 0)
            ans = min(ans, (prod / i) + i - 2);
    printf("%lld", ans);
    return 0;
}

Measured memory_bytes: 256
S=list(input())
T=list(input())
len0=len(S)
S=S*(len(T)//len0+1)

S=S+S

p=26
mod=(1<<31)+7# 互いに素なものを指定

TABLE=[0]# Rolling Hashのテーブル. 最初は0
LEN=len(S)

for i in range(LEN):
    TABLE.append((p*TABLE[-1]%mod+ord(S[i])-97)%mod)# テーブルを埋める

NOW=0
LEN2=len(T)

for i in range(LEN2):
    NOW=(p*NOW%mod+ord(T[i])-97)%mod

TH=NOW

def hash_ij(i,j): # [i,j)のハッシュ値を求める
    return (TABLE[j]-TABLE[i]*pow(p,j-i,mod))%mod

OK=[0]*LEN

for i in range(LEN2,LEN):
    if hash_ij(i-LEN2,i)==TH:
        OK[i-LEN2]=1

OK=OK[:len0]

ANS=0

ST=[-1]*len0

for i in range(len0):
    if OK[i]==1 and ST[i]==-1:

        j=i
        count=0

        while OK[j]==1:
            
            if ST[j]!=-1:
                count+=ST[j]
                break
            
            count+=1
            ST[j]=1
            j=(j+LEN2)%len0
            if j==i:
                print(-1)
                import sys
                sys.exit()

        ST[i]=count
        ANS=max(ANS,count)

print(ANS)


Measured memory_bytes: 168452
N = int(input())

nums = [int(i) for i in input().split()]
baisuu = [0,0,0]
for n in nums:
  if n%4 == 0:
    baisuu[0] += 1
  elif n%2 == 0:
    baisuu[1] += 1
  else:
    baisuu[2] += 1
   
if baisuu[1] % 2 == 1:
  baisuu[2] += 1
if baisuu[0] >= baisuu[2]-1:
  print("Yes")
else:
  print("No")
  

Measured memory_bytes: 14252
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .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")
}
fn main() {
    let price: u32 = read();
    let yen: u32 = read();
    let ans = if (price % 500) <= yen { "Yes" } else { "No" };
    println!("{}", ans);
}


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

using int32 = int_fast32_t;
using int64 = int_fast64_t;

const int32 INF = 1e9;
const int32 MOD = 1e9+7;
const int64 LLINF = 1e18;

#define YES(n) cout << ((n) ? "YES\n" : "NO\n"  )
#define Yes(n) cout << ((n) ? "Yes\n" : "No\n"  )
#define POSSIBLE cout << ((n) ? "POSSIBLE\n" : "IMPOSSIBLE\n"  )
#define ANS(n) cout << (n) << "\n"
#define REP(i,n) for(int64 i=0;i<(n);++i)
#define FOR(i,a,b) for(int64 i=(a);i<(b);i++)
#define FORR(i,a,b) for(int64 i=(a);i>=(b);i--)
#define ALL(obj) (obj).begin(),(obj).end()
#define pii pair<int32,int32>
#define pll pair<int64,int64>
#define pb(a) push_back(a)

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int32 n;
    cin >> n;
    int32 dsum = 0;
    int32 m = n;
    while(n > 0){
        dsum += n % 10;
        n /= 10;
    }
    Yes(m % dsum == 0);
    return 0;
}

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

using namespace std;
using Graph = vector<vector<int>>;
using Grid= vector<vector<char>>;
using vin= vector<int>;
using ll=long long;
using vll= vector<ll>;
using vbl=vector<bool>;
using vch=vector<char>;
using pnn=pair<int ,int>;

#define ft first
#define sd second
#define fn front
#define pb push_back
#define it insert
#define count ct
#define si(v) int((v).size())
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rell(i,n) for (ll i=0; i< (ll)(n); i++)
#define sot(x) sort(x.begin(), x.end())
#define rese(x) reverse(x.begin(), x.end())
#define vnn(x,y,s,name) vector<vector<int>> name(x, vector<int>(y,s))
#define mse(x) memset(x, 0, sizeof(x))
#define mii(x,y,z) min(x,min(y,z))
#define maa(x,y,z) max(x,max(y,z))

string yes="Yes",no="No";

int main() {
   ll n,k;
   cin>>n>>k;
   vll p(n),c(n);
   rep(i,n){
       cin>>p[i];
       p[i]--;
   }
   rep(i,n) cin>>c[i];
   ll ans=-(1e9);
   rep(i,n){
       ll x=i;
       ll sum=0;
       vll cpx,px;
       while(p[x]!=i){
           px.pb(x);
           sum+=c[p[x]];
           cpx.pb(sum);
           x=p[x];
       }
       px.pb(x);
       sum+=c[p[x]];
       cpx.pb(sum);
       ll len=px.size();
       if(k<len){
           rep(j,k){
               ans=max(ans,cpx[j]);
           }
           continue;
       }
       if(sum<0){
           rep(j,len){
               ans=max(ans,cpx[j]);
           }
           continue;
       }
       ll ansi=sum*((k/len)-1);
       ll lk=k%len;
       rep(j,len){
           ans=max(ans,ansi+cpx[j]);
       }
       ansi+=sum;
       rep(j,lk){
           ans=max(ans,ansi+cpx[j]);
       }
       
   }
   cout<<ans<<endl;
}


Measured memory_bytes: 3840
#define _GLIBCXX_DEBUG
#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 Graph vector<vector<int>>
typedef long long ll;
const int INF = 1000000007;

// #include <boost/multiprecision/cpp_dec_float.hpp>
// #include <boost/multiprecision/cpp_int.hpp>
// namespace mp = boost::multiprecision;
// using Bint = mp::cpp_int;
// using Real = mp::number<mp::cpp_dec_float<1024>>;

int main(){
    int N, M;
    cin >> N >> M;
    Graph G(N);
    rep(i, M){
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    vector<bool> visited(N, false);
    queue<int> que;
    visited[0] = true;

    for(int j : G[0]){
        if(visited[j]) continue;
        visited[j] = true;
        que.push(j);
    }

    while(!que.empty()){
        int v = que.front();
        que.pop();
        for(int j : G[v]){
            visited[j] = true;
        }
    }

    if(visited[N-1]) cout << "POSSIBLE" << endl;
    else cout << "IMPOSSIBLE" << endl;

}

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

int main() {

    map<string, string> predict_pair;
    predict_pair["Sunny"] = "Cloudy";
    predict_pair["Cloudy"] = "Rainy";
    predict_pair["Rainy"] = "Sunny";

    string s;
    cin >> s;
    cout << predict_pair[s] << endl;

    return 0;
}

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

#define fi first
#define se second

const int N = 2020;
const int Q = N * N;
const int mod = 1e9 + 7;

using namespace std;

int pw(int x, int n)
{
        int res = 1;
        for(; n > 0; n >>= 1){
                if(n & 1){
                        res = 1ll * res * x % mod;
                }
                x = 1ll * x * x % mod;
        }
        return res;
}

int fac[Q], inv[Q];

void make()
{
        fac[0] = 1;
        for(int i = 1; i < Q; i++) fac[i] = fac[i - 1] * 1ll * i % mod;
        inv[Q - 1] = pw(fac[Q - 1], mod - 2);
        for(int i = Q - 2; i >= 0; i--) inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
}

int C(int n, int k)
{
        if(k < 0 || k > n) return 0;
        return 1ll * fac[n] * inv[k] % mod * inv[n - k] % mod;
}

void add(int &x, int y)
{
        x += y;
        if(x >= mod){
                x -= mod;
        }
}

int n, k;
int d[N][N];

int main()
{
        ios_base::sync_with_stdio(0);

        //freopen("input.txt", "r", stdin);
        //freopen("output.txt", "w", stdout);

        make();

        cin >> n >> k;
        if(k == 1){
                cout << 1 << "\n";
                return 0;
        }
        d[0][0] = 1;
        for(int i = 0; i <= n; i++){
                for(int j = i; j <= n; j++){
                        if(i > 0)add(d[i][j], d[i - 1][j]);
                        if(j > 0)add(d[i][j], d[i][j - 1] * 1ll * C(j * (k - 1) + i - 1, k - 2) % mod);
                }
        }
        cout << d[n][n] * 1ll * fac[n] % mod << "\n";
}


Measured memory_bytes: 49308
import java.util.Scanner;

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

		while (true) {
			int n = sc.nextInt();
			if (n == 0) {
				break;
			}

			char[] upOrDown = new char[n];
			for (int i = 0; i < n; i++) {
				upOrDown[i] = sc.next().charAt(1);
			}

			int count = 0;
			for (int i = 0; i < n / 2; i++) {
				if (upOrDown[2 * i] == upOrDown[2 * i + 1]) {
					count++;
				}
			}

			System.out.println(count);
		}
		sc.close();
	}
}

Measured memory_bytes: 37288
package main

import (
	"fmt"
)

func main() {
	var n,m int
	fmt.Scan(&n,&m)

	s := make([][]int,m)
	for i:=0; i<m; i++ {
		var k int
		fmt.Scan(&k)
		for j:=0; j<k; j++ {
			var in int
			fmt.Scan(&in)
			s[i] = append(s[i], in)
		}
	}

	p := make([]int,m)
	for i:=0; i<m; i++ {
		fmt.Scan(&p[i])
	}

	ans := 0

	for i:=0; i<(1 << uint64(n)); i++ {
		f := true
		for j:=0; j<m; j++ {
			count := 0
			for _,k := range s[j] {
				if ((1 << uint64(k-1)) & i) == (1 << uint64(k-1)) {
					count++
				}
			}

			if count%2 != p[j] {
				f = false
			}
		}
		if f {
			ans++
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 512
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;

namespace AtCoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            new Program().Solve(new ConsoleInput(Console.In, ' '));
        }

        public void Solve(ConsoleInput cin)
        {
            var a = cin.ReadInt;
            var b = cin.ReadInt;
            if (a <= b)
            {
                for(int i = 1; i <= b; i++)
                {
                    Write(a);
                }
            }
            else
            {
                for (int i = 1; i <= a; i++)
                {
                    Write(b);
                }
            }
        }
    }

    public class ConsoleInput
    {
        private readonly System.IO.TextReader _stream;
        private char _separator = ' ';
        private Queue<string> inputStream;
        public ConsoleInput(System.IO.TextReader stream, char separator = ' ')
        {
            this._separator = separator;
            this._stream = stream;
            inputStream = new Queue<string>();
        }
        public string Read
        {
            get
            {
                if (inputStream.Count != 0) return inputStream.Dequeue();
                string[] tmp = _stream.ReadLine().Split(_separator);
                for (int i = 0; i < tmp.Length; ++i)
                    inputStream.Enqueue(tmp[i]);
                return inputStream.Dequeue();
            }
        }
        public string ReadLine { get { return _stream.ReadLine(); }}
        public int ReadInt { get { return int.Parse(Read); }}
        public long ReadLong { get { return long.Parse(Read); }}
        public double ReadDouble { get { return double.Parse(Read); }}
        public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret;}
        public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret;}
        public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret;}
    }
}

Measured memory_bytes: 13268
#include <stdio.h>
#include <iostream>
#include <fstream>

using std::cin;
using std::cout;
using std::endl;
using std::terminate;

void solve() {
    int n, m; cin >> n >> m;
    int a[n];
    int all = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        all += a[i];
        a[i] *= 4 * m;
    }

    int y = 0;
    for (int i = 0; i < n; ++i) {
        if (a[i] >= all) {
            y++;
        }
    }

    cout << (y >= m ? "Yes" : "No") << endl;
}

int main() {

#ifdef DEV
    std::ifstream in("AtCoder/ABC161/Popular Vote.input");
    cin.rdbuf(in.rdbuf());

    int t; cin >> t;
    for (int x = 1; x <= t; ++x) {
        solve();
    }
#else
    solve();
#endif

    return 0;
}


Measured memory_bytes: 3624
n, x, m = map(int, input().split())
A = [x]
checkA = {x}
ans = x

for i in range(1,n):
    buf = A[i-1]*A[i-1] % m
    if buf in checkA:
        idx = A.index(buf)
        back = len(A) - idx
        nokori = n-len(A)
        sumKurikaeshi = sum(A[idx:])
        ans += int(nokori/back)*sumKurikaeshi
        last = nokori%back
        ans += sum(A[idx:idx+last])
        break
    else:
        A.append(buf)
        checkA.add(buf)
        ans += buf

print(ans)

Measured memory_bytes: 13132
export const Main = function (input: Array<Array<string>>) {
  const N = parseInt(input[0][0]);
  console.log(Math.ceil(0.5 * N) - 1)
}
const parseInput = (input: string) => {
  const lines = input.split("\n");
  if (lines[lines.length - 1] === "") lines.pop();
  return lines.map((el) => (el.split(" ")));
}

Main(parseInput(require("fs").readFileSync("/dev/stdin", "utf8")));


Measured memory_bytes: 7372
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
using namespace std;

int main(){
	int N, M;
	cin >> N >> M;
	vector<int> L(M), R(M);
	for(int i=0;i<M;i++){
		cin >> L[i] >> R[i];
	}
	int left = 0;
	int right = N+1;
	for(int i=0;i<M;i++){
		left = max(left, L[i]);
		right = min(right, R[i]);
	}
	int ans = right - left + 1;
	if(ans <= 0) ans = 0;
	cout << ans << endl;
}

Measured memory_bytes: 1024
n = int(input())
a = list(map(int,input().split()))


minuscount = 0
abss = []
for i in a:
	abss.append(abs(i))
	if (i < 0):
		minuscount += 1

if minuscount % 2 == 0:
	print (sum(abss))
else :
	print (sum(abss) - 2 * min(abss))

Measured memory_bytes: 14284
#include <iostream>
#include <cmath>
using namespace std;
int n,dp[100002],h[100002];

int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>h[i];
	dp[1]=0,dp[2]=abs(h[1]-h[2]);
	for(int i=3;i<=n;i++){
		dp[i]=min(dp[i-2]+abs(h[i]-h[i-2]),dp[i-1]+abs(h[i]-h[i-1]));
	}
	cout<<dp[n]<<endl;
	return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
using namespace std;
const int N=300005,P=1e9+7;
int n,f[N][3][3];
char s[N];
void addx(int&k1,int k2){
	(k1+=k2)>=P&&(k1-=P);
}
int main(){
	scanf("%s",s+1);
	n=strlen(s+1);
	if(n==1){
		puts(s[1]=='0'?"0":"1");
		return 0;
	}
	f[0][0][0]=1;
	rep(i,1,n){
		if(s[i]!='1'){
			rep(j,0,2)rep(k,0,2)addx(f[i][j][k?3-k:1],f[i-1][j][k]);
		}
		if(s[i]!='0'){
			rep(j,0,2)rep(k,0,2)addx(f[i][min(2,j+(k==0))][max(k-1,0)],f[i-1][j][k]);
		}
	}
	int ans=0;
	rep(i,0,2)rep(j,0,2)if(i>=2||j==0)addx(ans,f[n][i][j]);
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 14612
#include <cassert>

#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#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 <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
//#include <boost/foreach.hpp>
//#include <boost/range/algorithm.hpp>
#define rep(i,j,k) for(int i=(int)j;i<(int)k;i++)
#define ll long long
#define Sort(v) sort(all(v))
#define INF 1000000000
#define END return 0
#define pb push_back
#define se second
#define fi first
#define pb push_back
#define all(v) (v).begin() , (v).end()
#define MP make_pair
#define MOD 1000000007LL
using namespace std;
int day[12]={31,28,31,30,31,30,31,31,30,31,30,31};

int main (){
    int q;cin>>q;
    set<int> st;
    rep(i,0,q){
        int a,b;cin>>a>>b;
        if(a==0){
            st.insert(b);
            cout<<st.size()<<endl;
        }else if(a==1){
            cout<<((st.find(b)==st.end())?0:1)<<endl;
        }else {
            st.erase(b);
        }
    }
    
    
}



/*

*/



Measured memory_bytes: 12452
#include <iostream>
#include <array>
#include <algorithm>
#include <vector>
#include <bitset>
#include <set>
#include <unordered_set>
#include <cmath>
#include <complex>
#include <deque>
#include <iterator>
#include <numeric>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <limits>
#include <iomanip>
#include <functional>
#include <cassert>
using namespace std;

using ll=long long;
template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
using vll = V<ll>;
using vvll = V<vll>;
#define rep(i, k, n) for (ll i=k; i<(ll)n; ++i)
#define REP(i, n) rep(i, 0, n)
#define ALL(v) v.begin(),v.end()
template < class T > inline bool chmax(T& a, T b) {if (a < b) { a=b; return true; } return false; }
template < class T > inline bool chmin(T& a, T b) {if (a > b) { a=b; return true; } return false; }
#define DEBUG_VLL(vec) REP(sz, vec.size()) std::cerr<<vec[sz]<<(sz==vec.size()-1?'\n':' ');

const long long MOD = 1000000007;
const long long HIGHINF = (long long)1e18;
const int INF = (int)1e9;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n, x, d; cin >> n >> x >> d;
    if (d == 0) {
        if (x == 0) cout << 1 << '\n';
        else cout << n + 1 << '\n';
    } else {
        map<ll, map<ll, int> > remd;
        remd[0].insert({0, 1}), remd[0].insert({1, -1});
        // k 個選んだ時を全探索
        for (ll k = 1; k <= n; k++) {
            // S が有り得るのは kx + left * d ~ kx + right * d まで
            ll left = k * (k - 1) / 2, right = k * n - (k * (k + 1) / 2);
            ll kxmod = k * x % d, kxdiv = k * x / d;
            if (kxmod < 0) kxmod -= d;
            // d の余りで考えると (kx % mod) + left ~ (kx % mod) + right まで
            // d の他の余りには影響しない (S が有り得るのは間隔が d なので)
            remd[kxmod][kxdiv + left]++, remd[kxmod][kxdiv + right + 1]--;
        }

        ll ans = 0;
        for (P<ll, map<ll, int> > rd: remd) {
            int imos = 0;
            ll li;
            for (P<ll, int> pm: rd.second) {
                if (imos == 0) li = pm.first;
                imos += pm.second;
                if (imos == 0) ans += pm.first - li;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}


Measured memory_bytes: 53584
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <limits.h>
#include <math.h>
#include <functional>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <float.h>
#include <random>

#define repeat(i,n) for (int i = 0; (i) < (n); ++ (i))
#define debug(x) cerr << #x << ": " << x << '\n'
#define debugArray(x,n) for(long long hoge = 0; (hoge) < (n); ++ (hoge)) cerr << #x << "[" << hoge << "]: " << x[hoge] << '\n'
#define debugArrayP(x,n) for(long long hoge = 0; (hoge) < (n); ++ (hoge)) cerr << #x << "[" << hoge << "]: " << x[hoge].first<< " " << x[hoge].second << '\n'

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> Pii;
typedef vector<int> vint;
typedef vector<ll> vll;
const int INF = INT_MAX;
const ll MOD = 1e9+7;

int N,M;
vector<vector<pair<int,ll> > > G;
int color[100010];
ll val[100010];
bool cycle=false;
int dfs(int v,int p,int c){
  ll ret=-1;
  if(color[v]==c)return ret;
  if(color[v]==0)color[v]=c;
  else{
    return v;
  }
  for(pair<int,ll> u:G[v])if(u.first!=p){
    ret = dfs(u.first,v,-c);
    if(ret>=0){
      if(cycle)return ret;
      val[ret] = u.second-val[ret];
      cycle=v==ret;
      return ret;
    }
  }
  return ret;
}

bool used[100010];
ll mi[2]={INF,INF};

bool dfs2(int v,int p){
  used[v]=true;
  if(color[v]!=0){
    mi[(color[v]+1)/2]=min(mi[(color[v]+1)/2],val[v]);
  }
  for(pair<int,ll> u:G[v])if(u.first!=p){
    if(used[u.first]){
      if(val[u.first]!=u.second-val[v])return false;
    }else{
      val[u.first]=u.second-val[v];
      if(!dfs2(u.first,v))return false;
    }
  }
  return true;
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin>>N>>M;
  G.resize(N);
  repeat(i,M){
    int u,v;
    ll s;
    cin>>u>>v>>s;u--;v--;
    G[u].push_back({v,s});
    G[v].push_back({u,s});
  }
  int r = dfs(0,-1,1);
  if(r>=0){
    debug(r);
    debug(val[r]);
    val[r]/=2;
    bool isok = dfs2(r,-1);
    debug(isok);
    if(isok){
      repeat(i,N){
        isok &= val[i]>0;
      }
    }
    cout<<isok<<endl;
  }else{
    bool isok=dfs2(0,-1);
    ll ans=0;
    if(isok){
      ans = max(0ll,mi[0]+mi[1]-1);
    }
    cout<<ans<<endl;
  }
  return 0;
}


Measured memory_bytes: 16896