akhauriyash/Code-Regression huggingface dataset:
//header{{{
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>
#include <ext/pb_ds/trie_policy.hpp>
 
using namespace __gnu_pbds;
using namespace std;
 
#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) begin(x),end(x)
#define Fixed fixed << setprecision(12)
#define int int_fast64_t
using pii = pair<int,int>;
constexpr int INF  = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int mod1 = 1e9+7;
constexpr int mod2 = 998244353;
 
template <class Func>
class FixPoint : Func {
public:
    explicit constexpr FixPoint(Func&& f) noexcept : Func(forward<Func>(f)) {}
 
    template <class... Args>
    constexpr decltype(auto) operator()(Args&&... args) const {
        return Func::operator()(*this, std::forward<Args>(args)...);
    }
};
 
template <class Func>
static inline constexpr decltype(auto) makeFixPoint(Func&& f) noexcept {
    return FixPoint<Func>{forward<Func>(f)};
}
 
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }
 
template <class T> using min_heap = priority_queue<T,vector<T>,greater<T> >;
template <class T> using max_heap = priority_queue<T>;
template <class A, class B> using umap = unordered_map<A,B>;
template <class T> using Set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <class K, class V> using Umap = gp_hash_table<K, V>;
using Trie = trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update>;
 
inline int square(int a){ return a * a;}
inline int updiv(int a,int b){ return (a + b - 1) / b; }
 
constexpr int dx[] = {1,0,-1,0,1,1,-1,-1};
constexpr int dy[] = {0,-1,0,1,1,-1,-1,1};
//}}}

signed main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout.setf(ios_base::fixed);
    cout.precision(10);

    int s;
    cin >> s;

    vector<vector<int> > dp(s+1, vector<int>(s + 1));

    for(int i = 3; i <= s; ++i){
        dp[0][i] = 1;
    }

    for(int i = 0; i < s; ++i){
        for(int j = 0; j <= s; ++j){
            if(j + 3 > s) continue;
            (dp[i+1][j + 3] += dp[i][j]) %= mod1;
        }
        for(int j = 1; j <= s; ++j){
            (dp[i+1][j] += dp[i+1][j-1]) %= mod1;
        }
    }

    int res = 0;

    for(int i = 0; i < s; ++i){
        res += dp[i][s];
        res %= mod1;
    }

    cout << res << '\n';

    return 0;
}

Measured memory_bytes: 34496
#include <bits/stdc++.h>
#define int long long
#define mod (int)(1e9+7)
#define inf (int)(3e18+7)
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(v) v.begin(),v.end()
#define mkp make_pair
#define mkt make_tuple
#define prique(T) priority_queue<T,vector<T>,greater<T>>
#define vecunique(vec) sort(vec.begin(), vec.end());decltype(vec)::iterator result = std::unique(vec.begin(), vec.end());vec.erase(result, vec.end())
using namespace std;

bool prime(int x) {
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0)return false;
	}
	return x > 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x / gcd(x, y) * y;
}
int kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= i; res %= mod;
	}
	return res;
}
int mod_pow(int x, int y) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % mod;
		}
		x = x * x % mod;
		y >>= 1;
	}
	return res;
}
int comb(int x, int y) {
	if (y > x)return 0;
	return kai(x, y) * mod_pow(kai(y, y), mod - 2) % mod;
}
/*--------Library Zone!--------*/

