akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main() {
	
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    string s;
    cin>>s;
    ll sum=0;
    for(ll i=0;i<s.length();i++)
    {
        sum+=(s[i]-'0');
    }
    if((sum%9)==0)
    {
        cout<<"Yes"<<endl;
    }
    else
    {
        cout<<"No"<<endl;
    }
    
	return 0;
}


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

using namespace std;

typedef long long int ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pt;
typedef pair<ll,ll> pll;

#define Max 1000001
#define intinf 2147483647
#define longlonginf 9223372036854775807
#define MOD 998244353
#define MOD2 1000000007
#define fastio ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define vint vector<int>
#define vll vector<long long>
#define endl '\n'
#define fi first
#define se second
#define pb push_back
#define F(i,n) for(int i = 0;i<n;i++)
#define Fr(i,l,r) for(int i = l;i <= r;i++)
#define rF(i,n) for(int i = n-1;i>=0;i--)
#define all(arr) arr.begin(),arr.end()


ll Lpow(ll a,ll b)
{
    ll ans = 1;
    while(b > 0)
    {
        if(b%2)
            ans = (ans*a);
        a = (a*a);
        b = b/2;
    }
    return ans;
}

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

signed main()
{
    fastio;
//    cout.flush();
    
    int n,k;
    cin >> n >> k;
    
    vector<int> arr(n);
    int mi = intinf;
    F(i,n)
    {
        cin >> arr[i];
        mi = min(mi,arr[i]);
    }
    
    sort(all(arr));
    
    vector<int> brr(100005,0);
    
    for(int i = 0;i<n;i++)
    {
        for(int j = 0;j<mi;j++)
        {
            if(arr[i] + j <= 100000)
                brr[arr[i] + j] = 1;
        }
    }
    
    for(int i = 1;i<=100000;i++)
    {
        for(int j = 0;j<n;j++)
        {
            if(arr[j] < i && brr[i - arr[j]] == 0)
                brr[i] = 1;
        }
    }
    
    if(brr[k] == 1)
        cout << "First\n";
    else
        cout << "Second\n";
    
    return 0;
}


Measured memory_bytes: 640
#include<cstdio>
#include<functional>
#include<algorithm>
#include<cstring>
using namespace std;
int main(void)
{
	int n,i,a[100001],b[100000],x;
	long long sum;
	scanf("%d",&n);
	for(i=0;i<=n;i++)	scanf("%d",&a[i]);
	for(i=0;i<n;i++)	scanf("%d",&b[i]);
	sum=0;
	for(i=0;i<n;i++)	{
		if(a[i]>=b[i])	{
			x=b[i];
			a[i]-=x;
			b[i]-=x;
			sum+=x;
		}
		else {
			x=a[i];
			a[i]-=x;
			b[i]-=x;
			sum+=x;
			if(a[i+1]>=b[i])	{
				x=b[i];
				a[i+1]-=x;
				b[i]-=x;
				sum+=x;
			}
			else {
				x=a[i+1];
				a[i+1]-=x;
				b[i]-=x;
				sum+=x;
			}
		}
	}
	printf("%lld\n",sum);
	return 0;
}

Measured memory_bytes: 896
#include <algorithm>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <cctype>
#include <iostream>
#include <set>
#include <string>
#include <queue>
#include <map>
#include <utility>
using namespace std;
int size(string x){
	string::size_type size=x.size();
	return size;
}
#define fu(l,k) for(int i=l;i<k;i++)
#define fd(l,k) for(int i=l;i>k;i--)
#define sort(ss) sort(ss.begin(), ss.end())
#define rsort(ss) sort(ss.rbegin(), ss.rend())
typedef  vector<string> vs;
typedef  vector<int> vi;
double pi(){
	return M_PI;
}
typedef set<int> set_i;
typedef set<string> set_s;
int INF=1000000;
int main(){
	double l[11]={},ll=0,lb;
	double v1,v2,ans;
	double m;
	char a;
	while(cin>>l[0]>>a>>l[1]>>a>>l[2]>>a>>l[3]>>a>>l[4]>>a>>l[5]>>a>>
		l[6]>>a>>l[7]>>a>>l[8]>>a>>l[9]>>a>>v1>>a>>v2){
		ll=0;
		for(int i=0;i<10;i++){
			ll+=l[i];
		}
		m=ll/(v1+v2);
		lb=0;
		for(int i=0;i<10;i++){
			lb+=l[i];
			if(m*v1<=lb){
				ans=i+1;
				break;
			}
		}
		cout<<(int)ans<<endl;
	}
}

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

int main() {
	
	int n, k;
	cin >> n >> k;
	
	int i=1;
	while(1){
		if(n<pow(k,i)) {
			cout << i << endl;
			break;
		}
		i++;
	}
	
	return 0;
}

Measured memory_bytes: 256
import Foundation
func readInts() -> [Int] { readLine()!.split(separator: " ").map { Int($0)! } }

_ = readLine()
var ai = readInts()
var ans = 0
while true {
  if ai.count == ai.filter({ $0 % 2 == 0 }).count {
    ans += 1
    ai = ai.map { $0 / 2 }
  } else { break }
}
print(ans)

Measured memory_bytes: 13508
#include <bits/stdc++.h>
#include <unistd.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<ll,ll> P;
 
long long int INF = 1e18;
const ll fact_table = 5000000;
double Pi = 3.1415926535897932384626;
 
vector<ll> G[550010];
//vector<P> tree[500010];
priority_queue <ll> pql;
priority_queue <P> pqp;
//big priority queue
priority_queue <ll,vector<ll>,greater<ll> > pqls;
priority_queue <P,vector<P>,greater<P> > pqps;
//small priority queue
//top pop
 
