akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;
using System.Linq;

namespace C
{
    internal class Program
    {
        public static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int[] an = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();

            Dictionary<int, int> dictionary = new Dictionary<int, int>(n);

            foreach (var a in an)
            {
                if (dictionary.ContainsKey(a))
                {
                    dictionary[a]++;
                    continue;
                }
                dictionary.Add(a, 1);
            
            }

            int result = 0;
            foreach (var d in dictionary)
            {
                if (d.Key > d.Value)
                {
                    result += d.Value;
                    continue;
                }
                result += d.Value - d.Key;
            
            }
            Console.WriteLine(result);
        }
    }
}


Measured memory_bytes: 28892
#include <iostream>
#include <iomanip>
#include <ios> 
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
#include <bitset>
#include <map>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define sz(c) ((int)(c).size())

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
//const int MAX=;



int main(){
	int N,M;
	cin>>N>>M;
	int k[12],p[12];
	int s[12][12];
	
	rep(i,M){
		cin>>k[i];
		rep(j,k[i]){
			cin>>s[i][j];
			s[i][j]--;
		}
	}
	rep(i,M)cin>>p[i];
	
	int ans=0;
	rep(b,(1 << N)){
		bool ok=true;
		rep(i,M){
			int ct=0;
			rep(j,k[i]){
				int z=s[i][j];
				if((1 & (b>>z)))ct++;
			}
			if(ct%2!=p[i])ok=false;
		}
		if(ok)ans++;
	}
	
	cout<<ans<<endl;
}

Measured memory_bytes: 256
A, B, K = map(int, input().split())
a = []
if K > (abs(A - B) / 2):
    for i in range(A, B + 1):
        a.append(i)
else:
    for i in range(K):
        a.append(A + i)
        a.append(B - i)
        
a.sort()
for i in range(len(a)):
    print(a[i])


Measured memory_bytes: 3060
temp=input().split()
H=int(temp[0])
W=int(temp[1])

INF=10000000000
ans=INF
#超特殊例
if H%3==0 or W%3==0:
	ans=0
ans=min(ans,H,W)
#横長がある場合
for i in range(H):
	S1=W*i
	S2=int(W/2)*(H-i)
	S3=(W-int(W/2))*(H-i)
	if max(S1,S2,S3)-min(S1,S2,S3)<ans:
		ans=max(S1,S2,S3)-min(S1,S2,S3)
for i in range(W):
	S1=H*i
	S2=int(H/2)*(W-i)
	S3=(H-int(H/2))*(W-i)
	if max(S1,S2,S3)-min(S1,S2,S3)<ans:
		ans=max(S1,S2,S3)-min(S1,S2,S3)
print(ans)

Measured memory_bytes: 3064
n,i,j,u,v=1,a[2][3];long d[1<<25];s(){for(i=n;i;)d[i]=i--;for(;i<=n;++i)for(j=0;j<3;++j)a[v][j]>a[u][j]&&i>=a[u][j]&&(d[i]=fmax(d[i],d[i-a[u][j]]+a[v][j]));}main(){for(scanf("%d",&n);i<2;i++)for(j=0;j<3;)scanf("%d",a[i]+j++);s(),n=d[n],u=1,v=0,s();printf("%lld\n",d[n]);}

Measured memory_bytes: 196736
from enum import Enum
from queue import Queue

import numpy as np

import collections
import bisect
import sys
import math

from scipy.sparse.csgraph import floyd_warshall

S = input()
ans = True
for i in range(len(S)):
    if i % 2 == 0:#iが奇数の時
        if S[i] == 'L':
            ans = False
            break
    else:#iが偶数の時
        if S[i] == 'R':
            ans = False
            break

if ans:
    print('Yes')
else:
    print('No')

            


Measured memory_bytes: 13816
import java.util.Scanner;

public class Main{
	public static void main(String[] args)
	{
		Scanner sc =new Scanner(System.in);
		int a=sc.nextInt();
		int b=sc.nextInt();
		int time=a+b;
		
		if(time>=24) time-=24;
		System.out.println(time);
	}
} 

Measured memory_bytes: 21716
import java.util.*;

public class Main {

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

		int k = sc.nextInt();
		
		if(k % 2 == 0) {
			System.out.println((int)Math.pow(k/2, 2)); 
		} else {
			System.out.println((k/2)*(k+1)/2);
		}
	}
}


Measured memory_bytes: 21204
import math

a,b,angle=map(str,input().split())
a=float(a)
b=float(b)
angle=int(angle)

S=a*b*math.sin(math.radians(angle))/2
c=math.sqrt(a**2+b**2-2*a*b*math.cos(math.radians(angle)))
print(S)
print(a+b+c)
print(2*S/a)


Measured memory_bytes: 5712
# -*- coding: utf-8 -*-
#AGC012A
import sys
import collections

n= int(input())
tmp = input().split()
a = list(map(lambda a: int(a), tmp))

#print(a)
a.sort()
#print(a)

total=0
for i in range(n,3*n-1,2):
	total+=a[i]
print(total)


Measured memory_bytes: 37468
import java.util.*;

class Main{
  public static void main(String args[]){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    Map<String,Integer> mp = new HashMap<>();
    for(int i=0;i<n;i++){
      String s = sc.next();
      mp.put(s,mp.getOrDefault(s,0)+1);
    }
    int m = sc.nextInt();
    for(int i=0;i<m;i++){
      String s = sc.next();
      if(mp.containsKey(s)){
        mp.put(s,mp.get(s)-1);
      }
    }
    Iterator<Integer> itr = (mp.values().iterator());
    int max = 0;
    while(itr.hasNext()){
      max = Math.max(itr.next(),max);
    }
    System.out.println(max);
  }
}

Measured memory_bytes: 21716
#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <set>
#include <algorithm>
#include <unordered_map>
#include <queue>
#include <iomanip>
#include <map>
#include <utility>
#include <numeric>
#include <chrono>
#include <ctime>
#include <bitset>
#include <iterator>

#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define P pair<long long, long long>
#define debug(x) cerr << #x << ": " << x << ", "
#define debugln(x) cerr << #x << ": " << x << '\n'

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