int h, w;
char c[2005][2005];
int up[2005][2005], low[2005][2005], ri[2005][2005], le[2005][2005];
signed main() {
	cin >> h >> w;
	rep(i, h)rep(j, w)cin >> c[i][j];
	rep(i, w) {
		rep(j, h) {
			if (c[j][i] == '.') {
				up[j + 1][i] = up[j][i] + 1;
			}
		}
	}
	rep(i, w) {
		for (int j = h - 1; j > 0; j--) {
			if (c[j][i] == '.') {
				low[j - 1][i] = low[j][i] + 1;
			}
		}
	}
	rep(i, h) {
		rep(j, w) {
			if (c[i][j] == '.') {
				le[i][j + 1] = le[i][j] + 1;
			}
		}
	}
	rep(i, h) {
		for (int j = w - 1; j > 0; j--) {
			if (c[i][j] == '.') {
				ri[i][j - 1] = ri[i][j] + 1;
			}
		}
	}
	int ans = 0;
	rep(i, h) {
		rep(j, w) {
			if (c[i][j] == '#')continue;
			ans = max(ans, up[i][j] + low[i][j] + ri[i][j] + le[i][j] + 1);
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 129792
#include<cstdio>
#include<algorithm>
using namespace std;
int vis[101][101];
int main()
{
	int ans=0,i,j,n,k;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
		{
			if(vis[i][j] or vis[j][i] or j%2==i%2)continue;
			ans++;
			vis[i][j]=1;
		}
	printf("%d",ans);
	return 0;
 } 

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

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

  int C = 0;
  for (int i = 0; M > i ; i++){
      int A ;
      cin >> A;
      C = C + A ;
  }
  if( N - C >= 0){
  	cout << N - C << endl;
  }else{
  	cout << -1 << endl;
  }
  
}


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

int main(){
  while(1){
    string s;
    cin>>s;
    if(s=="-"){
      break;
    }
    int m;
    cin>>m;
    for(int i=0;i<m;i++){
      int h;
      cin>>h;
      s=s.substr(h)+s.substr(0,h);
    }
    cout<<s<<endl;
  }
  return 0;
}



Measured memory_bytes: 3152
#include <stdio.h>

#define N_MAX (100000)

int main(void)
{
	int flag[N_MAX];
	int n;
	int i, j;
	int d;
	int app[2];
	
	for (i = 0; i < N_MAX; i++){
		flag[i] = 1;
	}
	flag[0] = flag[1] = 0;
	
	while (scanf("%d", &n) != EOF){
		for (i = 2; i <= n; i++){
			if (flag[i]){
				for (j = i + i; j <= n + n; j += i){
					flag[j] = 0;
				}
			}
		}
		app[0] = app[1] = 0;
		d = 1;
		while (!app[0] || !app[1]){
			if (flag[n + d] && !app[0]){
				app[0] = n + d;
			}
			if (flag[n - d] && !app[1]){
				app[1] = n - d;
			}
			d++;
		}
		
		printf("%d %d\n", app[1], app[0]);
	}
	
	return (0);
}

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

int main(){
  int n,ans = 0;
  string t,s;

  cin >> n >> t;

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

    int k = 1;
    bool f = false;

    while(k<s.size()){
      for(int j=0;j<s.size();j++){
	bool match = true;
	for(int x=0;x<t.size();x++){
	  if(j+k*x>=s.size() || t[x] != s[j+k*x]){
	    match = false;
	    break;
	  }
	}
	if(match){
	  f = true;
	  ans++;
	  break;
	}
      }
      if(f)break;
      k++;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 1208
//code by lynmisakura.wish to be accepted!
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

int main(void){
	int n;cin >> n;
	vector<string> a(n);
	vector<int> t(n,0);
	for (int i = 0; i < n; ++i)
	{
		cin >> a[i];
		int T;cin >> T;
		if(i == 0)t[i] = T;
		else t[i] = t[i-1] + T;
	}
	map<string,int> m;
	for (int i = 0; i < n; ++i)
	{
		m[a[i]] = t[i];
	}
	string x;cin >> x;
	cout << t[n-1] - m[x] << endl;
	return 0;	
}


Measured memory_bytes: 256
class UnionFindTree
  def initialize(n)
    @size = Array.new(n + 1, 1)
    @rank = Array.new(n + 1, 0)
    @parent = []

    (0..n).each do |i|
      @parent[i] = i
    end
  end

  def find(x)
    if @parent[x] == x
      x
    else
      @parent[x] = find(@parent[x])
    end
  end

  def unite(x, y)
    x = find(x)
    y = find(y)
    return if x == y

    if @rank[x] < @rank[y]
      @parent[x] = y
      @size[y] += @size[x]
    else
      @parent[y] = x
      @size[x] += @size[y]

      @rank[x] += 1 if @rank[x] == @rank[y]
    end
  end

  def same?(x, y)
    find(x) == find(y)
  end

  def size(x)
    @size[find(x)]
  end
end

n, m = gets.chomp!.split(" ").map(&:to_i)
bridges = m.times.map do
  gets.split.map(&:to_i).map{ |i| i - 1 }
end

all = n * (n - 1) / 2
ans = [all]

uft = UnionFindTree.new(n - 1)
bridges.reverse.each do |bridge|
  unless uft.same?(bridge[0], bridge[1])
    ans << ans[-1] - uft.size(bridge[0]) * uft.size(bridge[1])
  else
    ans << ans[-1]
  end

  uft.unite(bridge[0], bridge[1])
end

puts ans[0..-2].reverse


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

using namespace std;

int main(){
  int n,t; cin >> n >> t;
  double x,h,ans=0;
  for(int i=0;i<n;++i) {
    cin>> x >> h;
    ans=max(h/x,ans);
  }

  printf("%.16f\n",ans*t);
  
  return 0;
}



Measured memory_bytes: 3296
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <map>
 
using namespace std;
const long long MAXN = 100100;
const long long MOD = 1e9 + 7;
vector<long long> v1[MAXN];
long long dp[MAXN][5];
void dfs(long long curr,long long par){
    dp[curr][0] = dp[curr][1] = 1;
    for(auto x:v1[curr]){
        if(x == par){
            continue;
        }
        dfs(x,curr);
        dp[curr][0]*=dp[x][1];
        dp[curr][0]%=MOD;
        dp[curr][1]*=(dp[x][1]+dp[x][0]);
        dp[curr][1]%=MOD;
    }
}
int main() {
   long long n;
   cin>>n;
   for(long long i=0;i<n-1;i++){
       long long x,y;
       cin>>x>>y;
       v1[x].push_back(y);
       v1[y].push_back(x);
       
   }
   dfs(1,1);
   cout<<(dp[1][0]+dp[1][1])%MOD<<endl;
}

Measured memory_bytes: 15232
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll mod = 10e9+7;

#define vec vector<int>
#define vecll vector<ll>
#define vpair vector<pair<int, int>>
#define vpairll vector<pair<ll, ll>>

#define rep(i,n)   for(int i=(int)0; i<(int)n; i++)
#define REP(i,m,n) for(int i=(int)m; i<(int)n; i++)
#define all(var)     (var).begin(), (var).end()
#define prt(var)     cout << var << endl
#define prtd(n, var)  cout << fixed << setprecision(n) << var << endl
#define prt2(var1, var2) cout << var1 << " " << var2 << endl

//----------------------------------------------------------------

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

  vpairll task(n);
  rep(i,n){
    ll a, b;
    cin >> a >> b;
    task[i] = make_pair(b, a);
  }

  sort(all(task));

  ll time=0;
  rep(i,n){
    time += task[i].second;
    if(time>task[i].first){
      prt("No"); return 0;
    }
  }

  prt("Yes");
}


Measured memory_bytes: 3328
import sys
sys.setrecursionlimit(10**5)
N = int(input())

def rec(num, use):
    if num > N:
        return 0

    i = 0
    if (use == 0b111):
        i = 1

    return rec(num*10+7, use | 0b100)\
         + rec(num*10+5, use | 0b010)\
         + rec(num*10+3, use | 0b001)\
         + i

print(rec(0,0))


Measured memory_bytes: 3060
#include<stdio.h>
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <vector>
#include <math.h>
#include<stack>
#include <queue>
#include<map>
#include <set>
#include<math.h>
using namespace std;
#define int long long
#define ll long long
#define rep(i,n) for(ll i=0;i<n;++i)
#define loop(i,m,n) for(ll i=m;i<n;++i)
#define ggr getchar(); getchar();return 0;
#define pie 3.141592653589793238462643383279
#define elif else if
#define P pair<ll,ll>
const int inf = 1000000007;
int bin(int bina) {
	int ans = 0;
	for (int i = 0; bina > 0; i++)
	{
		ans = ans + (bina % 2) * pow(10, i);
		bina = bina / 2;
	}
	return ans;
}
bool prime(int n) {
	for (ll i = 2; i <= sqrt(n); i++) {
		if (n % i == 0)return false;
	}
	return n != 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x * y / gcd(x, y);
}
int kai(int x) {
	if (x == 0)return 1;
	return kai(x - 1) * x % inf;
}
int mod_pow(int x, int y, int mod) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % mod;
		}
		x = x * x % mod;
		y >>= 1;
	}
	return res;
}
int comb(int x, int y) {
	return kai(x)* mod_pow(kai(x - y), inf - 2, inf) % inf * mod_pow(kai(y), inf - 2, inf) % inf;
}
struct union_find {
	int par[200010], size_[200010];
	void init(int x) {
		rep(i, x) { par[i] = i; size_[i] = 1; }
	}
	int find(int x) {
		if (par[x] == x)return x;
		return par[x] = find(par[x]);
	}
	void unite(int x, int y) {
		x = find(x); y = find(y);
		if (x == y)return;
		if (size_[x] < size_[y]) {
			par[x] = y;
			size_[y] += size_[x];
		}
		else {
			par[y] = x;
			size_[x] += size_[y];
		}
	}
};
union_find iwa;
signed main() {	
	int n, m;
	cin >> n >> m;
	iwa.init(n);
	rep(i, m) {
		int a, b, c;
		cin >> a >> b >> c;
		iwa.unite(a - 1, b - 1);
	}
	set<int>st;
	rep(i, n) {
		st.insert(iwa.find(i));
	}
	cout << st.size() << endl;
}