int dx[8]={1,0,-1,0,1,1,-1,-1};
int dy[8]={0,1,0,-1,1,-1,-1,1};
char dir[] = "DRUL";
//ll bit[500005];
//↓,→,↑,←
 
 
#define p(x) cout<<x<<"\n";
#define el cout<<"\n";
#define pe(x) cout<<(x)<<" ";
#define ps(x) cout<<fixed<<setprecision(25)<<x<<endl;
#define pu(x) cout<<(x);
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define CLEAR(a) a = decltype(a)(); 
 
 
ll mod = 998244353;
//ll mod = 1000000007;
 
ll rui(ll number1,ll number2){
 
    if(number2 == 0){
        return 1;
    }else{
        ll number3 = rui(number1,number2 / 2);
        number3 *= number3;
        number3 %= mod;
        if(number2%2==1){
            number3 *= number1;
            number3 %= mod;
        }
        return number3;
    }
}
ll gcd(ll number1,ll number2){
 
    if(number1 > number2){
        swap(number1,number2);
    }
    if(number1 == 0 || number1 == number2){
        return number2;
    }else{
        return gcd(number2 % number1,number1);
    }
}
void YES(bool condition){
 
    if(condition){
        p("YES");
    }else{
        p("NO");
    }
    return;
}
void Yes(bool condition){
 
    if(condition){
        p("Yes");
    }else{
        p("No");
    }
    return;
}
 
/*
ll fact[fact_table + 5],rfact[fact_table + 5];
 
void c3_init(){
    fact[0] = rfact[0] = 1;
    for(ll i=1; i<=fact_table; i++){
        fact[i] = (fact[i-1]*i) % mod;
    }
    rfact[fact_table] = rui(fact[fact_table],mod - 2);
    for(ll i=fact_table; i>=1; i--){
       rfact[i-1] = rfact[i] * i;
       rfact[i-1] %= mod;
    }
    return;}
ll c3(ll n,ll r){
    return (((fact[n] * rfact[r]) % mod ) * rfact[n-r]) % mod;}
*/
 
ll n,m,num,sum,a,b,c,d,e,g,h,w,i,j,q,r,l;
ll k,ans;
ll x[500005],y[500005],z[500005];
char s[500005];

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

    cin >> x[0] >> x[1];
    for(int i=0;i<2;i++){
        if(x[i] == 1){
            ans += 300000;
        }else if(x[i] == 2){
            ans += 200000;
        }else if(x[i] == 3){
            ans += 100000;
        }
    }
    if(x[0] == x[1] && x[0] == 1){
        ans += 400000;
    }
    p(ans);


    return 0;
}


















Measured memory_bytes: 17152
#include <bits/stdc++.h>
using namespace std;
#define int long long
int MOD = (int)1e9 + 7;
int INF = (int)2e18;
// Comment out below and program paste

// #include "UnionFind.hpp"
// #include "power.hpp"

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<string> S(N);
    int ans = 0;
    int BA = 0, XA = 0, BX = 0;
    for (int i = 0; i < N; i++) {
        cin >> S[i];
        int l = S[i].length();
        for (int j = 0; j < S[i].length() - 1; j++) {
            if(S[i].substr(j, 2) == "AB") ++ans;
        }
        if (S[i][0] == 'B' && S[i][l - 1] == 'A') ++BA;
        else if (S[i][l - 1] == 'A') ++XA;
        else if (S[i][0] == 'B') ++BX;
    }
    if (XA > 0 && BA > 0) {
        ++ans;
        --XA;
    }
    if (BA > 1) {
        ans += (BA - 1);
        BA = 1;
    }
    if (BA == 1 && BX > 0) {
        ++ans;
        --BX;
        --BA;
    }
    ans += min(XA, BX);
    cout << ans << endl;
}


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

int main() {

  int N;
  cin >> N;
  
  if(N%10==3) cout << "bon" << endl;
  
  else if(N%10==0 || N%10==1 || N%10==6 || N%10==8) cout << "pon" << endl;
  
  else cout << "hon" << endl;
  
}

Measured memory_bytes: 3604
n,m = map(int,input().split())
data = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    data[a-1].append(b-1)
    data[b-1].append(a-1)
ans = 0
def search(passed):
    if len(passed)==n:
        global ans
        ans += 1
    else:
        for i in data[passed[-1]]:
            if i in passed:
                continue
            else:
                search(passed+[i])
search([0])
print(ans)

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0;i < n;i++){
      cin >> a[i];
    }
    sort(a.begin(),a.end());
    for(int i = 0;i < n - 1;i++){
      if(a[i] == a[i + 1]){
        cout << "NO" << endl;
        return 0;
      }
      else continue;
    }
    cout << "YES" << endl;
}


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

#define fst first
#define snd second
#define ll long long
#define ld long double
#define pb push_back
#define emp emplace_back
#define pii pair<int, int>
#define usg unsigned
#define sg signed
#define mp make_pair

using namespace std;

void setIO(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);
}

const ld PI = 4*atan((ld)1);
const int INF = 1e9+7;
const ll _INF = 1e18+7;
const int mxn = 1e6+7;

ll fact[mxn];

ll fpow(ll x, ll y){
	ll res = 1;
	while (y){
		if (y&1) res = (res*x)%INF;
		x = (x*x)%INF;
		y >>= 1;
	}
	return res;
}

ll c(ll x, ll y){
	return fact[x]*(fpow(fact[x-y], INF-2)*fpow(fact[y], INF-2)%INF)%INF;
}

int main(){
	setIO();
	fact[0] = 1;
	for (int i = 1; i < mxn; i++)
		fact[i] = (fact[i-1]*i)%INF;
	ll n, ans = 0; cin >> n;
	for (int i = 2; i <= n; i++){
		ll znconf = (fpow(2, i)-2)*c(n, i)%INF;
		ans = (ans+(znconf*fpow(8, n-i))%INF)%INF;
	}
	cout << ans << endl;
}

Measured memory_bytes: 11404
import collections as c
ip = lambda : map(int, input().split())
# ##############
mod = 1e9+7
N,M = ip()
a = set()
for i in range(M):
    a.add(int(input()))
dp = [0]*(N+1)
dp[0] = 1
if 1 in a:
    pass