using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;

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

  string s; cin >> s;
  int n = s.size();

  for(int k=0; k<8; k++) {
    string tmp;
    for(int i=0; i<n; i++) {
      if (k <= i && i <= k+(n-8)) continue;
      tmp.push_back(s[i]);
    }
    if (tmp == "keyence") {
      cout << "YES" << endl;
      return 0;
    }
  }

  cout << "NO" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <climits>
#include <utility>
typedef long long ll;
using namespace std;

vector<ll> a, b, sa, sb;

int binarySearch(ll key) {
  int left = -1;
  int right = (int)sb.size();

  while (right-left>1) {
    int mid = left + (right-left) / 2;

    if (sb[mid]<=key) left = mid;
    else right = mid;
  }

  return left;
}

int main(int argc, char *argv[]) {
  int n, m, i;
  ll k;

  cin >> n >> m >> k;
  
  a.resize(n);
  sa.resize(n+1);
  b.resize(m);
  sb.resize(m+1);

  sa[0] = 0LL;
  sb[0] = 0LL;
  for(i=0;i<n;i++){
    cin >> a[i];
    sa[i+1] = sa[i] + a[i];
  }
  for(i=0;i<m;i++){
    cin >> b[i];
    sb[i+1] = sb[i] + b[i];
  }
  
  int ans = 0, tmp;
  for(i=0;i<=n;i++){
    if(sa[i]>k) continue;
    else{
      tmp = i + binarySearch(k-sa[i]);
      if(tmp>ans) ans = tmp;
    }
  }

  cout << ans << endl;

  return 0;
}


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

int main(){
  int N,C,K;
  cin>>N>>C>>K;
  vector<int> Ti(N);

  for(int i=0;i<N;i++){
    cin>>Ti[i];
    Ti[i]+=K;
  }
  sort(Ti.begin(),Ti.end());

  int ans = 0;
  
  for(int i=0;i<N;){
    int j,c=0;
    for(j=0;j<C&&Ti[i]+K>=Ti[i+j];j++)
      if(Ti[i]+K>=Ti[i+j])
	c++;
    ans++;
    i+=c;
  }
  cout<<ans<<endl;
  
  return 0;
}


Measured memory_bytes: 768
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1000000007;
int n,k;
int a[2005];
int f(int x){
	return x*(x+1)/2%mod;
}
signed main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>a[i];
	int ans=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(a[i]>a[j]){
				ans=ans+f(k-1+(i<j));
				ans%=mod; 
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i,k,n)  for(int i = (k);i < (n);++i)
#define REP(i,n)    FOR(i,0,n)
#define ALL(x)      begin(x),end(x)

using namespace std;
using vecint = vector<int>;
using ll = int64_t;
constexpr ll MOD = 1000003;

// a^-1 mod p
ll inv(ll a,ll p){
  return ( a == 1 ? 1 : (1 - p*inv(p%a,a)) / a + p );
}

ll powmod(ll x, ll i) {
  if (i == 0) return 1;
  if ((i % 2) == 1) return (x * powmod(x, i-1)) % MOD;
  ll h = powmod(x, i/2);
  return (h * h) % MOD;
}

int main()
{
  int q;
  cin>>q;
  vector<ll> fact(MOD);
  vector<ll> factinv(MOD);
  fact[0] = factinv[0] = 1;
  REP(i,MOD-1) {
    fact[i+1] = fact[i] * (i+1);
    fact[i+1] %= MOD;
    factinv[i+1] = inv(fact[i+1], MOD);
  }
  REP(task,q) {
    ll x,d,n;
    cin>>x>>d>>n;
    if (x == 0) {
      cout << 0 << endl;
    } else if (d == 0) {
      cout << powmod(x, n) << endl;
    } else {
      ll y = (x * inv(d, MOD)) % MOD;
      if (y+n-1 < MOD) {
        ll res = powmod(d, n);
        res *= fact[y+n-1];
        res %= MOD;
        res *= factinv[y-1];
        res %= MOD;
        cout << res << endl;
      } else {
        cout << 0 << endl;
      }
    }
  }
  return 0;
}


Measured memory_bytes: 16512
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws IOException {
		new Main().run();
	}

	private void run() throws IOException {
		Scanner scanner = new Scanner(System.in);
		while (true) {
			int w = scanner.nextInt();
			int h = scanner.nextInt();
			if ((w | h) == 0)
				break;
			list = new ArrayList<List<Pair>>();
			for (int i = 0; i < 6; i++) {
				list.add(new ArrayList<Pair>());
			}
			boolean[] b = new boolean[6];
			for (int i = 0; i < h; i++) {
				char[] cs = scanner.next().toCharArray();
				for (int j = 0; j < w; j++) {
					if (cs[j] == 'S') {
						sy = i;
						sx = j;
					} else if (cs[j] == 'G') {
						gy = i;
						gx = j;
					} else if (cs[j] != '.') {
						int c = Character.getNumericValue(cs[j]);
						list.get(c).add(new Pair(i, j));
						b[c] = true;
					}
				}
			}
			int sum = 0;
			for (int i = 1; i < 6; i++) {
				if (b[i])
					sum++;
			}
			min = Integer.MAX_VALUE;
			int index = -1;
			for (int i = 1; i < 6; i++) {
				int cos = slove(i, i == 1 ? 5 : i - 1);
				if (min > cos) {
					min = cos;
					index = i;
				}
			}
			System.out.println(index == -1 ? "NA" : index + " " + min);

		}

	}

	private int slove(int k, int g) {
		PriorityQueue<Pair> pq = new PriorityQueue<Pair>();
		int s = k == 5 ? 1 : k + 1;
		for (int i = 0; i < list.get(s).size(); i++) {
			int y = list.get(s).get(i).y;
			int x = list.get(s).get(i).x;
			int dis = Math.abs(y - sy) + Math.abs(x - sx);
			int gdis = Math.abs(y - gy) + Math.abs(x - gx);
			pq.add(new Pair(y, x, dis, k + 1, dis + gdis));
		}
		while (!pq.isEmpty()) {
			Pair pair = pq.poll();
			int y = pair.y;
			int x = pair.x;
			int cost = pair.cost;
			int id = pair.id;
			int tmpid = id > 5 ? id - 5 : id;
			if (id == 10) {
				return cost;
			}
			if (tmpid != g) {
				for (Pair i : list.get(tmpid == 5 ? 1 : tmpid + 1)) {
					int dis = Math.abs(y - i.y) + Math.abs(x - i.x);
					int gdis = Math.abs(i.y - gy) + Math.abs(i.x - gx);
					pq.add(new Pair(i.y, i.x, cost + dis, id + 1, cost + dis
							+ gdis));
				}
			} else {
				int dis = Math.abs(y - gy) + Math.abs(x - gx);
				pq.add(new Pair(0, 0, cost + dis, 10, cost));
			}
		}
		return Integer.MAX_VALUE;
	}

	List<List<Pair>> list;
	int sy;
	int gy;
	int sx;
	int gx;
	int min;

	class Pair implements Comparable<Pair> {
		int y;
		int x;
		int cost;
		int id;
		int md;

		@Override
		public int compareTo(Pair o) {
			if (this.md == o.md)
				return o.id - this.id;
			return this.md - o.md;
		}

		public Pair(int y, int x) {
			super();
			this.y = y;
			this.x = x;
		}

		public Pair(int y, int x, int cost, int id, int md) {
			super();
			this.y = y;
			this.x = x;
			this.cost = cost;
			this.md = md;
			this.id = id;
		}

	}
}