Measured memory_bytes: 6528
import * as fs from "fs";

let input = (fs.readFileSync("/dev/stdin", "utf8") as string).split("\n");
const s = input[0];
let c = s[0];
let result = 0;
for(let i=0; i<s.length;i++){
	if(c!==s[i]){
		result += 1;
		c = s[i];
	}
}

console.log(result);


Measured memory_bytes: 7500
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n,k = map(int,readline().split())
lst1 = list(map(int,readline().split()))

ans = 0
for a in range(n+1):
    for b in range(n+1):
        if a+b > min(n,k):
            continue
        left = lst1[:a]
        right = lst1[n-b:]
        res = left + right
        rest = k - (a + b)
        if rest > 0:
            res.sort()
            while rest:
                if len(res) == 0:
                    break
                if res[0] < 0:
                    del res[0]
                    rest -=1
                else:
                    break
        ans = max(ans,sum(res))

print(ans)



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

int main(){
	int A, B, C;
	cin >> A >> B >> C;
	if (A == B){
		if (A != C) cout << "Yes" << endl;
		else cout << "No" << endl;
	}else if (A == C) cout << "Yes" << endl;
	else if (B == C) cout << "Yes" << endl;
	else cout << "No" << endl;
}


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

string s;
int se[4] = {};

int main() {
	cin >> s;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == 'N') {
			se[0]++;
		}
		else if (s[i] == 'W') {
			se[1]++;
		}
		else if (s[i] == 'S') {
			se[2]++;
		}
		else {
			se[3]++;
		}
	}
	if (se[0] == 0 && se[2] != 0 || se[2] == 0 && se[0] != 0) {
		cout << "No" << endl;
		return 0;
	}
	if (se[1] == 0 && se[3] != 0 || se[3] == 0 && se[1] != 0) {
		cout << "No" << endl;
		return 0;
	}
	cout << "Yes" << endl;
	return 0;
}

Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Jaynil
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        ACircle solver = new ACircle();
        solver.solve(1, in, out);
        out.close();
    }

    static class ACircle {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int r = in.nextInt();
            out.println(r * r);
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

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

    }
}