else:
    dp[1] = dp[0]
if N>1:
    for i in range(2,N+1):
        if i in a:
            continue
        dp[i] += dp[i-2] + dp[i-1]
        dp[i] = int(dp[i] % mod)
print(dp[N])

Measured memory_bytes: 12268
#include<vector>
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include <iostream>
#include <algorithm>
#include <map>
#include <cmath>
#include<queue>

#define INF 100000000000000
using namespace std;
typedef long long llong;

//int isalpha(char ch): ch がアルファベットなら true を返す
//int isdigit(char ch): ch が数字なら true を返す
//int islower(char ch): ch が小文字なら true を返す
//int isupper(char ch): ch が大文字なら true を返す
//int tolower(char ch): ch の小文字を返す
//int toupper(char ch): ch の大文字を返す

//string型
//size()	文字数を返す
//Insert()	（指定した場所に）文字・文字列を挿入する
//erase()	（指定した場所の）文字・文字列を削除する
//clear()	すべての文字を削除する
//substr()	文字列の（指定した）部分文字列を返す
//replace()	（指定した）部分文字列を新しい文字列に置換する
//c_str()変換
//文字列の比較は、<=や==などを使え
//replace関数を使い、簡単に文字列を置換
//リバース関数：reverse(str.begin(), str.end());
//map<type, type> dict;で宣言
//グラフ理論用変数
//vector<vector<llong> > graph(N);

//ソート
//降順sort(v.begin(), v.end(), std::greater<Type>());

//大文字から小文字へんかん
//w[i] = w[i]-'A'+'a';

//vector
//assignメソッド　引数：サイズ、値
//与えられたサイズと値でvectorを初期化する

//queueクラス
//find()次に取り出す値の表示をする。
//pop()値を取り出す。戻り値はなし
//push()キューに値をプッシュする

//priority_queueクラス

//切り上げ
//ceil
//floor

int main(){
    map<string, llong> dict;
    llong N;
    string key;
    cin >> N;
    for(int i=0; i<N; i++){
        cin >> key;
        dict[key] += 1;
    }
    cout << "AC x "<< dict["AC"] << endl;
    cout << "WA x "<<dict["WA"] << endl;
    cout << "TLE x "<<dict["TLE"] << endl;
    cout << "RE x "<<dict["RE"] << endl;

    return 0;
}





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

using namespace std;

int n,m;
int cnt;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
char t[20][20];

void fanc(int x,int y){
	cnt++;
	int ny,nx;
	t[y][x]=',';
	for(int i=0;i<4;i++){
		ny=y+dy[i];
		nx=x+dx[i];
		if(ny>=0&&nx>=0&&ny<m&&nx<n&&t[ny][nx]=='.'){
			fanc(nx,ny);
		}
	}
}

int main(){
	
	while(1){
		
		cin >> n >> m;
		
		if(n==0) break;
		
		int nx,ny;
		for(int i=0;i<m;i++){
			for(int j=0;j<n;j++){
				cin >> t[i][j];
				if(t[i][j]=='@'){
					ny=i;nx=j;
				}
			}
		}
		cnt=0;
		fanc(nx,ny);
		cout << cnt << endl;
	}
	return 0;
}


Measured memory_bytes: 3072
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  int A[N];
  for(int i = 0; i < N; i++) A[i] = 0;
  for(int i = 0; i < N-1; i++){
    int a;
    cin >> a;
    a--;
    A[a]++;
  }
  for(int i = 0; i < N; i++) cout << A[i] << endl;
    
}

Measured memory_bytes: 4412
#include <bits/stdc++.h>
using namespace std;
#define data_type long long

int main()
{

   data_type n,m=0,sum=0;
   cin>>n;
   vector<data_type>vc(n);
   for(auto &i:vc)
      cin>>i;
   for(auto i:vc)
   {
      m=max(i,m);
      sum+=m-i;
   }

   cout<<sum<<endl;
    return 0;

}


Measured memory_bytes: 4700
#include<stdio.h>
#define N 100001
typedef struct treeee
{
  int p;
  int l;
  int r;
}tree;
tree T[N];
int n;

int depth(int i){
  int count=0,iNoOya;
  iNoOya=i;
  while(1){
    if(T[iNoOya].p==-1) break;
    iNoOya=T[iNoOya].p;
    count++;
    
  }
  return count;
}

void hantei(int i){
  if(T[i].l==-1&&T[i].p!=-1) printf("leaf,");
  else if( T[i].p == -1)printf("root,");
  else if(T[i].l !=-1) printf("internal node,");
}

void printChild(int i){
  int ani;
  printf(" [");
  if(T[i].l !=-1){
    printf("%d",T[i].l);
    ani= T[i].l;
    while(1){
      if(T[ani].r==-1)break;
      printf(", %d",T[ani].r);
      ani=T[ani].r;
    }
  }
  printf("]\n");
}



int main(){
    int i,j,node,zisu,child,left;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    T[i].p=-1;
    T[i].l=-1;
    T[i].r=-1;
  }
  for(i=0;i<n;i++){
    scanf("%d%d",&node,&zisu);
    for(j=0;j<zisu;j++){
      scanf("%d",&child);
      if(j==0){
	T[node].l=child;
	T[child].p = node;
      }   
      else{
	T[left].r=child;
	T[child].p=node;
      }
      left = child;
    }
  }

  for(i=0;i<n;i++){
    printf("node %d: parent = %d, depth = %d, ",i,T[i].p,depth(i));
    hantei(i);
    printChild(i);
   
  }
  return 0;
}

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

int main() {
    string S, T;
    cin >> S >> T;
    int A, B;
    cin >> A >> B;
    string U;
    cin >> U;
    if(S == U) {
        A--;
    } else {
        B--;
    }
    cout << A << " " << B << '\n';
    return 0;
}

// overflow
// corner cases


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

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

}



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

using namespace std;
typedef long long ll;
typedef long double ld;
using graph = vector<vector<int>>;