Measured memory_bytes: 103208
#include <functional>
#include <list>
#include <string>
#include <vector>
#include <climits>
#include <cstring>
#include <map>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <set>
#include <deque>
#include <stack>
#include <cassert>
using namespace std;
#define FOR(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define ALL(x) (x).begin(),(x).end()
#define CASET2 int ___T, case_n = 1; scanf("%d ", &___T); while ((___T > 0 ? printf("Case #%d:\n", case_n++) : 0), ___T-- > 0)
#define CASET1 int ___T, case_n = 1; scanf("%d ", &___T); while ((___T > 0 ? printf("Case #%d: ", case_n++) : 0), ___T-- > 0)
#define CASET int ___T; scanf("%d ", &___T); while (___T-- > 0)
#define SZ(X) ((int)(X).size())
#define LEN(X) strlen(X)
#define REP(i,n) for(int i=0;i<int(n);i++)
#define REP1(i,a,b) for(int i=(a);i<=int(b);i++)
#define PER1(i,a,b) for(int i=(a);i>=(b);i--)
#define REPL(i,x) for(int i=0;x[i];i++)
#define PER(i,n) for(int i=(n)-1;i>=0;i--)
#define RI1(x) scanf("%d",&x)
#define RI2(x,y) RI1(x), RI1(y)
#define RI3(x,y...) RI1(x), RI2(y)
#define RI4(x,y...) RI1(x), RI3(y)
#define RI5(x,y...) RI1(x), RI4(y)
#define RI6(x,y...) RI1(x), RI5(y)
#define GET_MACRO(_1, _2, _3, _4, _5, _6, NAME, ...) NAME
#define RI(argv...) GET_MACRO(argv, RI6, RI5, RI4, RI3, RI2, RI1)(argv)
#define DRI(argv...) int argv;RI(argv)
#define WRI(argv...) while (RI(argv) != EOF)
#define DWRI(x...) int x; WRI(x)
#define RS(x) scanf("%s",x)
#define MP make_pair
#define PB push_back
#define MS0(x) memset(x,0,sizeof(x))
#define MS1(x) memset(x,-1,sizeof(x))
#define X first
#define Y second
#define V(x) vector<x >

typedef long double LD;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef long long LL;
const int INF = 1000000000;

void print(int i) { printf("%d", i); }
void print(LL i);
template<class T> void PI(T i) { print(i); puts(""); }
template<class T> void PIS(T i) { print(i); printf(" "); }

template<class T>
void PV(T const &v, int N) {
    REP(i, N) {
        print(v[i]);
        printf("%c", i == N-1 ? '\n' : ' ');
    }
}

template<class T> void PV(T const &v) { PV(v, SZ(v)); }

template<class T, class S> bool has_bit(T mask, S i) { return (mask >> i) & 1; }
long long shift(int i) { return 1ll << i; }

template<class C> void mini(C&a4, C b4){a4=min(a4, b4); }
template<class C> void maxi(C&a4, C b4){a4=max(a4, b4); }
int popcount(int x) { return __builtin_popcount(x); } 
int popcount(long long x) { return __builtin_popcountll(x); } 

#include <unordered_set>
#include <unordered_map>
#define EB emplace_back
#define RL(x) scanf("%lld", &(x))
#define PL(x) printf("%lld\n", x)
#define DRL(x) LL x; RL(x)

int main() {
  DRI(N);
  VI A(N), B;
  LL sum = 0;
  REP(i, N) {
    RI(A[i]);
    if (i) {
      B.PB(A[i] - A[i-1]);
    }
    sum += A[i];
  }
  B.PB(A[0] - A[N-1]);
  LL g = (N + 1ll) * N / 2;
  if (sum % g != 0) {
    puts("NO");
    return 0;
  }
  LL x = sum / g;
  // a + b = x, a - (N-1)b = B
  for (int BB : B) {
    if ((x - BB) % N || (x - BB) / N < 0 || (x - BB) / N > x) {
      puts("NO");
      return 0;
    }
  }
  puts("YES");
  return 0;
}


Measured memory_bytes: 1276
#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <numeric>
#include <set>