Measured memory_bytes: 21460
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
#define fr first
#define sc second
#define pb push_back
#define mpr make_pair
#define pop_back()
#define sz(x) int(x.size())
#define all(x) x.begin(), x.end()
#define lb lower_bound
#define ub upper_bound
#define ins insert
const int N = 3e5 + 1, n2 = 5001, mod = 1e9 + 7, n3 = 501;
int n, cnt;
string s, t;
int main()
{
    ios_base :: sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> s >> t;
    for(int i = 1;i <= n; ++ i){
        if(s.substr(n - i, i) == t.substr(0, i)){
            cnt = i;
        }
    }
    cout << 2 * n - cnt;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main()
{

int a[10000], min, max, n, i;
long long sum = 0;
scanf("%d", &n);//1以上が入力されるものとします
for(i = 0; i < n; i++){
scanf("%d", &a[i]);
sum += a[i];
}
max = min = a[0];//とりあえず最初の要素をセットしておく
for(i = 1; i < n; i++){//2番目以降の要素と比較
if(a[i] > max)max = a[i];
if(a[i] < min)min = a[i];
}
printf("%d %d %lld\n", min, max, sum);

return 0;
}


Measured memory_bytes: 2796
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(a,b) for(int a=0;a<b;a++)
#define repd(a,b) for(int a=b;a>=0;a--)
signed main()
{
    int x,y,a,b,c;
    cin>>x>>y>>a>>b>>c;
    int r[a],g[b],cl[c];
    rep(i,a)
    {
        cin>>r[i];
    }
    rep(i,b)
    {
        cin>>g[i];
    }
    rep(i,c)
    {
        cin>>cl[i];
    }
    sort(r,r+a,greater<int>());
    sort(g,g+b,greater<int>());
    sort(cl,cl+c,greater<int>());
    int ans[x+y];
    rep(i,a)
    {
        if(i<x)
        {
            ans[i]=r[i];
        }
        else
        {
            break;
        }
        
    }
    rep(i,b)
    {
        if(i<y)
        {
            ans[x+i]=g[i];
        }
    }
    sort(ans,ans+x+y);
    int i=0;
    while(ans[i]<cl[i]&&i<c&&i<(x+y))
    {
        ans[i]=cl[i];
        i++;
    }
    int sum=0;
    rep(i,x+y)
    {
        sum+=ans[i];
    }
    cout<<sum<<"\n";
    
    
}

Measured memory_bytes: 3968
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define INF 0x6fffffff
#define INFL 0x6fffffffffffffffLL

int main() {
	ll		a,b,c,h,i,j,k,l,m,n,x,y;
	ll		ans = 0;
	string	s;
	cin >> n >> k;
	vector<ll>	aa(n);
	for(i=0;i<n;i++) cin >> aa[i];

	for(i=0;i<n;i++) {
		a = abs(k-aa[i]);
		b = aa[i];
		ans += min(a,b) * 2;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
int main(){
    double n, i;
    double xa , ya, ra, xb, yb, rb;
    double d;
    scanf("%lf",&n);
    for (i = 0; i < n; i++) {
        scanf("%lf %lf %lf %lf %lf %lf", &xa, &ya, &ra, &xb, &yb, &rb);
         d =sqrt(pow((xa-xb),2)+pow(ya-yb, 2));
        if (ra >= rb && (ra - rb) > d) {
            printf("%d\n",2);
        }
        else if (rb >= ra && (rb - ra) > d) {
            printf("%d\n",-2);
        }
        else if (d <= (ra + rb) ){
            printf("%d\n",1);
        }
        else {
            printf("%d\n",0);
        }
    }
    return (0);
}

Measured memory_bytes: 632
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i,n) for (int i = 0; i < (n); ++i)
int main() {
    int a, b;
    cin >> a >> b;
    int tmp_max;
    tmp_max = max(a+b, a*b);
    cout << max(a-b, tmp_max) << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<string>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long int ll;
typedef vector<pair<ll,ll> > Q;
typedef pair<int,int> P;
#define rep(i,n) for(int i=0;i<(int)(n);i++)


int par[1000000];//親
int ran[200000]; //木の深さ


struct unionfind
{

unionfind(int n) //初期化
{
  rep(i,n)
  {
    par[i]=i;
    ran[i]=0;
  }
}

int root(int x) //木の根を求める
{
  if(par[x]==x) return x;
  else return par[x]=root(par[x]);
}

void unite(int x,int y) //xとyの属する集合を併合
{
  x=root(x);
  y=root(y);
  if(x==y) return;

  if(ran[x]<ran[y]) par[x]=y;
  else
  {
    par[y]=x;
    if(ran[x]==ran[y]) ran[x]++;
  }
}

bool same(int x,int y) //xとyが同じ集合に属するのか
{
    return root(x)==root(y);
}

};


int main()
{
  int n,m;
  cin>>n>>m;
  int p[n];
  rep(i,n) cin>>p[i];

  unionfind tree(n);

  rep(i,m)
  {
    int x,y;
    cin>>x>>y;
    tree.unite(x-1,y-1);
  }

  int cnt=0;
  rep(i,n)
  {
    if(tree.same(i,p[i]-1)) cnt++;
  }

  cout<<cnt<<endl;

}

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

int main() {
  int N, i, y;
  string S;
  cin >> N;
  y = 0;

  for (i = 0; i < N; i++){
    cin >> S;
    if (S == "Y") y += 1;
  }
  
  if (y != 0) cout << "Four" << endl;
  else cout << "Three" << endl;
}

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

int main(){
	int n;
	cin >> n;
	vector<int> len(n);
	vector<char> d(n);
	vector<pair<int, int> > shorter(n);
	for(int i=0; i<n; i++){
		cin >> d[i] >> len[i];
		shorter[i] = make_pair(len[i], i);
	}
	sort(shorter.begin(), shorter.end());

	int ans = 0;
	for(int i=0; i<n; i++){
		int curr = shorter[i].second;
		if(d[curr] != 'y') continue;
		for(int j=curr; j>=0; j--){
			if(d[j]=='n' && len[j] >= len[curr]) break;
			if(d[j]=='y' && len[j] >= len[curr]) d[j] = 'e';
		}
		for(int j=curr; j<n; j++){
			if(d[j]=='n' && len[j] >= len[curr]) break;
			if(d[j]=='y' && len[j] >= len[curr]) d[j] = 'e';
		}
		ans++;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3140
import java.util.*;

class Main {
	public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int N = Integer.parseInt(sc.next());
      List<Integer> list = new ArrayList<>();
      
      for (int i = 0; i < N; ++i) {
        list.add(Integer.parseInt(sc.next()));
      }
      
      list.sort(Comparator.comparing(Integer::intValue));
      
      int result = 0;
      
      for (int i = 0; i < N - 2; ++i) {
        for (int j = i + 1; j < N - 1; ++j) {
          for (int k = j + 1; k < N; ++k) {
            if (list.get(k) < list.get(i) + list.get(j)) result++;
            else break;
          }
        }
      }
      
      
      System.out.println(result);
    }
}

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

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repr(i, n) for(int i = (int)(n); i >= 0; i--)
#define repm(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define repmr(i, m, n) for(int i = (int)(n); i >= (int)(m); i--)
#define all(x) (x).begin(),(x).end()
#define inf 2e9
#define MOD 1000000007

using namespace std;
typedef long long int lli;
typedef long long ll;

int main(){
    int n; cin >> n;
    vector<int> p(n); rep(i,n) cin >> p[i];

    int max_product = 0;
    int sum = 0;
    rep(i,n){
        max_product = max(max_product,p[i]);
        sum += p[i];
    }

    int ans = sum - max_product/2;

    cout << ans << endl;
}


Measured memory_bytes: 256
//nani?
#include<bits/stdc++.h>
#define pi acos(-1);
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define f(i,a,b) for( int i = a; i < b ; i++ ) 
#define sor(a) sort( a.begin(), a.end() )
#define rsor(a) sort( a.rbegin(), a.rend() )
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
//#define inf 1LL<<62
typedef long long ll;
typedef double ld;
using namespace std;
const ll inf=1e9;
const ll MOD=1e9+7;
// ac cmtr;
const ll MAX_N = 1e5;
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cerr << name << " : " << arg1 << endl;}
 
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << " : " << arg1<<" | ";
  __f(comma+1, args...);}
#else
#define trace(...)
#endif
//---------------------------

ll dp[100005];

int main(){
    fastio;
    ll n;
    cin>>n;
    vector <ll> v;
    f(i,0,n){
        ll num;
        cin>>num;
        v.pb(num);
    }
    dp[0]=0;
    dp[1]=abs(v[1]-v[0]);
    f(i,2,n){
        //cout<<dp[i-1]+abs(v[i]-v[i-1])<<" "<<dp[i-2]+abs(v[i]-v[i-2])<<endl;
        dp[i]=min(dp[i-1]+abs(v[i]-v[i-1]),dp[i-2]+abs(v[i]-v[i-2]));
    }
    cout<<dp[n-1]<<endl;




    return 0;
}   



Measured memory_bytes: 1908
package main

import "fmt"

type submit struct {
	number int
	result string
}

type score struct {
	acNum int
	waNum int
}

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

	submits := make([]submit, m)
	for i, s := range submits {
		fmt.Scan(&s.number, &s.result)
		s.number--
		submits[i] = s
	}
	ac, wa := cal(submits, n)
	fmt.Println(ac, wa)
}

func cal(submits []submit, n int) (int, int) {
	accepts := make([]bool, n)
	warongs := make([]int, n)
	cntAC, cntWA := 0, 0

	for _, submit := range submits {
		if accepts[submit.number] != true {
			if submit.result == "AC" {
				accepts[submit.number] = true
				cntAC++
				cntWA += warongs[submit.number]
			}
			if submit.result == "WA" {
				warongs[submit.number]++
			}
		}
	}

	return cntAC, cntWA
}


Measured memory_bytes: 6656
#include<stdio.h>
#include<ctype.h>

int main(){
	char mozi[1200];
	int i=0;
	
	fgets(mozi,sizeof(mozi),stdin);
	while(mozi[i]!='\0'){
		if(isupper(mozi[i])){
			mozi[i]=tolower(mozi[i]);
		}
		else if(islower(mozi[i])){
			mozi[i]=toupper(mozi[i]);
		}
		printf("%c",mozi[i]);
		i++;
	}
	
	return 0;
}

Measured memory_bytes: 524
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1000000007;
//cout << setprecision(20) << 

int main() {
    ll N, M; cin >> N >> M;
    vector<pair<ll, ll>> v(N);
    for (int i = 0; i < N; ++i) {
        ll a, b; cin >> a >> b;
        v[i] = make_pair(a, b);
    }
    sort(v.begin(), v.end());

    ll count = 0;
    ll sum = 0;
    for (auto i: v) {
        if (count + i.second < M) {
            count += i.second;
            sum += i.first * i.second;
        }
        else {
            if (count < M) {
                sum += i.first * (M - count);
                count += i.second;
            }
        }
    }
    cout << sum << endl;
}

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

#define ll long long int
#define All(a) (a).begin(),(a).end()

// Remember v.shrink_to_fit() when erasing

void solve(){
  ll n,m;
  scanf("%lld",&n);
  if(n==1)printf("0");
  else
  {
    printf("1");
  }
  
  // for(int i=0;i<n;i++){

  //   scanf("%d",&A[i]);
  // }

}
int main(){
  solve();
  return 0;
}

Measured memory_bytes: 3652
a=list(map(int,input().split()))
n=1
zahyo=0
hane=list(map(int,input().split()))
for i in range(a[0]):
    if zahyo+hane[i]>a[1]:
        break
    else:
        zahyo=zahyo+hane[i]
        n=n+1
print(n)

Measured memory_bytes: 2940
#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 lower[3] = {0, 10, 100};
int upper[3] = {9, 99, 999};

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M; cin >> N >> M;
    int s[5], c[5];
    rep(i, M) cin >> s[i] >> c[i];
    REP(i, lower[N - 1], upper[N - 1]) {
        string S = to_string(i);
        //cout << S << endl;
        bool ok = true;
        rep(j, M) {
            if(S[s[j] - 1] != c[j] + '0') ok = false;
        }
        if(ok) {
            cout << i << endl;
            return 0;
        }
    }
    cout << -1 << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std; 
const int maxn = 200500;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    string s, t;
    int n;
    cin >> n;
    cin >> s >> t;
    for(int i = 0 ; i < n ; ++i)
        cout << s[i] << t[i];
    return 0;
}