#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define repd(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//xにはvectorなどのコンテナ
#define all(x) (x).begin(),(x).end()
#define size(x) ((ll)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))

#define INF 1000000000000
#define MOD 10000007
#define MAXR 100000

#define pb push_back
#define mp make_pair
#define f first
#define s second

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 (b<a) { a=b; return true; } return false; }

int main(){
	ll a,b,c,x,y; cin>>a>>b>>c>>x>>y;
	ll ans=0;
	if(a+b>2*c)ans+=2*c*min(x,y);
	else ans+=(a+b)*min(x,y);
	if(x<y)ans+=min(2*c*(y-x),b*(y-x));
	if(x>y)ans+=min(2*c*(x-y),a*(x-y));
	cout<<ans<<endl;
}



Measured memory_bytes: 256
#include <math.h>
#include <algorithm>
#include <set>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <string>
#include <cstring>
#include <functional>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <chrono>
#include <climits>
using namespace std ;
#define ld long double
#define int long long
#define ii pair<int,int>
#define FAST_IO ios_base::sync_with_stdio(false) ;cin.tie(NULL);cout.tie(NULL); clock_t beg = clock()
#define dbg(x) cerr << #x << " is " << x << endl;
#define ms(x,a) memset(x,(int)(a),sizeof(x))
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define vi vector<int >
#define pb push_back
#define endl '\n'
#define ff first
#define ss second
const int N = 3e5+7 ;
const int INF = 1e18 ;
const int MOD = 1e9 + 7 ;
string s ;

void solve(){
	int n , m ;
	cin >> n >>m ;
   vector<ii> a(n) ;
   for(int i = 0 ; i < n ; i++){
   	cin >> a[i].ff >> a[i].ss ;
   }
   priority_queue<int> Q ;
   sort(all(a)) ;
   int j = 0 ;
   int ans = 0 ;
   for(int i = 0 ; i < m+1 ; i++){
   		while(j<n && a[j].ff == i){
   			Q.push(a[j].ss) ;
   			j++ ;
   		}
   		if(!Q.empty()) ans += Q.top() , Q.pop();
   }
   cout << ans << endl ;
}

int32_t main(){
	FAST_IO ;
	int t = 1 ;
//	cin >> t ;
	while(t--){
		solve() ;
	}
    cerr << "\nExecution time: " << (clock() - beg) / 1000 << '\n';
}


Measured memory_bytes: 2936
def main():
    n, m, x, y = map(int, input().split())
    dx = map(int, input().split())
    dy = map(int, input().split())

    max_x = max(list(dx))
    min_y = min(list(dy))
    # if x >= y:
    #     print("WAR")
    #     exit()

    z = x + 1
    while z <= y:
        if z > max_x and z <= min_y:
            # print("No War", z)
            print("No War")
            exit()
        z += 1
    print("War")


if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
#include <algorithm>
#include <iostream>
#include <set>
using namespace std;
int main(){
  int N;
  cin >> N;
  int A[N], id[N+1];
  for(int i = 0; i < N; ++i){
    cin >> A[i];
    id[A[i]] = i;
  }
  long long int ans = 0LL;
  set<int> S;
  S.insert(N);
  S.insert(-1);
  for(int i = 1; i <= N; ++i){
    S.insert(id[i]);
    set<int>::iterator itr = S.find(id[i]), l = itr, r = itr;
    --l;
    ++r;
    ans += (long long int)(id[i] - *l)*(*r - id[i])*i;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 11136
#include<iostream>
#include<cmath>
#include<stdio.h>
using namespace std;
int main(){
    double x1,x2,y1,y2,distance;
    cin>>x1 >> y1 >> x2 >> y2;
    distance=(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
    printf("%f\n",sqrt(distance));
}


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

int main(){
  int a,b;
  cin >> a >> b;
  if(a<=0 && b>=0)cout << "Zero" << endl;
  else if(a>0)cout << "Positive" << endl;
  else if(b<0){
    if((b-a+1)%2==1)cout << "Negative" << endl;
    else cout << "Positive" << endl;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/rope>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define ll long long
//#define int long long
#define pb push_back
#define x first
#define ld long double
#define y second
#define mk(a,b) make_pair(a,b)
#define rr return 0
#define sqr(a) ((a)*(a))
#define all(a) a.begin(),a.end()

using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
template<class value, class cmp = less<value> >
using ordered_set = tree<value, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
template<class value, class cmp = less_equal<value> >
using ordered_multiset = tree<value, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
template<class key, class value, class cmp = less<key> >
using ordered_map = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

/// find_by_order()
/// order_of_key()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline int randll(int l = INT_MIN, int r = INT_MAX) {
    return uniform_int_distribution<int>(l, r)(rng);
}
const int MOD = 1e9 + 7;
inline void add (int &val, int x) {
    val += x;
    if (val < 0) val += MOD;
    if (val >= MOD) val -= MOD;
}
inline int mul (int a, int b) {
    return ((ll)a * b) % MOD;
}
inline int binpow (int a, int n) {
    int ans = 1;
    while (n) {
        if (n & 1) {
            ans = mul(ans, a);
        }
        a = mul(a, a);
        n >>= 1;
    }
    return ans;
}
inline int inv (int x) {
    return binpow(x, MOD - 2);
}
const int N = 401;
int dp[N][N] = {}, sum[N][N] = {};
main()
{
    ios::sync_with_stdio(0);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, c;
    cin >> n >> c;
    vector <int> a(n), b(n);
    for (auto &i : a) cin >> i;
    for (auto &i : b) cin >> i;
    for (int i = 0; i < n; i++) {
        for (int i1 = a[i]; i1 <= b[i]; i1++) {
            int step = 1;
            for (int j = 0; j <= c; j++) {
                add(sum[i][j], step);
                step = mul(step, i1);
            }
        }
    }
    dp[0][0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= c; j++) {
            if (!dp[i][j]) continue;
            for (int k = 0; k + j <= c; k++) {
                add(dp[i + 1][j + k], mul(dp[i][j], sum[i][k]));
            }
        }
    }
    cout << dp[n][c] << '\n';
}


Measured memory_bytes: 1536
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<climits>
#include<iostream>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<list>
#include<map>
#include<set>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
#define pb push_back
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};
 
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)

int h,w;
char s[100][100];
bool used[100];
bool d[300][300];
bool check(char up,char m){
    if(d[up][m])
        return true;
    for(int i = 'A';i <= 'Z';i++){
        if(d[up][i]){
            if(check(i,m))
                return true;
        }
    }
    return false;
}
void solve(){

    bool f = true;
    REP(i,100)
        used[i] = false;
    fill((bool*)d, (bool*)d + 300 * 300,false);
    while(f){
        f = false;
        REP(i,h){
            REP(j,w){
                if(s[i][j] != '.' && !used[s[i][j] - 'A']){
                    used[s[i][j] - 'A'] = true;
                    f = true;
                    int m = s[i][j];

                    int maxi = 0,maxj = 0,mini = 100,minj = 100;
                    REP(k,h){
                        REP(l,w){
                            if(s[k][l] == m){
                                if(maxi < k)
                                    maxi = k;
                                if(maxj < l)
                                    maxj = l;
                                if(mini > k)
                                    mini = k;
                                if(minj > l)
                                    minj = l;
                            }
                        }
                    }
                    FOR(k,mini,maxi + 1){
                        FOR(l,minj,maxj + 1){
                            if(s[k][l] == '.' || (m != s[k][l] && check(s[k][l],m))){
                                printf("SUSPICIOUS\n");
                                return;
                            }
                            if(m != s[k][l]){
                                d[m][s[k][l]] = true;
                            }
                        }
                    }
                }
                if(f)
                    break;
            }
            if(f)
                break;
        }
    }
    printf("SAFE\n");
}

void input(){
    scanf("%d%d",&h,&w);
    REP(i,h){
        scanf("%s",&s[i][0]);
    }
}


int main(){
    int n;
    scanf("%d",&n);
    for(int i = 0;i < n;i++){
        input();
        solve();
    }
}

Measured memory_bytes: 3156
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair< ll, ll > Pi;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep2(i,n) for(int i=1;i<=(n);i++)
#define rep3(i,i0,n) for(int i=i0;i<(n);i++)
#define pb push_back
#define mod 1000000007
const ll INF = 1LL << 60;
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; }
ll gcd(ll a, ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) {return a/gcd(a,b)*b;}
#define all(x) x.begin(), x.end()
#define mp make_pair
bool compare(Pi a, Pi b) {
    if(a.first != b.first){
        return a.first < b.first;
        
    }else{
        return a.second < b.second;
    }
}