using namespace std;
struct aaa{aaa(){cin.tie(nullptr); ios::sync_with_stdio(false); cout<<fixed<<setprecision(20);};}aaa;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v){o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
#define debug(v) {cerr<<"\033[1;36m[debug]\033[m "<<#v<<" : "<<v<<endl;}

using int64 = long long;

int main() {
    int x,a,b;
    cin >> x >> a >> b;
    if (abs(a - x) < abs(b - x))
        cout << "A" << endl;
    else
        cout << "B" << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(),(a).end()
#define SZ(a) (int)(a).size()
#define FOR(i, a, b) for(int i=(a); i<=(b); ++i)
#define iFOR(i, a, b) for(int i=(a); i>=(b); --i)
#define make_unique(a) sort(all((a))), (a).resize(unique(all((a)))-(a).begin())

using namespace std;

typedef pair<int,int> PII;
typedef long long LL;
typedef double DD;
typedef long double LD;
typedef pair<LL,LL> PLL;
typedef pair<DD,DD> PDD;
typedef vector<int> VI;
typedef vector<LL> VL;

const int N=203;
LL num[N];
char player[N];
int n;
LL gelim[N][62];
void print(LL a){
    iFOR(i, 59, 0){
        if( (1ll<<i)&a ) printf("%d ",i);
    }
    printf("\n");
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        memset(gelim, 0, sizeof gelim);
        scanf("%d",&n);   
        FOR(i, 1, n) scanf("%lld",&num[i]);
        scanf(" %s",player+1);
        if(player[n] != '0'){
            printf("1\n"); continue;
        }
        int ch = 1;
        iFOR(i, n, 1){
            FOR(j, 0, 59) gelim[i][j] = gelim[i+1][j];
            iFOR(j, 59, 0){
                if( (1ll<<j)&num[i] ) num[i] ^= gelim[i][j];
            }
            if(player[i]!='0'){
                if(num[i]){
                    ch = 0; break;
                }
            }else{
                iFOR(j, 59, 0){
                    if((1ll<<j)&num[i]){
                        gelim[i][j] = num[i];
                        break;
                    }
                }
            }
        }
        if(ch) printf("0\n");
        else printf("1\n");
    }
	return 0;
}
/*
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 */


Measured memory_bytes: 3760
from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))

mod = 10**9 + 7
memo = defaultdict(int)
base = 0
for i in a:
    base = (base+pow(i, mod-2, mod))%mod
    num = i
    c = 0
    while num%2==0:
        c += 1
        num //= 2
    memo[2] = max(memo[2], c)
    for j in range(3, int(i**.5)+1, 2):
        if num%j==0:
            c = 0
            while num%j==0:
                num //= j
                c += 1
            memo[j] = max(memo[j], c)
    if num != 1:
        memo[num] = max(memo[num], 1)
k = 1
for s, t in memo.items():
    k = (k*pow(s, t, mod))%mod

print((k*base)%mod)

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

int main() {
  int N;
  cin >> N;
  vector<int> moti(N);
  rep(i, N) {
    cin >> moti.at(i);
  }
  int tmp = 0;
  
  sort(moti.begin(), moti.end());
  
  int ans = 1;
  rep(i, N-1) {
    if (moti.at(i) != moti.at(i+1)) {
      ans++;
    }
  }
  
  cout << ans << endl;
}


Measured memory_bytes: 256
import math
n=input()
mod = int(1e9) + 7
a=list(map(int,raw_input().split()))
if(len(a)%2==0 and a.count(0)>0):
    print(0)
elif(len(a)%2!=0 and a.count(0)>1):
    print(0)
else:    
    l=[0]*n
    b=set(a)
    for i in a:
        l[i] +=1
    for i in range(1,len(a)):
        if(l[i]%2==1):
            print(0)
            exit()
    if(a.count(0)):
        print(pow(2,len(b)-1,mod))
    else:
        print(pow(2,len(b),mod))      
            
        

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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N;
  cin >> N;
  int ans = 0;
  float tmp = log(N) / log(3);
  ans = ceil(tmp);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3448
#include <bits/stdc++.h>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
#include <iostream>
#include <bitset>
#include <cassert>
#include <queue>
#include <random>
#include <stack>
#include <iomanip>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)n; i++)
#define repf(i, a, b) for (ll i = (ll)a; i < (ll)b; i++)
#define repr(i, a, b) for (ll i = (ll)a; i > (ll)b; i--)
#define repv(x, arr) for (auto &x : arr)
#define all(v) (v).begin(), (v).end()
#define vec(name, num) vector<ll> name((num), 0);
#define mp(a, b) make_pair(a, b)
#define op(i) cout << (i) << endl;
#define F first
#define S second
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vii;
typedef vector<vii> vvii;
const ll mod = 1e9 + 7;
const int infi = 2147483600;
const ll infl = 1e17;



int main()
{
    ll w, h;
    cin >> w >> h;
    vector<ll> p(w), q(h);
    rep(i, w) cin >> p[i];
    rep(i, h) cin >> q[i];
    sort(all(p));
    sort(all(q));
    ll noww = w+1, nowh = h+1;
    ll cnt = w + h;
    ll pidx = 0, qidx = 0;
    ll ans = 0;
    while (cnt>0){
        if (pidx==w){
            ans += noww * q[qidx];
            qidx++;
            cnt--;
            nowh--;
        }
        else if (qidx==h){
            ans += nowh * p[pidx];
            pidx++;
            cnt--;
            noww--;
        }
        else {
            if (p[pidx]<q[qidx]){
                ans += nowh * p[pidx];
                pidx++;
                cnt--;
                noww--;
            }
            else if (p[pidx]>q[qidx]){
                ans += noww * q[qidx];
                qidx++;
                cnt--;
                nowh--;
            }
            else{
                if (noww<=nowh){
                    ans += noww * q[qidx];
                    qidx++;
                    cnt--;
                    nowh--;
                }
                else
                {
                    ans += nowh * p[pidx];
                    pidx++;
                    cnt--;
                    noww--;
                }
            }
        }

    }
    cout << ans << endl;
}