Measured memory_bytes: 256
import bisect
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))

a.sort()
c.sort()

ans=0
for i in b:
  x=bisect.bisect_left(a,i)
  y=n-bisect.bisect_right(c,i)
  ans+=x*y
print(ans)

Measured memory_bytes: 23360
#![allow(unused_macros)]
#![allow(dead_code)]
#![allow(unused_imports)]

use text_io::*;

const U_INF: usize = 1 << 60;
const I_INF: isize = 1 << 60;

fn main() {
    let n: usize = read!();
    let mut values = Vec::with_capacity(n);
    let mut costs = Vec::with_capacity(n);
    for _ in 0..n {
        let v: usize = read!();
        values.push(v);
    }
    for _ in 0..n {
        let c: usize = read!();
        costs.push(c);
    }

    let ans = values
        .iter()
        .zip(costs.iter())
        .filter(|(v, c)| v > c)
        .map(|(v, c)| v - c)
        .sum::<usize>();
    println!("{}", ans);
}


Measured memory_bytes: 2164
import java.lang.reflect.Array;
import java.util.*;
import java.util.List;

public class Main {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        // height: index
        int n = scan.nextInt();
        int[] hs = new int[n];
        boolean[] hasNei = new boolean[n];
        Arrays.fill(hasNei, false);
        boolean[] isBad = new boolean[n];
        Arrays.fill(isBad, false);
        int nEdge = scan.nextInt();
        for (int i = 0; i < n; i++) {
            hs[i] = scan.nextInt();
        }
        for (int i = 0; i < nEdge; i++) {
            int l = scan.nextInt();
            int r = scan.nextInt();
            hasNei[l - 1] = true;
            hasNei[r - 1] = true;
            if (hs[l - 1] >= hs[r - 1]) {
                isBad[r - 1] = true;
            }
            if (hs[l - 1] <= hs[r - 1]) {
                isBad[l - 1] = true;
            }

        }
        scan.close();
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (!hasNei[i]) {
                cnt++;
                continue;
            }