bool In_map(ll y,ll x,ll h,ll w){
    if(y<0 || x<0 || y>=h || x>=w){
        return 0;
    }else{
        return 1;
    }
}
const vector<ll> dx{1,0,-1,0};
const vector<ll> dy{0,1,0,-1};


int main() {
    ll N;
    cin >>N;
    vector<ll> A(N);
    vector<ll> ans(N);
    rep(i,N-1){
        ll a;
        cin>>a;
        a--;
        ans[a]++;
    }

    rep(i,N){
        cout << ans[i] << endl;
    }
    


    return 0;
    

}

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

int main(){
  double n,t,a;
  cin >> n >> t >> a;
  vector<pair<double,int>> h(n);
  for(int i=0;i<n;i++){
    double x;  cin >> x;
    h.at(i).first=max(a-t+x*0.006,t-x*0.006-a);
    h.at(i).second=i+1;
  }
  sort(h.begin(),h.end());
  cout << h.at(0).second << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cmath>
#include <cassert>
#include <queue>
#include <set>
#include <map>
#include <valarray>
#include <bitset>
#include <stack>
#include <iomanip>
#include <fstream>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
const int INF = 1<<29;
typedef long long ll;
typedef pair<int,int> pii;

char c[10][10];

int main() {
  int n;
  cin >> n;
  int strong = -1;
  REP(i,n) {
    int cnt = 0;
    REP(j,n) {
      cin >> c[i][j];
      if (c[i][j] != 'x')cnt++;
    }
    if (cnt == n) strong = i;
  }
  REP(i,1000) {
    if (strong == -1) printf("%d\n", rand()%n+1);
    else printf("%d\n", strong+1);
    fflush(stdout);
    int a;
    scanf("%d", &a);
  }
}

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

using namespace std;

int a[100100],b[100100],c[100100];
int dp_a[100100],dp_b[100100],dp_c[100100];

int vac(int i,int n,char estado){
    if(i>n) return 0;

    int resp;

    if(i==0){
        resp=max((a[i]+vac(i+1,n,'a')),(b[i]+vac(i+1,n,'b')));
        resp=max(resp,c[i]+vac(i+1,n,'c'));
    }else{
        switch(estado){
            case 'a':
                if(dp_a[i]!=-1) return dp_a[i];
                return dp_a[i] =max(b[i]+vac(i+1,n,'b'),c[i]+vac(i+1,n,'c')); break;
            case 'b':
                if(dp_b[i]!=-1) return dp_b[i];
                return dp_b[i] =max(a[i]+vac(i+1,n,'a'),c[i]+vac(i+1,n,'c')); break;
            case 'c':
                if(dp_c[i]!=-1) return dp_c[i];
                return dp_c[i] =max(a[i]+vac(i+1,n,'a'),b[i]+vac(i+1,n,'b')); break;
        }
    }
    return resp;
}

int main(){

    memset(dp_a,-1,sizeof(dp_a));
    memset(dp_b,-1,sizeof(dp_b));
    memset(dp_c,-1,sizeof(dp_c));

    int n;
    cin>>n;

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

    cout<<vac(0,n-1,'d');
}


Measured memory_bytes: 12204
# 人を頂点と見なしたグラフを作る。有向で、逆向きの場合は正負を反転させて辺を張る
# 頂点からの距離を記録し、一致しない箇所があればNG。
# 全ての辺を通るまで続ける。
# 辺の情報を[{0から行ける頂点},{1から行ける頂点},...]で管理する
# 親には進まないようにしてDFSする

N,M = map(int,input().split())
E = [[] for i in range(N)]
for i in range(M):
  L,R,D = map(int,input().split())
  E[L-1].append([R-1,D])
  E[R-1].append([L-1,-D])
from collections import deque
# 頂点、親、距離
INF = 10 ** 10
dist = [INF] * N
for i in range(N):
  if dist[i] != INF:
    continue
  dist[i] = 0
  q = deque()
  q.append(i)
  while q:
    v = q.popleft()
    for child in E[v]:
      if dist[child[0]] == INF:
        dist[child[0]] = dist[v] + child[1]
        q.append(child[0])
      else:
        if dist[child[0]] != dist[v] + child[1]:
          print("No")
          exit(0)
else:
  print("Yes")


Measured memory_bytes: 77304
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pp pair<pair<ll, ll>,pair<ll, ll>>
#define pll pair<ll,ll>
#define pdd pair<double,double>
#define vii vector<int>
#define vll vector<ll>
#define mat vector<vector<ll>>
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define fi first
// #define sc second
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep2(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define all(x) x.begin(),x.end()
#define sz(x) (ll) (x).size()
#define pq priority_queue<ll>
#define pqg priority_queue<ll,vector<ll>,greater<ll>>
#define LB(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin())
#define UB(v,x) (upper_bound(v.begin(),v.end(),x)-v.begin())
#define ERASE(v) sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end())
#define int ll
using namespace std;
const ll INF = (1 << 30 ) - 1;
const ll LLINF = (1LL << 60LL);
const ll MOD = 1000000007;
const ll mod = 998244353;
const ll MAX = 1100000;
const double pi = acos(-1);
const double eps = 1e-10;
ll dx[4] ={1,0,-1,0} , dy[4] ={0,1,0,-1};

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; }

struct Timer{
    chrono::system_clock::time_point start, end;
    Timer(){ start = chrono::system_clock::now(); }
    ~Timer(){
        end = chrono::system_clock::now();
        auto msec = chrono::duration_cast<chrono::milliseconds>(end - start).count();
        cerr<<"time : "<<msec<<" ms"<<endl;
    }
};


signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    // Timer TM;
    
    
    ll n,m;
    cin>>n>>m;
    ll a[40][40];
    map<ll,ll> mp;
    rep(i,n){
        ll k;
        cin>>k;
        rep(j,k){
            cin>>a[i][j];
            mp[a[i][j]]++;
        }
    }
    ll ans=0;
    rep2(i,1,m+1){
        if(mp[i]==n) ans++;
    }

    cout<<ans<<endl;

    return 0;
}