Measured memory_bytes: 1792
#include<iostream>
using namespace std;
int main(){
	long n,k;
  	long Sum=0,Sum_2=0;
  	cin>>n>>k;
  	for(int i=1;i<=n;i++){
  	    // k lẽ thì kiểm tra coi có h nào + nó = bội củ k
  	    // vd 3%2 = 1 == k/2 => 3+1 % k == 0
    	if(!(k%2))
    	    if(i%k == k/2) Sum_2++;
        // Bội của k 
        Sum+=(i%k ? 0 : 1 );
    }
  	cout<<Sum*Sum*Sum + Sum_2*Sum_2*Sum_2;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
#define PI acos(-1)
#define sz 18500000
#define RUN_FAST ios::sync_with_stdio(false);
using namespace std;

int main()
{
    RUN_FAST; cin.tie(nullptr);
    int a, b;
    string s1, s2;
    char ch1, ch2;
    cin >> a >> b;
    ch1=a+48; ch2=b+48;
    s1=s2="";
    while (a--) s1+=ch2;
    while (b--) s2+=ch1;
    stringstream ss;
    ss << s1;
    ss >> a;
    ss.clear();
    ss << s2;
    ss >> b;
    cout << max(a, b) << endl;
    return 0;
}


Measured memory_bytes: 3512
#include "bits/stdc++.h"
#define ll long long
#define rep2(i,a,b) for(ll i=a;i<=b;++i)
#define rep(i,n) for(int i=0;i<n;i++)
#define rep3(i,a,b) for(int i=a;i>=b;i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define tii tuple<int,int,int>
#define pq priority_queue<int>
#define pqg priority_queue<int,vector<int>,greater<int>>
#define pb push_back
#define edge(v,a,b) v[a].pb(b);v[b].pb(a);
ll MOD=1e9+7;
#define INF 1e9+7
#define N 1000010
#define MAX_V 400010
#define vec vector<int>
#define ALL(c) (c).begin(),(c).end()

int in() {int x;scanf("%d",&x);return x;}
ll lin() {ll x;scanf("%lld",&x);return x;}
using namespace std;
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
#define umap unordered_map<ll,int,custom_hash>
struct pair_hash
{
    template<class T1,class T2>
    size_t operator() (const pair<T1,T2> &p)const{
        return hash<T1>()(p.first)^hash<T2>()(p.second);
    }
};


main(){
    int n;
    int a[N];
    cin>>n;
    rep(i,n)a[i]=in();
    int sum=0;
    rep(i,n)sum+=a[i];
    int d=INF;
    int ans=-1;
    rep(i,n){
        if(abs(sum-a[i]*n)<d){
            ans=i;
            d=abs(sum-a[i]*n);
        }
    }
    cout<<ans;
}




Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const long double PI = acos(-1);
typedef long long ll;
typedef pair<int64_t,int64_t> pll;
int dx[]={1,-1,0,0,1,-1,1,-1};
int dy[]={0,0,1,-1,1,-1,-1,1};
#define INF (2147483647)
#define mod (1000000007)
#define limit (7368791)
#define rep(i,a,b) for (int64_t i = (a); i < (b); i++)
#define REP(i,n) rep(i,0,n)
#define ALL(a) begin(a),end(a)
#define sz(s) (s).size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second


void solve()
{
    int n;cin>>n;
    
    vector<vector<int> >dp(n,vector<int>(3,0));REP(i,3)cin>>dp[0][i];
    rep(i,1,n)
    {
        int abc[3];REP(i,3)cin>>abc[i];
        REP(j,3)
            rep(k,j+1,j+3)
                dp[i][j]=max(dp[i][j],dp[i-1][k%3]+abc[j]);
    }
    int ans=0;
    REP(i,3)ans=max(ans,dp[n-1][i]);
    cout<<ans<<endl;
}

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

Measured memory_bytes: 5760
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<string>

#define all(c) (c).begin(),(c).end()

using namespace std;

int main(void){

  set<string>S;
  string str="AIDUNYAN";

  sort(all(str));

  do{
    S.insert(str);
  }while(next_permutation(all(str)));

  cin >> str;
  for(int i=0;i+7<str.size();i++){
    if(S.count(str.substr(i,8))){
      str=str.substr(0,i)+"AIZUNYAN"+str.substr(i+8,str.size()-8);
      i+=7;
    }
  }

  cout << str << endl;

  return 0;
}

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

struct color_data{
    int color[2], number;
};

vector<vector<int>> roads[2];
vector<int> colors[2];

void fill_color(int now, int color, bool if_railway){
    colors[if_railway][now] = color;
    for(int i = 0; i < roads[if_railway][now].size(); i++){
        if(colors[if_railway][roads[if_railway][now][i]] == -1){
            fill_color(roads[if_railway][now][i], color, if_railway);
        }
    }
}

int main(){
    int N, K, L;
    cin >> N >> K >> L;
    roads[0].resize(N);
    roads[1].resize(N);
    for(int i = 0; i < K; i++){
        int start, goal;
        cin >> start >> goal;
        roads[0][start - 1].push_back(goal - 1);
        roads[0][goal - 1].push_back(start - 1);
    }
    for(int i = 0; i < L; i++){
        int start, goal;
        cin >> start >> goal;
        roads[1][start - 1].push_back(goal - 1);
        roads[1][goal - 1].push_back(start - 1);
    }
    for(int i = 0; i < 2; i++){
        colors[i].resize(N);
        fill(colors[i].begin(), colors[i].end(), -1);
        int color = 0;
        for(int j = 0; j < N; j++){
            if(colors[i][j] == -1){
                fill_color(j, color, i);
                color++;
            }
        }
    }
    map<pair<int, int>, vector<int>> color_pattern;
    for(int i = 0; i < N; i++){
        color_pattern[{colors[0][i], colors[1][i]}].push_back(i);
    }
    int ans[N];
    for(auto i: color_pattern){
        for(int j = 0; j < i.second.size(); j++){
            ans[i.second[j]] = int(i.second.size());
        }
    }
    string ans_string = "";
    for(int i = 0; i < N; i++){
        ans_string += to_string(ans[i]) + " ";
    }
    ans_string.pop_back();
    cout << ans_string << endl;
}


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

#define ll long long int
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define mt make_tuple
#define all(A) A.begin(), A.end()
#define sz(A) (int)A.size()
typedef vector <int> vi;
typedef vector <ll> vl;
typedef pair <int, int> pii;
typedef tuple <int, int, int> tii;
const ll mod = 1e9 + 7;
//const ll mod = 998244353;
const int inf = 1e9;
//const ll inf = 1e18;
const int N = 2e5;

ll power (ll n, ll k) {
	ll res = 1;
	while (k != 0) {
		if (k & 1) 
			res = (res * n) % mod;
		n = (n * n) % mod;
		k /= 2;
	}
	return res;
}

void solve () {
	int n, k;
	cin >> n >> k;
	ll a[n];
	vector <pair<ll, ll>> v; 
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		if (a[i] >= 0) {
			v.pb(mp(a[i], 0));
		}
		else {
			v.pb(mp(-a[i], 1));
			cnt++;
		}
	}
	ll mul = 1;
	if (cnt == n) {
		if (k & 1) sort(all(v));
		else sort(all(v), greater <pair <ll, ll>>());
		for (int i = 0; i < k; i++) {
			mul = (mul * v[i].fi) % mod;
			if (v[i].se) 
				mul = (mod - mul) % mod;
		}
		cout << mul << "\n";
		return;
	}
	if (n == k) {
		for (int i = 0; i < k; i++) {
			mul = (mul * v[i].fi) % mod;
			if (v[i].se) 
				mul = (mod - mul) % mod;
		}
		cout << mul << "\n";
		return;
	}
	sort(all(v), greater<pair<ll, ll>>());
	cnt = 0;
	for (int i = 0; i < k; i++) {
		mul = (mul * v[i].fi) % mod;
		if (v[i].se) 
			cnt++;
	}
	ll x, y;
	if (cnt & 1) {
		x = -1;
		for (int i = k - 1; i >= 0; i--) {
			if (v[i].se == 0) {
				x = v[i].fi;
				break;
			}
		}
		y = -1;
		for (ll i = k - 1; i >= 0; i--) {
			if (v[i].se == 1) {
				y = v[i].fi;
				break;
			}
		}
		if (x == -1) {
			mul = (mul * power(y, mod - 2)) % mod;
			for (int i = k; i < n; i++) {
				if (v[i].se == 0) {
					mul = (mul * v[i].fi) % mod;
					break;
				}
			}
		}
		else {
			ll p = -1, q = -1;
			for (int i = k; i < n; i++) {
				if (v[i].se == 0) {
					p = v[i].fi;
					break;
				}
			}
			for (int i = k; i < n; i++) {
				if (v[i].se == 1) {
					q = v[i].fi;
					break;
				}
			}
			if (q == -1) {
				mul = (mul * power(y, mod - 2)) % mod;
				mul = (mul * p) % mod;
			}
			else if (p == -1) {
				mul = (mul * power(x, mod - 2)) % mod;
				mul = (mul * q) % mod;
			}
			else if (q * y > p * x) {
				mul = (mul * power(x, mod - 2)) % mod;
				mul = (mul * q) % mod;
			}
			else {
				mul = (mul * power(y, mod - 2)) % mod;
				mul = (mul * p) % mod;
			}
		}
	}
	cout << mul << "\n";
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
  #endif
	int t = 1;
	while (t--) {
		solve();
	}
 	return 0;
}