            if (!isBad[i]) {
                cnt++;
            }
        }

        System.out.println(cnt);
    }
}





Measured memory_bytes: 59680
N = gets.to_i
As, Bs = readlines.map{_1.split.map(&:to_i)}.transpose

m = ->(a){a.sort!; l = a.size; l.even? ? a[l/2 - 1, 2].sum/2r : a[(l - 1)/2]}
puts m[As].step(m[Bs], N.even? ? 1/2r: 1).size

Measured memory_bytes: 44196
N, M, X, Y = list(map(int, input().split()))
x = list(map(int, input().split()))
y = list(map(int, input().split()))

if X+1>Y:
    print("War")
else:
    if (max(x)+1) > min(y):
        print("War")
    else:
        if X +1 <= min(y) and Y >= max(x)+1:
            print("No War")
        else:
            print("War")

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
using namespace std;
typedef long long ll;
int INF = (1LL << 30) - 1;
int MOD = 1e9+7;
main(){
    string S;
    cin >> S;
    vector<int> idx(26, -INF);
    rep(i,0,S.size()){
        if(i - idx[S[i] - 'a'] <= 2){
            cout << idx[S[i] - 'a'] + 1<< " " << i + 1 << endl;
            return 0;
        }
        idx[S[i] - 'a'] = i;
    }
    cout << "-1 -1" << endl;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
typedef long long ll;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int,int>;
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*b/gcd(a,b);}
ll MOD=1000000007;

int main(){
  int x,y,z;cin>>x>>y>>z;
  cout<<z<<' '<<x<<' '<<y<<endl;
}

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

int main(){
    int N; cin >> N;
    vector<ll> A(N);
    for(int i = 0; i < N; i++) cin >> A[i];
    vector<ll> left(N), right(N);
    for(int i = 1; i < N; i++){
        if(i == 1){
            left[i] = A[0];
            right[N-i-1] = A[N-1];
        }
        else{
            left[i] = __gcd(left[i-1], A[i-1]);
            right[N-i-1] = __gcd(right[N-1 -(i-1)], A[N-i]);
        }
    }
    ll MAX = 0;
    for(int i = 0; i < N; i++){
        if(i == 0) MAX = max(right[i],MAX);
        else if(i == N - 1) MAX = max(left[i],MAX);
        else MAX = max(MAX, __gcd(left[i],right[i]));
    }
    cout << MAX << endl; 
}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
#define line cout<<endl;
#define space cout<<" ";
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef long long int ll;

using namespace std;

const int N = 1e9+7;





int main()
{
    int n,k;
    cin>>n>>k;
    int sum  = 0;
    vector<int> v(n);

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

    sort(v.begin(),v.end());

    for(int i=0;i<k;i++)
    {
        sum = sum+v[i];
    }
    cout<<sum;
}



Measured memory_bytes: 3624
#include<stdio.h>
int main(void){
  int n;
  long long ans=0;
  scanf("%d",&n);
  int d[n];
  for(int i=0;i<n;i++){
    scanf("%d",&d[i]);
  }
  for(int i=0;i<n;++i){
  	for(int j=i+1;j<n;j++){
		ans+=d[i]*d[j];
   	}
  }
  printf("%lld",ans);
  return(0);
}


Measured memory_bytes: 128
X,Y,Z,K=map(int,input().split())
A=[int(x) for x in input().split()]
A.sort(reverse=True)
B=[int(x) for x in input().split()]
B.sort(reverse=True)
C=[int(x) for x in input().split()]
C.sort(reverse=True)
D=[a+b for a in A for b in B]
D.sort(reverse=True)
D=D[:3000]
E=[ab+c for ab in D for c in C]
E.sort(reverse=True)
for i in range(K):
  print(E[i])


Measured memory_bytes: 160016
import java.awt.Point;
import java.awt.geom.Line2D;
import java.awt.geom.Point2D;
import java.util.*;

public class Main {	
	Scanner in = new Scanner(System.in);
	public static void main(String[] args){
		new Main();
	}
	public Main(){
		new AOJ1147();
	}
	class AOJ1147{
		public AOJ1147() {
			while (true) {
				int n = in.nextInt();
				if(n==0)break;
				int sum = 0;
				int max = -999;
				int min = Integer.MAX_VALUE/2;
				for(int i=0;i<n;i++){
					int input = in.nextInt();
					sum+=input;
					max = Math.max(max,input);
					min = Math.min(min,input);
				}
				sum-=max;sum-=min;
				n-=2;
				System.out.println(sum/n);
			}
			
		}
	}
}

Measured memory_bytes: 20940
readlines.each do |l|
	x1,y1,x2,y2,x3,y3,xp,yp = l.split.map(&:to_f)
	z1=(x3-x2)*(yp-y2)-(y3-y2)*(xp-x2)
	z2=(x1-x3)*(yp-y3)-(y1-y3)*(xp-x3)
	z3=(x2-x1)*(yp-y1)-(y2-y1)*(xp-x1)

	if (z1>0 && z2>0 && z3>0) || (z1<0 && z2<0 && z3<0) then
		print "YES\n"
	else
		print "NO\n"
	end
end

Measured memory_bytes: 6128
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;
using static System.Math;
using static System.Array;
using static AtCoder.Tool;

namespace AtCoder
{
    class AC
    {
        const int mod = 1000000007;
        const int INF = int.MaxValue / 2;
        const long SINF = long.MaxValue / 2;


        static void Main(string[] args)
        {
            //var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            //Console.SetOut(sw);
            Solve();
            //Console.Out.Flush();
        }
        static void Solve()
        {
            var cin = new Scanner();
            int N = int.Parse(Console.ReadLine());
            long[] A = new long[N];
            for(var i = 0; i < N; i++)
            {
                A[i] = long.Parse(Console.ReadLine());
            }
            long ans = 0;
            if (N == 1)
            {
                Console.WriteLine(A[0] == 0 ? 0 : -1);
            }
            else
            {
                if (A[0] != 0)
                {
                    Console.WriteLine(-1);
                    return;
                }
                for(var i = 1; i < N; i++)
                {
                    if (A[i] == A[i - 1] + 1)
                    {
                        ans++;
                    }
                    else if (A[i] <= A[i - 1])
                    {
                        ans += A[i];
                    }
                    else
                    {
                        ans = -1;
                        break;
                    }
                }
                Console.WriteLine(ans);
            }

        }

    }