Measured memory_bytes: 256
#include<cstdio>  
#include<cstdlib> 
#include<cstring>  
#include<cmath>  
#include<algorithm>  
using namespace std;  
int n,ans = 0;  
struct NOOD {
	int x, y;
}a[105], b[105];
bool G[205][205];
int girl[205];  
bool vis[205];
  
bool find(int x){  
    for(int j = 1; j <= n; j++){  
        if(G[x][j + n] == true && vis[j + n] == false){  
            vis[j + n] = 1;  
            if(girl[j + n] == 0 || find(girl[j + n])){  
                girl[j + n] = x;  
                return true;  
            }  
        }  
    }  
    return false;  
}  
int main(){  
	scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d%d", &a[i].x, &a[i].y);
    for(int i = 1; i <= n; i++) scanf("%d%d", &b[i].x, &b[i].y);
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			if(a[i].x < b[j].x && a[i].y < b[j].y) {
				G[i][j + n] = 1;
				G[j + n][i] = 1;
	}
	for(int i = 1; i <= n; i++){
		memset(vis,0,sizeof(vis));
		if(find(i)) ans++;
	}
	printf("%d\n", ans);
}


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

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

    int H, W;
    
    cin >> H >> W;

    vector<string> vec(H);
    for(int i = 0; i < H; i++) cin >> vec.at(i);


    for(int i = 0; i < H; i++)
    {
        for(int j = 0; j < W; j++)
        {    
            if(vec.at(i).at(j) != '.')
            {
                break;
            }
            if(j == W - 1)
            {
                for(int k = 0; k < W; k++) vec.at(i).at(k) = '_';
            }
        }
    }

    for(int i = 0; i < W; i++)
    {
        for(int j = 0; j < H; j++)
        {
            if(vec.at(j).at(i) != '.' && vec.at(j).at(i) != '_')
            {
               break;
            }
            if(j == H - 1)
            {
                //cout << "yes" << endl;
                for(int k = 0; k < H; k++) vec.at(k).at(i) = '_';
            }
        }
    }

    bool flag = false;

    for(int i = 0; i < H; i++)
    {
        flag = false;
        for(int j = 0; j < W; j++)
        {
            if(vec.at(i).at(j) != '_')
            {
                cout << vec.at(i).at(j);
            }

            for(int k = 0; k < W; k++)
            {
                if(vec.at(i).at(k) == '#') flag = true;
            }

        }
        if(flag) cout << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, Y;
    cin >> N >> Y;
    REP(i, 0, N) {
        REP(j, 0, N - i) {
            int k = N - i - j;
            if (10000 * i + 5000 * j + 1000 * k == Y) {
                cout << i << " " << j << " " << k << endl;
                return 0;
            }
        }
    }
    cout << "-1 -1 -1" << endl;

    return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <map>
#include <vector>
#include <math.h>
#include <algorithm>
#include <queue>
#include <set>
#include <tuple>
using namespace std;

#define FOR(i,init,a) for(int i=init; i<a; i++)
#define rep(i,a) FOR(i,0,a)
#define rrep(i,a) for(int i=a; i>=0; i--)
#define rep1(i,a) for(int i=1; i<=a; i++)
#define cout1(a) cout << a << endl;
#define cout2(a,b) cout << a << " " << b << endl;
#define cout3(a,b,c) cout << a << " " << b << " " << c << endl;
#define cout4(a,b,c,d) cout << a << " " << b << " " << c << " " << d << endl;
#define mem(a,n) memset( a, n, sizeof(a))
#define all(a) a.begin(),a.end()
#define chmin(a,b) a=min(a,b);
#define chmax(a,b) a=max(a,b);

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<VV> VVV;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LLINF = 1e18;
static const double pi = 3.141592653589793;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int N;
    cin>>N;
    
    ll sum=0,mn=LLINF;
    rep(i,N){
        ll a,b; cin>>a>>b;
        sum+=a;
        if(a>b) chmin(mn,b);
    }
    if(mn==LLINF) mn=sum;
    cout1(sum-mn)
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
using ll = long long;
int main(){
    int N, K;
    cin >> N >> K;
    int A[100010];
    ll min = 1e9;
    for(int i = 0;i < N;i++){
        cin >> A[i];
        if(min > A[i])min = A[i];
    }
    int count = 0;
    for(int i = 0;i < N;i++){
        if(min == A[i])count++;
    }

    if((N - count) % (K - 1) == 0)cout << (N - count) / (K - 1);
    else cout << (N - count) / (K - 1) + 1;
}

Measured memory_bytes: 640
eval"N,M,A,*B,s=#{`tr ' 
' ,`}[d=x=0]*9e5
B.map{|b|e=b
A>b&&b+=M
x+=t=b-A
[0,M].map{|m|s[m-~A]+=1
s[m+b]-=t
s[m-~b]+=t-1}
A=e}
p x-s.map{d+=$.+=_1}.max"

Measured memory_bytes: 38452
#pragma warning disable

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Runtime.Serialization.Formatters.Binary;
using System.Text;
using System.Text.RegularExpressions;
using System.Diagnostics;
using System.Numerics;
using System.Collections;

static class MainClass
{
    public static void Main(string[] args)
    {
        var s = Console.ReadLine();
        var t = Console.ReadLine();

        var dp = new int[s.Length + 1, t.Length + 1];

        for (int i = 0; i < s.Length; i++)
        {
            for (int j = 0; j < t.Length; j++)
            {
                if (s[i] == t[j])
                {
                    dp[i + 1, j + 1] = dp[i, j] + 1;
                }
                else
                {
                    dp[i + 1, j + 1] = Math.Max(dp[i + 1, j], dp[i, j + 1]);
                }
            }
        }
        var lens = s.Length;
        var lent = t.Length;
        var ii = lens;
        var jj = lent;
        var sb = new StringBuilder();
        while (ii >= 0 && jj >= 0 && dp[ii,jj] != 0)
        {

            if (dp[ii, jj] == dp[ii - 1, jj - 1] + 1 && s[ii - 1] == t[jj-1])
            {
                sb.Append(s[ii - 1].ToString());
                ii--; jj--;
            }
            else
            {
                if (dp[ii, jj] == dp[ii - 1, jj - 1])    
                {
                    ii--;
                    jj--;
                }
                else if (dp[ii, jj] > dp[ii, jj - 1])
                {
                    ii--;
                }
                else
                {
                    jj--;
                }

                }
        }

        

        // Console.WriteLine(dp[s.Length,t.Length]);
        Console.WriteLine(new string(sb.ToString().Reverse().ToArray()));
        Console.ReadLine();
    }

    public static void PrintArray(int[,] array)
    {
        for (int i = 0; i < array.GetLength(0); i++)
        {
            for (int j = 0; j < array.GetLength(1); j++)
            {
                Console.Write(array[i, j] + " ");
            }
            Console.WriteLine();
        }
    }

    #region ライブラリ
    public static long ToInt64(this string str) => long.Parse(str);
    public static int ToInt32(this string str) => int.Parse(str);
    public static BigInteger ToBigInteger(this string str) => BigInteger.Parse(str);
    public static List<string> SplittedStringToList(this string str) => str.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).ToList();
    public static List<int> SplittedStringToInt32List(this string str) => str.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(x => int.Parse(x)).ToList();
    public static List<BigInteger> SplittedStringToBigInteger(this string str) => str.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(x => BigInteger.Parse(x)).ToList();
    public const int INF = int.MaxValue / 2;
    public const long LONGINF = long.MaxValue / 2;
    #endregion
}



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