Measured memory_bytes: 8488
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5,M=1e6+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a) memset(a,0,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first 
#define se second
ll a[N];
int main(){
	int n,k;
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;i++) scanf("%lld",&a[i]);
	sort(a,a+n);
	int l=0,r=n-1,w=1; 
	ll ans=1;
	if(k&1) ans=a[r--],k--,w=(ans<0?-1:1);
	while(k){
		ll x=a[l]*a[l+1],y=a[r]*a[r-1];
		if(x*w>y*w) ans=(ans*(x%mod))%mod,l+=2;
		else ans=(ans*(y%mod))%mod,r-=2;
		k-=2;
	}
	printf("%lld\n",(ans%mod+mod)%mod);
	return 0;
}


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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)    FOR (i,0,n)
#define ALL(f,x,...) ([&](decltype((x)) ALL) {                          \
            return (f)(begin(ALL), end(ALL), ## __VA_ARGS__); })(x)

using namespace std;

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

    if (999 < N) cout << "ABD" << endl;
    else cout << "ABC" << endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
char s[60][60];
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	cin>>s[i][j];
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			int ans=0;
			if(s[i][j]=='#'){
				cout<<'#';
				continue; 
			}
			if(s[i+1][j]=='#')ans++;
			if(s[i-1][j]=='#')ans++;
			if(s[i][j+1]=='#')ans++;
			if(s[i][j-1]=='#')ans++;
			if(s[i+1][j-1]=='#')ans++;
			if(s[i+1][j+1]=='#')ans++;			
			if(s[i-1][j+1]=='#')ans++;			
			if(s[i-1][j-1]=='#')ans++;	
			cout<<ans;		
		}
		cout<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cmath>

using namespace std;

int main()
{
	int x0, y0, x1, y1, q, x2, y2;
	scanf("%d %d %d %d", &x0, &y0, &x1, &y1);
	scanf("%d", &q);
	for (int i = 0; i < q; i++)
	{
		scanf("%d %d", &x2, &y2);
		double x, y;
		x = (double)x0 + 1.0*(x1-x0)*((x1 - x0)*(x2 - x0) + (y1 - y0)*(y2 - y0)) / (pow(x1 - x0, 2) + pow(y1 - y0, 2));
		y = (double)y0 + 1.0*(y1-y0)*((x1 - x0)*(x2 - x0) + (y1 - y0)*(y2 - y0)) / (pow(x1 - x0, 2) + pow(y1 - y0, 2));
		double xr, yr;
		xr = 2 * x - x2;
		yr = 2 * y - y2;
		printf("%.10lf %.10lf\n", xr, yr);
	}
	return 0;
}

Measured memory_bytes: 1068
from collections import defaultdict
n,k,q = map(int,input().split())
l = [int(input()) for _ in range(q)] #複数行1文字をintでリストに
d = defaultdict(int)
for i in l:
    if i in d:
        d[i] += 1
    else:
      d[i]=1

for i in range(1,n+1):
    a = q-d[i]
    b = k-a
    if b >0:
        print("Yes")
    else:
        print("No")