    public class Scanner
    {
        public int[] SplitReader()
        {
            int[] array = Console.ReadLine().Split().Select(int.Parse).ToArray();
            return array;
        }
        public long[] SplitReaderL()
        {
            long[] array = Console.ReadLine().Split().Select(long.Parse).ToArray();
            return array;
        }
    }

    public static class Tool
    {
        static public void Initialize<T>(ref T[] array, T initialvalue)
        {
            for(var i = 0; i < array.Length; i++)
            {
                array[i] = initialvalue;
            }
        }
        static public long ModuloP(long value,long mod)
        {
            long r = value % mod;
            
            if (r * mod < 0)
            {
                r += mod;
            }
            return r;
        }

    }

    struct Pair<T> : IComparable<Pair<T>> where T : IComparable<T>
    {
        public T variable;
        public int index;

        public Pair(T val, int i)
        {
            variable = val;
            index = i;
        }

        public int CompareTo(Pair<T> otherPair)
        {
            return variable.CompareTo(otherPair.variable);
        }

        public int CompareIndex(Pair<T> otherPair)
        {
            return index.CompareTo(otherPair.index);
        }
    }


}






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

int main(){
  int A,B,C,X;
  cin >> A;//500円
  cin >> B;//100円
  cin >> C;//50円
  cin >> X;

  int count=0;
  
  for(int i=0; i<C+1; i++){
    for(int j=0; j<B+1; j++){
      for(int k=0; k<A+1; k++){
        if(500*k+100*j+50*i==X){
          count++;
        }
      }
    }
  }
  cout << count << endl;
}

Measured memory_bytes: 256
def max_benefit(num_list):
    max_num = 10**9*-1
    min_num = num_list[0]

    for i in range(1,len(num_list)):
        max_num = max(max_num,num_list[i]-min_num)
        min_num = min(num_list[i],min_num)
    return max_num

n = int(input())
num_list = []
for _ in range(n):
    num_list.append(int(input()))

ans = max_benefit(num_list)
print(ans)


Measured memory_bytes: 13588
#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;
    int n;
    cin>> n>>s;
    for(int i=0; i<s.length(); ++i) {
            s[i]+=n;
            if(s[i]>'Z') s[i]-=26;
    }
    cout<<s;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i,a,b) for(ut i=(a);i<(ut)(b);i++)
#define REP(i,b) FOR(i,0,b)
#define ALL(c) c.begin(),c.end()
#define PB push_back
#define cat //cout << __LINE__ << endl;
using namespace std;
typedef long long LL;
typedef double ld;
typedef int ut;
typedef complex<int> cli;
typedef vector<ut> VI;
typedef pair<ut,ut> pr;
typedef pair<ut,pr> ppr;
typedef vector<pr> Vpr;
typedef vector<ppr> Vppr;
typedef priority_queue<pr,Vpr> PQ;

int main(){
	int K,T,x;
	cin >> K >> T;
	int maxim=0;
	REP(i,T){
		cin >> x;
		maxim=max(maxim,x);
	}
	cout << max(maxim-(K-maxim+1),0) << endl;

	return 0;
}

Measured memory_bytes: 256
N,A,B,C=map(int,input().split())
L=[int(input()) for i in range(N)]
def f(X):
  global N,A,B,C,L
  if len(X)==N:
    a,b,c=0,0,0
    for i in range(N):
      a+=X[i][0]
      b+=X[i][1]
      c+=X[i][2]
    if min(a,b,c)==0:
      return 10**16
    else:
      return abs(A-a)+abs(B-b)+abs(C-c)
  return min(f(X+[[0,0,0]]),f(X+[[L[len(X)],0,0]])+10,f(X+[[0,L[len(X)],0]])+10,f(X+[[0,0,L[len(X)]]])+10)

print(f([])-30)

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