using namespace std;

string s;

int main() {
    ios_base::sync_with_stdio(false);
    cin >> s;
    string t = s.substr(0,4);
    if (t == "YAKI") {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
/**********************************************
*
*  Author: wangyankai
*  Email: wangyk0517@gmail.com 
*  Filename: dp.cpp
*  Last modified: 2019-08-13 22:07:57
*
***********************************************/

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cstring>
#include <queue>
#include <map>
#include <set>
using namespace std;
const int maxn = 5e5 + 5;
vector<int> vec[maxn];
int book[maxn], dir[maxn], ok[maxn];
void dfs(int u, int fa)
{
    book[u] = 1;
    for(int i = 0; i < vec[u].size(); i++)
    {
        int v = vec[u][i];
        if(v == fa) continue;
        if(ok[v]) continue;
        if(book[v]) 
        {
            dir[u] ^= 1;
            printf("%d %d\n", u, v);
        }
        else dfs(v, u);
    }
    if(fa != -1)
    {
        ok[u] = 1;
        if(dir[u]) printf("%d %d\n", u, fa);
        else printf("%d %d\n", fa, u), dir[fa] ^= 1;
    }
}
int main(int argc,char **argv)
{
    int n, m, x, y;
    while(~scanf("%d%d", &n, &m))
    {
        memset(book, 0, sizeof(book));
        memset(ok, 0, sizeof(ok));
        memset(dir, 0, sizeof(dir));
        for(int i = 1; i <= m; i++)
        {
            scanf("%d%d", &x, &y);
            vec[x].push_back(y);
            vec[y].push_back(x);
        }
        if(m%2) puts("-1");
        else dfs(1, -1);
    }
    return 0;
}


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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif
const int MAX = 10000000;
long long fac[MAX], finv[MAX], inv[MAX];
bool initialized = false;

/**
 * @fn
 * This function must be called at first.
 */
void combination_init() {
    initialized = true;
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++) {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

/**
 * @fn
 * Calculates the combination  ( nCK % p: N choose K mod p).
 *
 * @brief constraint: 1 ≤ k ≤ n ≤ 10^7
 * @return nCK % MOD
 */
long long combination(int n, int k) {
    assert(initialized);
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

/**
 * @fn
 * Calculates the factorial of the number.
 *
 * @brief constraint: 1 ≤ k ≤ 10^7 and 1 ≤ n ≤ 10^9
 * @return N! % MOD
 */
long long factorial(int n) {
    assert(initialized);
    if (n < 0) return 0;
    return fac[n] % MOD;
}

/**
 * @fn
 * Calculates the combination ( nCK % p: N choose K mod p).
 *
 * @brief
 * @return nCK % MOD
 */
long long combination2(int n, int k) {
    assert(initialized);
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    ll res = 1;
    k = min(k, n - k);
    for (long long x = 1; x <= k; x++) {
        res *= (n - x + 1);
        res %= MOD;
        res *= inv[x];
        res %= MOD;
    }
    return res;
}

ll f(ll r, ll c) {
    return (combination(r + c + 2, r + 1) - 1) % MOD;
}


void Main() {
    ll r1, c1, r2, c2;
    cin >> r1 >> c1 >> r2 >> c2;
    combination_init();
    ll ans = f(r2, c2);
    ans -= f(r1 - 1, c2);
    ans %= MOD;
    if (ans < 0) ans += MOD;
    ans -= f(r2, c1 - 1);
    ans %= MOD;
    if (ans < 0) ans += MOD;
    ans += f(r1 - 1, c1 - 1);
    ans %= MOD;
    cout << ans << '\n';
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 234624
import java.io.BufferedReader;
import java.io.Closeable;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		try(final Scanner sc = new Scanner(System.in)){
			final int N = sc.nextInt();
			
			final String[] strs = new String[N];
			for(int i = 0; i < N; i++) {
				strs[i] = sc.next();
			}
			
			int count = 0;
			int BA = 0, _A = 0, B_ = 0;
			for(final String str : strs) {
				
				for(int i = 0; i < str.length(); i++) {
					if(str.startsWith("AB", i)) { count += 1; }
				}
				
				if(str.endsWith("A") && str.startsWith("B")) {
					BA += 1;
				}else if(str.endsWith("A")) {
					_A += 1;
				}else if(str.startsWith("B")) {
					B_ += 1;
				}
			}
			
			if(BA >= 1) {
				final int BA_ONLY = Math.max(0, BA - 1);
				if(B_ > 0 && _A > 0) {
					System.out.println(count + BA_ONLY + 2 + Math.min(_A - 1, B_ - 1));
				}else if(_A > 0) {
					System.out.println(count + BA_ONLY + 1 + Math.min(_A - 1, B_));
				}else if(B_ > 0){
					System.out.println(count + BA_ONLY + 1 + Math.min(_A, B_ - 1));
				}else {
					System.out.println(count + BA_ONLY + 0 + Math.min(_A, B_));
				}
			}else {
				System.out.println(count + 0 + 0 + Math.min(_A, B_));
			}
		}
	}

	public static class Scanner implements Closeable {
		private BufferedReader br;
		private StringTokenizer tok;

		public Scanner(InputStream is) throws IOException {
			br = new BufferedReader(new InputStreamReader(is));
		}

		private void getLine() throws IOException {
			while(!hasNext()){
				tok = new StringTokenizer(br.readLine());
			}
		}

		private boolean hasNext() {
			return tok != null && tok.hasMoreTokens();
		}

		public String next() throws IOException {
			getLine();
			return tok.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		public int[] nextIntArray(int n) throws IOException {
			final int[] ret = new int[n];
			for(int i = 0; i < n; i++){
				ret[i] = this.nextInt();
			}
			return ret;
		}

		public long[] nextLongArray(int n) throws IOException {
			final long[] ret = new long[n];
			for(int i = 0; i < n; i++){
				ret[i] = this.nextLong();
			}
			return ret;
		}

		public void close() throws IOException {
			br.close();
		}
	}
}

Measured memory_bytes: 26068
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>

using namespace std;

#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define REV(i,n) for(ll (i) = (n) - 1;(i) >= 0;--i)
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {REP(WW,n)cerr << v[WW] << ' ';cerr << endl;}
#define SHOW2d(v,WW,HH) {REP(W_,WW){REP(H_,HH)cerr << v[W_][H_] << ' ';cerr << endl;}}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 998244353

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

vector<ll> v(222222);
vector<vector<ll> > g(222222);
vector<ll> lis(222222, LLINF);
ll ans[222222];

void dfs(ll node, ll pre, ll ma){
	ll mp = lower_bound(ALL(lis), v[node]) - lis.begin();
	ll tmp = lis[mp];
	lis[mp] = v[node];
	ma = max(ma, mp);
	ans[node] = ma;
	REP(i, g[node].size()){
		ll aite = g[node][i];
		if(aite == pre)continue;
		dfs(aite, node, ma);
	}
	lis[mp] = tmp;
}

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

	ll n;cin >> n;
	REP(i, n)cin >> v[i];
	REP(i, n-1){
		ll a, b;cin >> a >> b;
		a--;b--;
		g[a].EB(b);
		g[b].EB(a);
	}

	dfs(0, -1, -1);
	REP(i, n)cout << ans[i]+1 << endl;

	return 0;
}


Measured memory_bytes: 34028