Measured memory_bytes: 20124
#include<stdio.h>
#include<stdlib.h>
long long map[100005]={};
int main()
{
	long long ans=0,n,a,b;
	scanf("%lld %lld %lld",&n,&a,&b);
	for(int i=1;i<=n;i++)
		scanf("%lld",&map[i]);
	for(int i=1;i<n;i++){
		if((map[i+1]-map[i])*a<b) ans+=(map[i+1]-map[i])*a;
		else ans+=b;
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 896
import math
from  fractions import gcd

def lcm(a,b):
    return (a*b)//gcd(a,b)

A,B,C,D = map(int,input().split())
d_cnt = B//D-(A-1)//D
c_cnt = B//C-(A-1)//C
cd = lcm(C,D)
cd_cnt = B//cd-(A-1)//cd
print(B-A+1-(c_cnt+d_cnt-cd_cnt))



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

using namespace std;

#define debug(n) cerr << #n << ':' << n << endl;
#define dline    cerr << __LINE__ << endl;

using ll = long long;
using ull = unsigned long long;
template<class T, class U> using P = pair<T,U>;
template<class T> using Heap = priority_queue<T>;
template<class T> using heaP = priority_queue<T,vector<T>,greater<T>>;
template<class T,class U> using umap = unordered_map<T,U>;
template<class T> using uset = unordered_set<T>;

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

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

template<class T, size_t N, class U>
void Fill(T (&a)[N], const U&v){
    fill((U*)a,(U*)(a+N),v);
}

template<class T>
istream& operator >> (istream&is, vector<T>&v){
  for(auto&e:v)is >> e;
  return is;
}

int main(){
  int n,m; cin >> n >> m;n++;
  string s; cin >> s;
  reverse(s.begin(),s.end());
  vector<int> step;
  vector<int> idx;
  vector<int> dist;
  step.push_back(0);
  idx.push_back(0);
  dist.push_back(0);
  for(int i = 1; i < n; ++i){
    if(s[i] == '1')continue;
    if(i - idx.back() > m){
      cout << -1 << endl;
      return 0;
    }
    if(step.back() == 0){
      step.push_back(1);
      dist.push_back(i);
      idx.push_back(i);
      continue;
    }
    auto it = lower_bound(step.begin(),step.end(),step.back());
    int j = it - step.begin() - 1;
    if(i-idx[j] > m){
      step.push_back(step.back()+1);
      dist.push_back(i-idx.back());
    } else {
      step.push_back(step.back());
      dist.push_back(i-idx[j]);
    }
    idx.push_back(i);
  }
  // for(int i = 0; i < n; ++i){
  //   cout << s[i] << ' ';
  // }cout << endl;
  // cout << "step" << endl;
  // for(auto e:step){
  //   cout << e << ' ';
  // }
  // cout << endl;
  // cout << "dist" << endl;
  // for(auto e:dist){
  //   cout << e << ' ';
  // }
  // cout << endl;
  // cout << "idx" << endl;
  // for(auto e:idx){    
  //   cout << e << ' ';
  // }
  // cout << endl;
  for(int i = dist.size()-1; i > 0; --i){
    cout << dist[i] << endl;
    int x = idx[i] - dist[i];
    while(idx[i-1] > x)i--;
  }
  return 0;
}


Measured memory_bytes: 4776
#include <iostream>
#include <string>
#include <map>

using namespace std;

int main()
{
	string s,max("");
	map<string,int> w;
	map<int,string> x;
	
	while(cin>>s){
		if(s.size()>max.size()) max=s;
		w[s]++;
	}
	
	for(map<string,int>::iterator it=w.begin();it!=w.end();it++)
		x[(*it).second] = (*it).first;
	
	cout<<(*x.rbegin()).second<<" "<<max<<endl;
	return 0;
}

Measured memory_bytes: 0
//https://atcoder.jp/contests/abc156/tasks/abc156_a
#include <bits/stdc++.h>
#if LOCAL
#include "dump.hpp"
#else
#define dump(...)
#endif
using namespace std;
using ll=long long;
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
template<class T>bool chmax(T &a, const T &b) {if (a<b) { a=b; return 1; } return 0;}
template<class T>bool chmin(T &a, const T &b) {if (b<a) { a=b; return 1; } return 0;}
int main() {
#if LOCAL&01
    std::ifstream in("./test/sample-1.in");
    //std::ifstream in("./input.txt");
    std::cin.rdbuf(in.rdbuf());
#else
    cin.tie(0);
    ios::sync_with_stdio(false);
#endif
    ll N, R; cin>>N>>R;
    ll ans=R;
    if(N<10){
        ans=R+100*(10-N);
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
N = int(input())
a = list(map(int, input().split()))
a0 = 0
a2 = 0
a4 = 0

for i in a:
    if i % 4 == 0:
        a4 += 1
    elif i % 2 == 0:
        a2 += 1
    else:
        a0 += 1

if N == 3 and a4 >= 1:
    print('Yes')
elif a4 >= a0:
    print('Yes')
elif a4 +1 == a0 and a2 ==0:
    print('Yes')
else:
    print('No')

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

int main() {
  int n;
  int count = 0;
  cin >> n;
  bool x = false;
  vector<int> h(n);
  vector<int> counts(n);
  for(int i =0;i<n;i++){
    cin >> h.at(i);
  }
  for(int k = 0;k<n;k++){
    if(x){
      break;
    }
  	for(int i = 0;i<n;i++){
        if(k+i == n-1){
          //cout << k << i <<"ya-meta" << endl;
          x = true;
          break;
        }
        //cout << k+i << k+i+1 << endl;
    	if(h.at(k+i) >= h.at(k+i+1)){
      		count++;
    	}
   		else{
      		break;
    	}
  	}
  	counts.at(k) = count;
    count = 0;
  }
  sort(counts.begin(),counts.end());
  reverse(counts.begin(),counts.end());
  cout << counts.at(0) << endl;
  
  
  
  

}


Measured memory_bytes: 1024
using System;
using System.Linq;
using System.Collections.Generic;
namespace Myatcoder
{
    public class Program
    {
        public static void Main()
        {
            int[] NK = Console.ReadLine().Split().Select(x => int.Parse(x)).ToArray();
            int[] A = Console.ReadLine().Split().Select(x => int.Parse(x)).ToArray();
            Dictionary<int, int> D = new Dictionary<int, int>(NK[0]);
            for (int i = 0; i < NK[0]; i++) {
                D[A[i]] = 0;
            }
            int[] B = new int[D.Keys.Count];
            D.Keys.CopyTo(B, 0);
            double ans = 1;
            double len = B.Length;
            if (len > NK[1]) 
            {
                len -= NK[1];
                double k = NK[1];
                ans += Math.Ceiling(len / (k - 1));
            }
            Console.WriteLine(ans);
        }
    }
}

Measured memory_bytes: 22752
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define lper(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ins insert
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
using vpl=vector<pl>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[4]={1,0,-1,0};
const ll dx[4]={0,-1,0,1};
ll modfac(ll a){
    ll ans=1;
    while(a>1){
        ans*=a;
        ans%=1000000007;
        a--;
    }
    return ans;
}
ll modinv(ll a,ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m; 
    if (u < 0) u += m;
    return u;
}
struct UnionFind {
    vector<int> par;
    
    UnionFind(int n) : par(n, -1) {}

    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
};
ll modpow(ll a, ll n, ll mod) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
int main(){
    ll n,m,ans=0;cin >> n >>m;
    vvl v(m);
    rep(i,m){
        ll k;cin >> k;
        rep(j,k){
            ll x;cin >> x;
            v[i].pb(x-1);
        }
    }
    vl p(m);
    rep(i,m)cin >> p[i];
    rep(bit,1<<n){
        ll sum=0;
        rep(i,m){
            ll cnt=0;
            for(auto x:v[i]){
                if(bit&(1<<x))cnt++;
            }
            if(p[i]==cnt%2)sum++;
        }
        if(sum==m)ans++;
    }
    cout << ans <<endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <ctype.h>
int main ( void ) {
    char input;int i,len;
    while(1){
    scanf("%c",&input);
        if(input=='\n') break;
        if(islower(input)){
            input=toupper(input);
        }
        if(input==' '){
            printf(" ");
        }else if(input=='.'){
            printf(".");
        }else printf("%c",input);
    }
    puts("");
    return 0;
}

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

int main(){
    int q;
    cin >> q;
    for(int k=0;k<q;++k){
        string n;
        cin >> n;
        int cnt = 0;
        set<string> st;
        st.insert(n);
        while(n.size() > 1){
            string next;
            int maxi = 0;
            for(int i=1;i<n.size();++i){
                string a = n.substr(0,i);
                string b = n.substr(i);
                int prod = stoi(a) * stoi(b);
                if(prod > maxi){
                    maxi = prod;
                    next = to_string(prod);
                }
            }
            if(st.count(next)){
                cnt = -1;
                break;
            }
            st.insert(next);
            n = next;
            cnt++;
        }
        cout << cnt << endl;
    }

    return 0;
}



Measured memory_bytes: 3300
#include <iostream>
#include<algorithm>
using namespace std;
int main(void){
    
    int n,ans=0;
    int d[101];
    
    cin>>n;
    for(int i=0;i<n;i++)cin>>d[i];
    sort(d,d+n);
    for(int i=1;i<n;i++)if(d[i-1]<d[i])ans++;
    cout<<ans+1<<endl;
}


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

int n, m, res;
int dp[128]={0}, b[128], f[128];

void solve(){
	
	for(int i=2; i<128; ++i){
		dp[i]=INT_MAX;
	}
	
	for(int i=1; i<=n; ++i){
		
		if(dp[i]==INT_MAX){
			continue;
		}
		
		for(int j=0; j<m; ++j){
			
			if(b[j]<=i&&i<=f[j]){
				dp[f[j]+1] = min(dp[f[j]+1], dp[i]+1);
			}
		}
			
	}
	
	return;	
}

int main(){
	
	cin>>n>>m;
	
	for(int i=0; i<m; ++i){
		cin>>b[i]>>f[i];
	}
	
	solve();
	
	if(dp[n+1]<INT_MAX){
		cout << dp[n+1] << endl;
	}
	else{
		cout << "Impossible" << endl;
	}
	
	return 0;
}

Measured memory_bytes: 1164
#define _DEBUG 1
#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#ifdef _DEBUG
#define dump(x) cerr << #x << "=" << x << endl
#define dump2(x, y) cerr << #x << "=" << x << "," << #y << "=" << y << endl
#define dump3(x, y, z)                                                     \
  cerr << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z \
       << endl
#define check(s) cerr << s << endl
#else
#define dump(x)
#define dump2(x, y)
#define dump3(x, y, z)
#define check(s)
#endif

#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define unique(v) v.erase(unique(v.begin(), v.end()), v.end());

const ll LINF = 2e18;
const int INF = 1e9;

void yes() { cout << "Yes" << endl; }
void no() { cout << "No" << endl; }
void yesOrNo(bool flg) {
  if (flg)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}

void solve(std::string S, std::string T) {
  bool result = S == T.substr(0, S.size()) && S.size() + 1 == T.size();
  yesOrNo(result);
}

int main() {
  std::string S;
  std::cin >> S;
  std::string T;
  std::cin >> T;
  solve(S, T);
  return 0;
}


Measured memory_bytes: 3632
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <complex>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iomanip>
#include <assert.h>
#include <array>
#include <cstdio>
#include <cstring>
#include <random>
#include <functional>
#include <numeric>
#include <bitset>

using namespace std;

void main_(); signed main() {
  cin.tie(0); ios::sync_with_stdio(false);
  main_(); return 0;
}

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a, 0, sizeof a)
#define minus(a) memset(a, -1, sizeof a)
template<class T1, class T2> inline bool minimize(T1 &a, T2 b) { return b < a && (a = b, 1); }
template<class T1, class T2> inline bool maximize(T1 &a, T2 b) { return a < b && (a = b, 1); }

typedef long long ll;
int const inf = 1<<29;

void main_() {

  string s; cin >> s;
  if(s[0] == s.back() && s[0] == 'x') { cout << "x\n"; }
  else { cout << "o\n"; }
  
}

Measured memory_bytes: 3216