int main()
{
    int A, B, C;
    cin >> A >> B >> C;
    if(A==B&&B==C){
        cout << "No" << endl;
    }
    else if(A!=B&&B!=C&&A!=C){
        cout << "No" << endl;
    }
    else{
        cout << "Yes" << endl;
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <climits>
#include <sstream>
#include <bitset>
#include <queue>

using namespace std;

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

    if(x < 1200) cout << "ABC" << endl;
    else cout << "ARC" << endl;

    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(){
    while(1){
    int H,W,i,j;
    scanf("%d%d",&H,&W);
        if(H==0&&W==0)
        break;
        for(i=0;i<H;i++)
        {
            for(j=0;j<W;j++)
            {
				if((i + j )%2 == 0 )
                printf("#");
				else
				printf(".");
             }
            printf("\n");
        }
        printf("\n");
         
         
    }
return 0;
}


Measured memory_bytes: 2104
r, m = [int(i) for i in input().split()]
l = []
r = []
for i in range(m):
    lx, rx = [int(j) for j in input().split()]
    l.append(lx)
    r.append(rx)
ans = max(0, min(r) - max(l) + 1)
print(ans)

Measured memory_bytes: 10996
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define rng(a) a.begin(), a.end()
#define ina(n,a) cin >> n; for(int i = 1; i <= n; i++) cin >> a[i]
#define sz(x) (int)(x).size()
#define se second
#define fi first
#define prev            coyhhhhhhyoc    
#define next          sdNNNmNNNNNNNmds  
#define y0           hNNNNy_yNNNNNN_sNh
#define y1          mNNNNNdtdNNNNNNtsNNm
#define yn          mNNNNNNNNy___smNNNms
#define tm            oooooosyysooooot 
#define read               tyhyt        
#define rank              ytmNmo         
#define index              yyy
#define pb push_back
#define pcnt __builtin_popcountll
#define rrep(i,a,b) for(int i = (b); i >= (a); i--)
#define rall(x,a) for(auto x : a)
#define MOD 1000000007
#define endl "\n"
typedef long long ll;
using namespace std;

const int N = 16;
vector<pair<int, int> > test[N];
int n, m;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    rep(i, 1, n) {
        cin >> m;
        rep(j, 1, m) {
            int x, y;
            cin >> x >> y;
            test[i].pb(make_pair(x, y));
        }
    }
    int ans = 0;
    rep(mask, 0, (1 << n) - 1) {
        bool ok = true;
        rep(i, 1, n) {
            if(mask & (1 << (i - 1))) {
                rall(p, test[i]) {
                    bool hon = mask & (1 << (p.fi - 1));
                    if(hon != p.se) {
                        ok = false;
                    }
                }
            }
        }
        if(ok) {
            ans = max(ans, pcnt(mask));
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
import numpy as np

N , W = map(int,input().split())
dp = np.full(N * 1000 + 1,W + 1)
dp[0] = 0

for i in range(N):
  w,v = map(int,input().split())
  dp[v:] = np.minimum(dp[v:],dp[:-v] + w)

print(np.max(np.where(dp <= W)))

Measured memory_bytes: 16832
s=list(input())
t=list(input())
start=[-1]*26
goal=[-1]*26
for i in range(len(s)):
    a=ord(s[i])-ord("a")
    b=ord(t[i])-ord("a")

    if start[a]!=-1 or goal[b]!=-1:
        if start[a]!=b or goal[b]!=a:
            print("No")
            exit()

    start[a]=b
    goal[b]=a
print("Yes")


Measured memory_bytes: 6704
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 1000000010
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
	int x=0,f=1;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
ll n,ans;
signed main()
{
	cin>>n;
	for (ll i=1;i*i<=n;i++)
	if (n%i==0)
	{
		if ((i-1)*(n/i+1)>n) ans+=i-1;
		if (i*i!=n) if ((n/i-1)*(i+1)>n) ans+=n/i-1;
	}
	cout<<ans;
	return 0;
	//NOTICE LONG LONG!!!!!
}
//[n/m]=n%m
//n=km+x
//k=n-km (n-km<m)
//k+km=n
//k(m+1)=n
//n<m+km m(k+1)>n

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

int main() {
  int K, E, O; cin >> K;

  E = O = 0;

  for(int i=1; i<=K; ++i) {
    if(i%2 == 0) ++E;
    else         ++O;
  }

  cout << E*O << "\n";
}


Measured memory_bytes: 256
import java.util.*;

public class Main {

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

        int min = Integer.MAX_VALUE;
        for (int x = 1; x <= n; x++) {
            int y = n - x;
            if (y <= 0) continue;

            int tmpMin = sumDigits(x) + sumDigits(y);
            if (tmpMin < min) min = tmpMin;
        }

        System.out.println(min);
    }

    private static int sumDigits(int number) {
        int sum = 0;

        while (number > 0) {
            sum = sum + (number % 10);
            number /= 10;
        }

        return sum;
    }
}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define mod 1000000007ll
#define mod1 998244353ll
#define endl "\n"
#define inf (ll)1e18+1
using namespace std::chrono;

ll ar[20][20];

ll solve(ll h,ll w,ll xi,ll yi){
    ll dis[h][w];
    for(ll x=0;x<h;x++){
        for(ll y=0;y<w;y++){
            dis[x][y]=inf;
        }
    }
    dis[xi][yi]=0;
    queue<pair<ll,ll>> q;
    q.push({xi,yi});
    while(!q.empty()){
        auto pa=q.front();
        q.pop();
        ll x=pa.first;
        ll y=pa.second;
        if(y-1>=0 && ar[x][y-1]==1){
            if(dis[x][y-1]>dis[x][y]+1){
                dis[x][y-1]=dis[x][y]+1;
                q.push({x,y-1});
            }
        }
        if(y+1<w && ar[x][y+1]==1){
            if(dis[x][y+1]>dis[x][y]+1){
                dis[x][y+1]=dis[x][y]+1;
                q.push({x,y+1});
            }
        }
        if(x-1>=0 && ar[x-1][y]==1){
            if(dis[x-1][y]>dis[x][y]+1){
                dis[x-1][y]=dis[x][y]+1;
                q.push({x-1,y});
            }
        }
        if(x+1<h && ar[x+1][y]==1){
            if(dis[x+1][y]>dis[x][y]+1){
                dis[x+1][y]=dis[x][y]+1;
                q.push({x+1,y});
            }
        }
    }
    ll maxi=0;
    for(ll x=0;x<h;x++){
        for(ll y=0;y<w;y++){
            if(ar[x][y]==1){
                maxi=max(maxi,dis[x][y]);
            }
        }
    }
    return maxi;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll h,w;
    cin>>h>>w;
    for(ll x=0;x<h;x++){
        for(ll y=0;y<w;y++){
            char c;
            cin>>c;
            if(c=='.')ar[x][y]=1;
            else ar[x][y]=0;
        }
    }
    ll ans=0;
    for(ll x=0;x<h;x++){
        for(ll y=0;y<w;y++){
            if(ar[x][y]==1){
                ans=max(ans,solve(h,w,x,y));
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <deque>
#include <iostream>
#include <queue>
#include <string>
#include <vector>

#include <boost/multiprecision/cpp_int.hpp>

using namespace std;
using ll = long long;
namespace mp = boost::multiprecision;
using mpint = mp::cpp_int; // 多倍長整数（任意精度）


int main(){
  ll N, K;
  cin >> N >> K;

  ll ans = 0;
  for(ll i = K; i <= N+1; ++i){
    ans += i*(N+1-i)+1;
    ans %= 1000000007;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3644
def trial_division(n):
    a = []  
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2   
    if n != 1: a.append(n)

    return a

from fractions import gcd

A,B = map(int,input().split())

g = gcd(A,B)

L = trial_division(g)

D = {}

for i in L :
    if i not in D :
        D[i] = 1

print(len(D)+1)


Measured memory_bytes: 5048