akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <tuple>
#include <cassert>
#include <functional>
#include <set>
#include <deque>
#include <list>
using namespace std;
typedef long long ll;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
#define LNF __LONG_LONG_MAX__
const ll MOD = 1000000007;
const int MAX = 200000;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    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;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
// 法mでのaの逆元を計算
long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
// a^n mod を計算する
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
//最大公約数
long long gcd(long long x, long long y){
    if(y==0) return x;
    else return gcd(y,x%y);
}
//最小公倍数
long long lcm(long long x, long long y){
    return x / gcd(x, y) * y;
}
// nが大きく,kが10^7程度の時の二項係数
long long com[200005];
void combination(long long n,long long k){
    com[0] = 1;
    for(int i=1;i<=k;i++){
        com[i] = (com[i-1]*(n-i+1)%MOD)*modinv(i,MOD)%MOD;
    }
}

int main(){
    string s; cin >> s;
    for(int i=0;i<s.size();i++){
        if(s[i]==',') cout << " ";
        else cout << s[i];
    }
    printf("\n");
    return 0;
}


Measured memory_bytes: 3584
//↓template↓

#include "bits/stdc++.h"
using namespace std;
#define Would
#define you
#define all(n)  n.begin(),n.end()
#define rall(n) n.rbegin(),n.rend()
typedef long long ll;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const double EPS = 1e-10;
const double pi = acos(-1);//3.1415926535897932384626433832795028...
const ll SIZE = 1 << 17;
int dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 }, alp[30];
ll fac[200005], finv[200005], inv[200005];
vector<ll>dij;
struct edge { ll to, cost; };
vector<vector<edge> >G;

ll mod_pow(ll a, ll b) {
	ll res = 1, mul = a;
	for (int i = 0; i < 31; ++i) {
		if (b >> i & 1) {
			res *= mul;
			res %= MOD;
		}
		mul = (mul * mul) % MOD;
	}
	return res;
}

void addedge(int from, int to, int cost) {
	G[from].push_back({ to,cost });
	G[to].push_back({ from,cost });
}

template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }

template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
	return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}

template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T & t, const V & v) { t = v; }

template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T & t, const V & v) {
	for (auto& e : t) fill_v(e, v);
}

template<typename T>
void outp(vector<T>v) {
	for (int i = 0; i < v.size(); ++i) {
		cout << v[i];
		if (i != v.size() - 1) { cout << " "; }
	}
}

double add(double a, double b) {
	if (abs(a + b) < EPS * (abs(a) + abs(b))) { return 0; }
	return a + b;
}


//↑template↑


int main() {
	int a, b, c, d, e;
	cin >> a >> b >> c >> d >> e;
	string ans = "No";
	if (c + e <= a && c - e >= 0 && d + e <= b && d - e >= 0) { ans = "Yes"; }
	cout << ans << endl;
}


Measured memory_bytes: 3200
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <unordered_map> 

using namespace std;
#define MAXN 100000
#define pb push_back
#define ll long long
#define I(x,y) (1ll*(x)*n+~-(y))
#define U(x) ((x)/n)
#define V(x) ((x)%n+1)
#define rint register int
#define gc() getchar()
inline int read(rint ans = 0, rint sgn = ' ', rint ch = gc())
{
	for(; ch < '0' || ch > '9'; sgn = ch, ch = gc());
	for(; ch >='0' && ch <='9';(ans*=10)+=ch-'0', ch = gc());
	return sgn-'-'?ans:-ans;
}
int fa[MAXN+5], n, c; vector<ll> q; vector<int> e[MAXN+5]; unordered_map<ll,int> g; inline int getf(int x){return x^fa[x] ? fa[x]=getf(fa[x]) : x;}
int main()
{
	n = read(), c = 1; for(rint i = 1; i <= n; fa[i] = i, i++); for(rint i = 1, u, v; i <= (n<<1)-2; u = read(), v = read(), e[u].pb(v), e[v].pb(u), ++g[I(v,u)], ++g[I(u,v)]==2 ? q.pb(I(u,v)),0 : 0, i++);
	for(rint i = 0, u, v, j, t; i < (int)q.size() && c < n; i++)
		if(u = getf(U(q[i])), v = getf(V(q[i])), e[v].size()<e[u].size()?u^=v^=u^=v:0, g[q[i]]==2&&u^v)
			for(++c, fa[u] = v, j = 0; j < (int)e[u].size(); t = e[u][j], e[v].pb(t), e[t].pb(v), g[I(t,v)] += g[I(t,u)], (g[I(v,t)]+=g[I(u,t)])==2 ? q.pb(I(v,t)),0 : 0, j++); puts(c^n?"NO":"YES"); return 0;
}

Measured memory_bytes: 121096
let shift s i =
  String.map (fun c ->
      let cc = (Char.code c) in
      if cc >= 65 && cc <= 90 then
        (cc - 39 + i) mod 26 |> (+) 65 |> Char.chr
      else if cc >= 97 && cc <= 122 then
        (cc - 71 +i)  mod 26 |> (+) 97 |> Char.chr
      else c) s
;;

let () =
  let line = read_line () in
  print_endline (shift line (-3))
;;

Measured memory_bytes: 2032
N = int(input())
H = list(map(int, input().split()))
ans = [0]
counter = 0

for i in range(N-1):
    if H[i] - H[i+1] >= 0:
        counter += 1
    else:
        ans.append(counter)
        counter = 0

ans.append(counter)
        
ans_sorted = sorted(ans, reverse = True)
print(ans_sorted[0])

Measured memory_bytes: 14228
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		int n,m,l;
		long cal;
		int i,j,k;
		Scanner scan = new Scanner(System.in);
		n=scan.nextInt();
		m=scan.nextInt();
		l=scan.nextInt();
		long[][] yousoA =new long[n][m];
		long[][] yousoB =new long[m][l];
		long[][] yousoC =new long[n][l];
		for(i=0;i<n;i++)
		{
			for(j=0;j<m;j++) {
			cal=scan.nextInt();
			yousoA[i][j]=cal;
			}
		}
		for(i=0;i<m;i++)
		{
			for(j=0;j<l;j++) {
				cal=scan.nextInt();
				yousoB[i][j]=cal;
				}
		}
		for(i=0;i<n;i++)
		{
			cal=0;
			for(j=0;j<l;j++) {
				for(k=0;k<m;k++) {
				cal=cal+yousoA[i][k]*yousoB[k][j];
				}
				yousoC[i][j]=cal;
				cal=0;
				if(j==l-1)
					break;
				System.out.print(yousoC[i][j]+" ");
			}
			System.out.println(yousoC[i][j]);
			
		}
		
	}
}

Measured memory_bytes: 53432
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define rep(i, n) for(int i = 0; i < (int)(n); ++i)
#define REP(i, n) for(int i = 1; i < (int)(n); ++i)
using namespace std;

int n;
vector<vector<int>> graph(100);
queue<int> q;
vector<int> dist(100, -1);

void BFS() {
    int u = q.front();
    q.pop();
    for (int v : graph[u]) {
        if (dist[v] == -1) {
            dist[v] = dist[u] + 1;
            q.push(v);
        }
    }
    return;
}

int main() {
    cin >> n;
    rep(i, n) {
        int u, k;
        cin >> u >> k;
        rep(i, k) {
            int v;
            cin >> v;
            graph[u - 1].push_back(v - 1);
        }
    }
    
    q.push(0);
    dist[0] = 0;
    while (q.size() > 0) BFS();
    rep(i, n) cout << i + 1 << " " << dist[i] << endl;
    return 0;
}



Measured memory_bytes: 3160
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int main() {
	int A,B,C;
	cin >> A >> B >> C;
	if (B/A > C) {
		cout << C << endl;
	} else {
		cout << B/A << endl;
	}
	return 0;
}

Measured memory_bytes: 256
import java.util.*;
import java.io.*;

class Main {
  public static void main(String[] args) throws Exception{
    try (Scanner sc = new Scanner(System.in)){
      int a = sc.nextInt();
      int b = sc.nextInt();
      if (a + b == 15) {
        System.out.println("+");
      } else if (a * b == 15) {
        System.out.println("*");
      } else {
        System.out.println("x");
      }
    }
  }
}


Measured memory_bytes: 20820
#include <iostream>
#include <string>
#include <utility>
#include <stack>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <climits>
#include <set>
#include <numeric>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <cfloat>
using namespace std;
long long A[1000000];
bool is_prime[1000001];
int divisor_count[1000];
int gcd(int m, int n){
  if(n > m){
    return gcd(n, m);
  } else if(n == 0){
    return m;
  }
  return gcd(n, m % n);
}

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

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

  for(int i = 2; i < 1000001; i++){
    is_prime[i] = true;
  }
  for(int i = 2; i <= 1000; i++){
    if(is_prime[i]){
      for(int j = 2 * i; j < 1000001; j += i){
        is_prime[j] = false;
      }
    }
  }

  vector <int> prime_lst;
  for(int i = 2; i <= 1000; i++){
    if(is_prime[i]){
      prime_lst.push_back(i);
    }
  }

  bool done = false;
  bool pair_co = true;
  set <int> left_A_set;
  for(int i = 0; i < N; i++){
    int tmp = A[i];
    for(int j = 0; j < prime_lst.size(); j++){
      if(A[i] % prime_lst[j] == 0){
        divisor_count[j] ++;
        if(divisor_count[j] > 1){
          done = true;
          break;
        } 
        while(tmp % prime_lst[j] == 0){
          tmp /= prime_lst[j];
        }
      }
    }

    if(tmp != 1){
      if(left_A_set.find(tmp) != left_A_set.end()){
        pair_co = false;
        done = true;
      }
      left_A_set.insert(tmp);
    }
    if(done){
      break;
    }
  }

  for(int i = 0; i < prime_lst.size(); i++){
    if(divisor_count[i] >= 2){
      pair_co = false;
      break;
    }
  }

  if(pair_co){
    cout << "pairwise coprime" << endl;
    return 0;
  }

  long long tmp = A[0];
  for(int i = 1; i < N; i++){
    tmp = gcd(tmp, A[i]);
  }

  if(tmp == 1){
    cout << "setwise coprime" << endl;
  } else {
    cout << "not coprime" << endl;
  }
  return 0;
}


Measured memory_bytes: 12368
import sys
input = sys.stdin.readline


def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    A.sort()

    import collections
    q = collections.deque(A)

    p = collections.deque()
    p.append(q.pop())
    ans = 0
    while q:
        q1, q2 = q[0], q[-1]
        p1, p2 = p[0], p[-1]
        a = abs(q1 - p1)
        b = abs(q1 - p2)
        c = abs(q2 - p1)
        d = abs(q2 - p2)
        ma = max(a, b, c, d)
        ans += ma
        if ma == a:
            p.appendleft(q.popleft())
        elif ma == b:
            p.append(q.popleft())
        elif ma == c:
            p.appendleft(q.pop())
        elif ma == d:
            p.append(q.pop())
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 8148
string = input()

h = 0
A = [h]
for c in string:
    if c == "/": h += 1
    elif c == "\\": h -= 1
    A.append(h)

flg = False
ans1 = []
ans2 = []

forward = True
while len(A) > 1:
    h = 0
    B = [0]

    for i in range(len(A) - 1):
        if not flg: B = [0]

        d = A[i + 1] - A[i]
        if d < 0: flg = True
        h += d

        if h <= 0:
            B.append(h)

            if h == 0:
                if len(B) > 2:
                    if forward: ans1.append(abs(sum(B)))
                    else: ans2.append(abs(sum(B)))
                B = []
                flg = False
        else:
            h = 0

    A = B.copy()
    A.reverse()
    forward = (forward + 1) % 2

ans2.reverse()
ans = ans1 + ans2

print(sum(ans))
print(len(ans), *ans)


Measured memory_bytes: 7084
n, m = map(int, input().split())
h = list(map(int, input().split()))

ary = [0 for i in range(n)]
chk = [False for i in range(n)]
for i in range(m):
	a, b = map(int, input().split())
	#chk[a-1] = True
	#chk[b-1] = True
	if h[a-1] < h[b-1]:
		ary[a-1] += 1
	elif h[a-1] > h[b-1]:
		ary[b-1] += 1
	else:
		ary[a-1] += 1
		ary[b-1] += 1

cnt = 0
for i in range(n):
	if ary[i] == 0:
		cnt += 1
print (cnt)

Measured memory_bytes: 20128
#include<iostream>
#include<vector>
#include<algorithm>


using namespace std;

int main(){
  vector<int> aa(3);
  
  for(auto &x:aa){
    cin>>x;
  }
  
  
  sort(aa.begin(),aa.end());
  
  if(aa[0]+aa[1]==aa[2]){
    cout<<"Yes"<<endl;
  }
  else{
	cout<<"No"<<endl;
  }
}

Measured memory_bytes: 256
main(i,N,T,E,x,y){
	for(scanf("%d%d%d",&N,&T,&E),i=1;i<=N;i++){
		for(scanf("%d",&x),y=0;y<T-E;y+=x);
		if(y<=T+E){printf("%d\n",i);break;}
	}
	if(i>N)puts("-1");
	exit(0);
}

Measured memory_bytes: 0
#include <algorithm>
#include <bitset>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <vector>

using namespace std;

#define rep(i, n) for (int64_t i = 0; i < (int64_t)(n); i++)
#define irep(i, n) for (int64_t i = 0; i <= (int64_t)(n); i++)
#define rrep(i, n) for (int64_t i = (n)-1; i >= 0; i--)
#define rirep(i, n) for (int64_t i = n; i >= 0; i--)

#define chmax(a, b) (a) = max(a, b)
#define chmin(a, b) (a) = min(a, b)

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

  int N, K;
  cin >> N >> K;

  vector<int> a(N);
  rep(i, N) { cin >> a[i]; }

  int lb = 0, ub = 1'000'000'000;
  while (ub > lb + 1) {
    int mid = (ub + lb) / 2;

    int64_t cnt = 0;
    rep(i, N) { cnt += (a[i] + mid - 1) / mid - 1; }

    (cnt <= K ? ub : lb) = mid;
  }
  cout << ub << endl;

  return 0;
}

Measured memory_bytes: 3508
//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <iomanip>

using namespace std;

#define FAST       			ios_base :: sync_with_stdio(false); cin.tie(NULL); 
#define endl "\n"

typedef long long int  ll;


int main()
{
	FAST;
	char a[100][100],b[100][100];
	int n,m;
	cin >> n >> m;
	
	for(int i=0 ; i<n ; i++)
		cin >> a[i];
	for(int i=0 ; i<m ; i++)
		cin >> b[i];

	for(int i=0 ; i<n-m+1 ; i++)
	{
		for(int j=0 ; j<n-m+1 ; j++)
		{
		    bool flag = true;
			for(int k=i ; k<m+i ; k++)
			{
				for(int l=j ; l<m+j ; l++)
				{
					if(b[k-i][l-j] != a[k][l])
					{
						flag = false;
						break;
					}
				}
			}
			
			if(flag)
			{
			    cout << "Yes";
			    return 0;
			}
		}
	}
    
		
	cout << "No";
	return 0;

}

Measured memory_bytes: 256
#include <vector>
#include <iostream>
#include <algorithm>
#include <set>

using namespace std;
#define MAX 10000

vector<int> G[MAX];
int n;
bool visited[MAX];
int treeIdx[MAX], parent[MAX], lowest[MAX], treeNodeCounter;

void dfs(int curIdx, int prev)
{
	treeIdx[curIdx] = lowest[curIdx] = treeNodeCounter;
	treeNodeCounter++;

	visited[curIdx] = true;
	int next;

	for (int i = 0; i < G[curIdx].size(); ++i)
	{
		next = G[curIdx][i];
		if (!visited[next])
		{
			parent[next] = curIdx;
			dfs(next, curIdx);
			lowest[curIdx] = min(lowest[curIdx], lowest[next]);
		}
		else if (next != prev)
		{
			lowest[curIdx] = min(lowest[curIdx], treeIdx[next]);
		}
	}
}

void criticalPoints()
{
	for (int i = 0; i < n; ++i)
		visited[i] = false;
	treeNodeCounter = 1;

	dfs(0, -1);

	set<int> s;
	int np = 0;
	for (int i = 1; i < n; ++i)
	{
		int p = parent[i];
		if (0 == p) np++;
		else if (treeIdx[p] <= lowest[i])
			s.insert(p);
	}
	if (np > 1) cout << 0 << endl;
	for (auto v : s) cout << v << endl;
}

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

	for (int i = 0; i < m; ++i)
	{
		int s, t;
		cin >> s >> t;
		G[s].push_back(t);
		G[t].push_back(s);
	}
	criticalPoints();

	return 0;
}

Measured memory_bytes: 4884
fn slimes() -> Result<u32, &'static str> {
    let mut input = String::new();
    std::io::stdin().read_line(&mut input)
        .map_err(|_| "input error")?;
    let n = input.trim_right().parse::<usize>()
        .map_err(|_| "parse error")?;

    let mut line = String::new();
    std::io::stdin().read_line(&mut line)
        .map_err(|_| "input error")?;

    let mut chars = line.chars();
    let mut recur = chars.nth(0).ok_or("0 nth error")?;
    let mut count = 0u32;

    for c in chars {
        if recur != c {
            count = count + 1;
            recur = c;
        }
    }
    return Ok(count);
}

fn main() {
    println!("{}", slimes().unwrap());
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
using ll=unsigned long long;
int main(){
//  x%B=B-1
//Ax%B=0にちかければいい
  ll A,B,N; cin>>A>>B>>N;
  ll x;
  if(N>=B-1) x=B-1;
  else x=N;
  ll ans=(A*x)/B-A*(x/B);
  cout<<ans<<endl;
}

Measured memory_bytes: 3596
import java.util.Scanner;

class Main{
    public static void main(String[]args){
        Scanner cin=new Scanner(System.in);
        String l1 = cin.nextLine();
        String l2 = cin.nextLine();
        String l3 = cin.nextLine();
        System.out.println(new String(new char[] {l1.charAt(0), l2.charAt(1), l3.charAt(2)}));
    }
}

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

#include <iostream>
#include <fstream>

#include <bits/stdc++.h>

#define int long long
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define FOR(i, a, b) for (int i = (a), i##_len = (b); i <= i##_len; ++i)
#define REV(i, a, b) for (int i = (a); i >= (b); --i)
#define CLR(a, b) memset((a), (b), sizeof(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define INF 1001001001001001001ll
#define fcout cout << fixed << setprecision(12)

using namespace std;

typedef pair<int, int> P;

class BRowToColumn {
public:
    void solve(std::istream& cin, std::ostream& cout) {
        int N;
        cin >> N;

        vector<vector<char>> a(N, vector<char>(N, 0));
        REP(i, N) REP(j, N) cin >> a[i][j];

        set<int> cols, exists;
        vector<int> rows(N);
        bool ok = false;
        REP(i, N) {
            REP(j, N) {
                char c = a[i][j];
                if (c == '.') {
                    rows[i]++;
                    cols.insert(j);
                } else {
                    ok = true;
                    exists.insert(j);
                }
            }
        }

        if (!ok) {
            cout << -1 << endl;
            return;
        }

        int res = INF;
        REP(i, N) {
            int tmp;
            if (exists.count(i)) {
                tmp = rows[i];
            } else {
                tmp = rows[i] + 1;
            }
            res = min(tmp, res);
        }
        cout << res + cols.size() << endl;
    }
};


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    std::istream& in(std::cin);
    std::ostream& out(std::cout);

    BRowToColumn solver;
    solver.solve(in, out);
    return 0;
}


Measured memory_bytes: 512
import java.util.Scanner

object Main extends App {

  val sc = new Scanner(System.in)

  val n = sc.nextInt
  val al = Seq.fill(n)(sc.nextInt)

//  val containsCounts =
//    al.foldLeft(Map.empty[Int, Int]){ case (m, e) =>
//      if (m.isDefinedAt(e)) m.updated(e, m(e) + 1)
//      else m + (e -> 1)

      // m で定義されている  =>  mapValue
      // m で定義されていない=>  mapを追加
//  }

  val m = al
    .zipWithIndex
    .groupBy(_._1)
    .mapValues(_.size)

  val res = m.foldLeft(0){ case (acc, (e ,cnt)) =>
    acc + (if (e > cnt) cnt else cnt - e)
  }

  println(res)
}

Measured memory_bytes: 111412
#include <bits/stdc++.h>
using namespace std;
#define SZ(x) (int)(x.size())
#define REP(i, n) for(int i=0;i<(n);++i)
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define RREP(i, n) for(int i=(int)(n)-1;i>=0;--i)
#define RFOR(i, a, b) for(int i=(int)(b)-1;i>=(a);--i)
#define ALL(a) a.begin(),a.end()
#define DUMP(x) cerr<<#x<<" = "<<(x)<<endl
#define DEBUG(x) cerr<<#x<<" = "<<(x)<<" (L"<<__LINE__<<")"<< endl;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using P = pair<int, int>;
const double eps = 1e-8;
const ll MOD = 1000000007;
const int INF = INT_MAX / 2;
const ll LINF = LLONG_MAX / 2;
template <typename T1, typename T2>
bool chmax(T1 &a, const T2 &b) {
    if (a < b) { a = b; return true; }
    return false;
}
template <typename T1, typename T2>
bool chmin(T1 &a, const T2 &b) {
    if (a > b) { a = b; return true; }
    return false;
}
template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    os << "[";
    REP(i, SZ(v)) {
        if (i) os << ", ";
        os << v[i];
    }
    return os << "]";
}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const map<T1, T2> &mp) {
    os << "{";
    int a = 0;
    for (auto &tp : mp) {
        if (a) os << ", "; a = 1;
        os << tp;
    }
    return os << "}";
}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
    os << p.first << ":" << p.second;
    return os;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    int n; cin >> n;
    int ans = 0;
    if (n == 0) ans = 1;
    if (n == 1) ans = 2;
    if (n == 2) ans = 1;
    cout << ans << endl;

    return 0;

}



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

int main() {
    int n, m;
    cin >> n >> m;
    vector<string> a(n), b(m);
    rep(i,n) cin >> a.at(i);
    rep(i,m) cin >> b.at(i);

    for(int i = 0; i <= n-m; i++) {
        bool found = true;
        size_t pos = a.at(i).find(b.at(0));
        while(pos != string::npos && pos >= 0) {
            for(int j = 1; j < m; j++) {
                string asub = a.at(i+j).substr(pos, b.at(j).size());
                if(asub != b.at(j)) {
                    found = false;
                    break;
                }
            }
            if(found) {
                cout << "Yes" << endl;
                return 0;
            }
            else {
                pos = a.at(i).find(b.at(0), pos + b.at(0).size());
            }
        }
    }

    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3580
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <memory>

//#define int long long

using namespace std;

void Main()
{
	string s;
	cin >> s;

	if (s[2] != s[3]) {
		cout << "No" << endl;
		return;
	}
	if (s[4] != s[5]) {
		cout << "No" << endl;
		return;
	}

	cout << "Yes" << endl;
}

int32_t main()
{
	Main();
	return 0;
}



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

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

template<class T>
void debug(T itr1, T itr2) { auto now = itr1; while(now<itr2) { cout << *now << " "; now++; } cout << endl; }
#define repr(i,from,to) for (int i=(int)from; i<(int)to; i++)
#define all(vec) vec.begin(), vec.end()
#define rep(i,N) repr(i,0,N)
#define per(i,N) for (int i=(int)N-1; i>=0; i--)

const ll MOD = pow(10,9)+7;
const ll LLINF = pow(2,61)-1;
const int INF = pow(2,30)-1;

vector<ll> fac;
void c_fac(int x=pow(10,6)+10) { fac.resize(x,true); rep(i,x) fac[i] = i ? (fac[i-1]*i)%MOD : 1; }
ll inv(ll a, ll m=MOD) { ll b = m, x = 1, y = 0; while (b!=0) { int d = a/b; a -= b*d; swap(a,b); x -= y*d; swap(x,y); } return (x+m)%m; }
ll nck(ll n, ll k) { return fac[n]*inv(fac[k]*fac[n-k]%MOD)%MOD; }
ll gcd(ll a, ll b) { if (a<b) swap(a,b); return b==0 ? a : gcd(b, a%b); }
ll lcm(ll a, ll b) { return a/gcd(a,b)*b; }


int main() {
  int N; cin >> N;
  string s; cin >> s;
  int l = s.length();

  ll dp[N+1][N+1] = {}; dp[0][0] = 1;
  rep(i,N) rep(j,N+1) {
    if (j==0) dp[i+1][j] = (dp[i][j]+dp[i][j+1])%MOD;
    else if (j==N) dp[i+1][j] = (dp[i][j-1]*2)%MOD;
    else dp[i+1][j] = (dp[i][j-1]*2+dp[i][j+1])%MOD;
  }
  // rep(i,N+1) debug(dp[i],dp[i]+(N+1));
  ll div = 1, now = 1, p2 = 2;
  while (l>=now) { if (l&now) div = (div*p2)%MOD; now *= 2; p2 = (p2*p2)%MOD; }
  ll result = (dp[N][l]*inv(div))%MOD;
  cout << result << endl;
  return 0;
}

Measured memory_bytes: 195712
import java.io.InputStream;
import java.io.IOException;
import java.util.HashSet;

class MyScanner{
    InputStream stream;
    public MyScanner(){
        stream = System.in;
    }
    
    public int nextInt(){
        int ret = 0;
        try{
            while(true){
                char readed = (char)stream.read();
                if(readed < '0' || readed > '9'){
                    break;
                }
                ret = ret * 10 + (readed - '0');
            }
        }catch(IOException e){
            e.printStackTrace();
        }finally{
            return ret;
        }
    }
}

class Main {
    public static void main(String args[]) {
        MyScanner sc = new MyScanner();
        HashSet<Integer> set = new HashSet<Integer>();
        int n = sc.nextInt(), m = sc.nextInt();
        boolean[] selected = new boolean[m];
        for(int i = 0; i < m; i++){
            set.add(i);
        }
        
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < m; ++j){
                selected[j] = true;
            }
            int c = sc.nextInt();
            for(int j = 0; j < c; ++j){
                selected[sc.nextInt() - 1] = false;
            }
            for(int j = 0; j < m; ++j){
                if(selected[j]){
                    set.remove(j);
                }
            }
        }
        System.out.println(set.size());
    }
}


Measured memory_bytes: 21204
#include <stdio.h>
#include <math.h>

#define M_PI 3.141592653589793

int main(void) {

	int i = 0, j, k, l;
	int H[10000], W[10000];

	while (1) {
		scanf("%d %d", &H[i], &W[i]);
		if (H[i] == 0 && W[i] == 0) {
			break;
		}
		else {
			i++;
		}
	}

	for (l = 0; l < i; l++) {
		for (j = 0; j < H[l]; j++) {
			for (k = 0; k < W[l]; k++) {
				printf("#");
			}printf("\n");
		}printf("\n");
	}

	return 0;
}

Measured memory_bytes: 2576
/*  -*- coding: utf-8 -*-
 *
 * e.cc: E - Dist Max
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const long long LINF = 1LL << 62;

/* typedef */

typedef long long ll;

/* global variables */

/* subroutines */

/* main */

int main() {
  int n;
  scanf("%d", &n);

  ll minz = LINF, maxz = -LINF, minw = LINF, maxw = -LINF;
  for (int i = 0; i < n; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    ll z = x + y, w = x - y;
    if (minz > z) minz = z;
    if (maxz < z) maxz = z;
    if (minw > w) minw = w;
    if (maxw < w) maxw = w;
  }

  printf("%lld\n", max(maxz - minz, maxw - minw));
  return 0;
}


Measured memory_bytes: 3776
#include <bits/stdc++.h>
#define rep(i,a,n)  for (int i=(int)(a); i<=(int)(n); ++i)
#define rrep(i,a,n) for (int i=(int)(a); i>=(int)(n); --i)
#define debug(x) cerr << #x << " = " << x << "\n"
#define debugv(x) rep(f, 0, (x.size()-1)) cerr << x[f] << (f == (x.size() - 1) ? "\n" : " ")
#define all(x) x.begin(),x.end()
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = ((1LL << 30) + (1LL << 29));
const int MOD = 1000000007;

//=============================
int N,M,K;
vector<int> A;
vector<int> B;
int  H, W;
vector<vector<int>> s;
//=============================
void input()
{
    cin>>H>>W;
    s.resize(H,vector<int>(W));
    rep(i,0,H-1){
        rep(j,0,W-1){
            char tmp;
            cin>>tmp;
            s[i][j] = (tmp == '.' ? 1 : 0);
        }
    }
}
//=============================
void func(){}

set<pii> visited;
vector<vector<int>> ls(52,vector<int>(52,0));
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
void bfs(int now_i,int now_j){
    pii now = pii(now_i,now_j);
    queue <pii> q;
    q.push(now);
    ls[0][0] = 1;

    while(!q.empty()){
        pii t = q.front();
        q.pop();
        // if (t == pii(H-1,W-1)){
        //     shortest = count;
        //     return;
        // }
        int i=t.first;
        int j=t.second;
        // if (t == pii(0,0)){
        //     ls[0][0] = 1;
        // }
        // else {
            rep(ii,0,3){
                int ni = i+dx[ii];
                int nj = j+dy[ii];
                if (ni>=0 && nj>=0 && ni<H && nj<W){
                    if (!ls[ni][nj] && s[ni][nj]){
                        ls[ni][nj] = ls[i][j]+1;
                        q.push(pii(ni,nj));
                    }
                }
            }
        // }
    }

}
//=============================
void solve()
{
    int sum = 0;
    for (auto x : s){
        for (auto y : x){
            sum += y;
        }
    }
    bfs(0,0);
    int shortest = ls[H-1][W-1];

    int ans;
    if (shortest == 0){
        ans = -1;
    }
    else {
        ans = sum-shortest;
    }

    // rep(i,0,5){
    //     debugv(ls[i]);
    // }
    // debug(H*W);
    // debug(sum);
    // debug(shortest);
    cout<<ans<<endl;




}
//=============================
signed main()
{
    input();
    solve();
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <tuple>
#include <sstream>
#include <vector>
#include <cmath>
#include <ctime>
#include <bitset>
#include <cassert>
#include <cstdio>
#include <queue>
#include <set>
#include <map>
#include <fstream>
#include <cstdlib>
#include <string>
#include <cstring>
#include <algorithm>
#include <numeric>

#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef double ld;

template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

map<int, int> par;

int get_par(int x) {
    if (!par.count(x)) par[x] = x;
    return par[x];
}

int root(int x) {
    if (get_par(x) == x) return x;
    return par[x] = root(par[x]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.precision(10);
    cout << fixed;
#ifdef LOCAL_DEFINE
    freopen("input.txt", "rt", stdin);
#endif

    int n;
    cin >> n;
    vi a(n), b(n);
    forn(i, n) cin >> a[i];
    forn(i, n) cin >> b[i];
    int xa = 0, xb = 0;
    forn(i, n) xa ^= a[i], xb ^= b[i];
    a.pb(xa);
    b.pb(xb);
    if (multiset<int>(all(a)) != multiset<int>(all(b))) {
        cout << -1 << '\n';
        return 0;
    }
    ++n;
    int ans = -1;
    forn(i, n) {
        int x = a[i], y = b[i];
        if (x == y && i + 1 < n) continue;
        ++ans;
        x = root(x), y = root(y);
        par[x] = y;
    }
    int comps = 0;
    for (auto w: par) if (w.fi == w.se) ++comps;
//    cerr << ans << ' ' << comps << '\n';
    ans += comps - 1;
    cout << ans << '\n';

#ifdef LOCAL_DEFINE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}


Measured memory_bytes: 19824
#include <stdio.h>

int main(){
	int a,b,c,i,cntr;
	cntr=0;
	i=0;
	scanf ("%d %d %d",&a,&b,&c);
	if (a>=1&&a<=10000&&b>=1&&b<=10000&&b>=1&&c<=10000&&a<=b){
		for (i=0;a<=b;a++){
			if (c%a==0){
			cntr=cntr+1;
			}
		}
	}
	printf ("%d\n",cntr);
	return 0;
}
//(???,_??????)???????????????????????????!!

Measured memory_bytes: 596
import sys
readline = sys.stdin.buffer.readline
# ord('.') == 46

def main():
    H, W = map(int, readline().split())
    a = readline()
    k = a.find(b'#')
    if k == -1:
        k = W
    v = [1] * k + [0] * (W - k)
    u = [0] * W

    for _ in range(1, H):
        a = readline()
        u, v = v, u
        v[0] = t = u[0] if a[0] == 46 else 0
        for j, uu, aa in zip(range(1, W), u[1:], a[1:]):
            v[j] = t = uu + t if aa == 46 else 0
    print(v[-1] % (10 ** 9 + 7))


main()


Measured memory_bytes: 3444
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repp(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define repm(i,n) for(int (i)=(n-1);(i)>=0;(i)--)
#define INF (1ll<<60)
#define all(x) (x).begin(),(x).end()
typedef long long lint;
const lint MOD =1000000007;
const lint MAX = 10000000;
using Graph =vector<vector<lint>>;

 
lint fac[MAX], finv[MAX], inv[MAX];

void COMinit() // 二項係数を求める時は前処理としてCOMinit()をする
{
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (lint 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;
    }
}
 
// 二項係数計算
long long COM(lint n, lint k)
{
    if (n < k)
        return 0;
    if (n < 0 || k < 0)
        return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

lint primary(lint num)
{
    if (num < 2) return 0;
    else if (num == 2) return 1;
    else if (num % 2 == 0) return 0; // 偶数はあらかじめ除く

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            // 素数ではない
            return 0;
        }
    }

    // 素数である
    return 1;
}
lint lcm(lint a,lint b){
      return a/__gcd(a,b)*b;
  }
    lint B1[3000];
    lint B2[3000];
  int main(){
        lint N,K;
        lint ans=0;
        cin>>N>>K;
        lint A[N];
        lint C[N];
        rep(i,N){
            cin>>A[i];
            C[i]=A[i];
        }
        sort(C,C+N,greater<lint>());
        rep(i,N){
            lint x=0;
           while(1){
               if(A[i]<C[x])B1[i]++;
               else break;
               x++;
           }
        }
        rep(i,N){
            rep(j,i){
                if(A[i]<A[j])B2[i]++;
            }
        }
      rep(i,N){
          lint g;
            ans+=B2[i]*K;
            ans%=MOD;
            g=K*(K-1)/2;
            g%=MOD;
            g*=B1[i];
            g%=MOD;
            ans+=g;
      }
      ans%=MOD;
        cout<<ans;
  }
  

Measured memory_bytes: 256
# coding: utf-8

n = int(input())
a = ""

if n == 0:
    print(0)
else:
    while n != 0:
        if n % 2 == 0:
            a = "{0}{1}".format(0, a)
            n /= -2
        else:
            a = "{0}{1}".format(1, a)
            n = (n-1)/(-2)
    print(a)

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

int main() {
  int N;
  cin >> N;
  string s;
  cin >> s;
  int S = s.size();

  char c[S];
  for (int i = 0; i < S; i++) {
    c[i] = s.at(i);
  }
  
  for (int i = 0; i < S; i++) {
    for (int j = 0; j < N; j++) {
      if (c[i] != 'Z') {c[i]++;}
      else {c[i] = 'A';}
    }
  }
  for (int i = 0; i < S; i++) {
    cout << c[i];
  }
  cout << endl;
}

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

int main() {
	// your code goes here
	long long int n = 0, m = 0, a = 0, b = 0, c = 0;
	string s;
	cin >> a >>  b;
	
	if((a + b)  % 2 == 0){
		
	cout << (a + b) / 2 << endl;
	}
	else{
		cout << "IMPOSSIBLE" << endl;
	}
	
	return 0;
}

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

int main(){
	string s;
	int j;
	int count=0;
	
	cin >> s;

	j=0;
	for(int i=1;i<s.length();i++){
		if(!(s.at(j)==s.at(i))){
		// cout <<i<< count <<s.at(j)<<s.at(i)<< endl;
			j=i;
			count++;
		}
	}
	
	cout << count << endl;
	return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int A, B, C, K;
    cin >> A >> B >> C >> K;
    if(A >= K) cout << K;
    else if(A + B >= K) cout << A;
    else cout << A - (K-A-B);
    return 0;
}


Measured memory_bytes: 3620
H,W=map(int,input().split())

if H%3==0 or W%3==0:
  print(0)
elif H==2 or W==2:
  ans0=min(H,W)
  
  H,W=min(H,W),max(H,W)
  w1=W//3
  w2=W-w1
  s1=2*w1
  s2=w2
  ans1=s2-s1
  
  w1=W//3+1
  w2=W-w1
  s1=2*w1
  s2=w2
  ans2=s1-s2
  print(min(ans0,ans1,ans2))
else:
  ans0=min(H,W)
  
  h1=H//2
  h2=H-h1
  
  w1=W//3
  w2=W-w1
  s1=w1*H
  s2=w2*h1
  s3=w2*h2
  ans1=max(s1,s2,s3)-min(s1,s2,s3)
  
  w1=W//3+1
  w2=W-w1
  s1=w1*H
  s2=w2*h1
  s3=w2*h2
  ans2=max(s1,s2,s3)-min(s1,s2,s3)
  
  H,W=W,H
  h1=H//2
  h2=H-h1
  
  w1=W//3
  w2=W-w1
  s1=w1*H
  s2=w2*h1
  s3=w2*h2
  ans3=max(s1,s2,s3)-min(s1,s2,s3)
  
  w1=W//3+1
  w2=W-w1
  s1=w1*H
  s2=w2*h1
  s3=w2*h2
  ans4=max(s1,s2,s3)-min(s1,s2,s3)
  print(min(ans0,ans1,ans2,ans3,ans4))

Measured memory_bytes: 3188
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define debug(x) cout << "debug " << x << endl;
const long long INF = 2000000000L;
using namespace std;

int main(){
    long long n, t;
    long long a[100005][3];
    cin >> n >> t;
    rep(i,n) cin >> a[i][0];

    long long mini = INF, maxi = 0;
    rep(i,n){
        mini = min(mini, a[i][0]);
        a[i][1] = mini;
        a[i][2] = a[i][0] - a[i][1];
        maxi = max(maxi, a[i][2]);
    }

    long long cnt = 0;
    rep(i,n){
        if(maxi == a[i][2]) cnt++;
    }
    cout << cnt << endl;
}


Measured memory_bytes: 2560
A,B,K = map(int, input().split())

def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    c = a % b
    return gcd(b, c)


C = gcd(A,B)

y = []
for i in range(C):
    if C % (i+1) == 0:
        y.append(i+1)


print(y[::-1][K-1])


Measured memory_bytes: 3060
void main() {
	auto N = ri;
	auto S = rs;
	ulong res;
	foreach(i; 0..S.length - 2) {
		if(S[i..i+3] == "ABC") res++;
	}
	res.writeln;
}

// ===================================

import std.stdio;
import std.string;
import std.functional;
import std.algorithm;
import std.range;
import std.traits;
import std.math;
import std.container;
import std.bigint;
import std.numeric;
import std.conv;
import std.typecons;
import std.uni;
import std.ascii;
import std.bitmanip;
import core.bitop;

T readAs(T)() if (isBasicType!T) {
	return readln.chomp.to!T;
}
T readAs(T)() if (isArray!T) {
	return readln.split.to!T;
}

T[][] readMatrix(T)(uint height, uint width) if (!isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		res[i] = readAs!(T[]);
	}
	return res;
}

T[][] readMatrix(T)(uint height, uint width) if (isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		auto s = rs;
		foreach(j; 0..width) res[i][j] = s[j].to!T;
	}
	return res;
}

int ri() {
	return readAs!int;
}

double rd() {
	return readAs!double;
}

string rs() {
	return readln.chomp;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define poi 500000
#define inf 0x3f3f3f3f
using namespace std;
#define int long long
inline int re()
{
	char c=(char)getchar();
	int x=0,k=1;
	while(c<'0'||c>'9')
	{if(c=='-')k=-1;c=(char)getchar();}
	while(c>='0'&&c<='9')
	{x=(x<<1)+(x<<3)+c-'0';c=(char)getchar();}
	return k<0?-x:x;
}
void wr(int x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) wr(x/10);
	putchar(x%10+'0');
}
signed main()
{
	int n=re(),p=re(),ans=1ll;
	if(n==1)
	{
		wr(p);
		return 0;
	}
	for(int i=2;i*i<=p;i++)
	{
		int coco=0ll;
		while(!(p%i))
		{
			coco++;
			if(coco==n)
			ans=ans*i,coco=0ll;
			p/=i;
		}
	}
	wr(ans);
	return 0;
}
/*
1 984883985932
*/

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define FILL(a, n, x) memset((a), (x), sizeof ((a)[0]) * (n))
#define COPY(a, n, b) memcpy((b), (a), sizeof ((a)[0]) * (n))
using namespace std;

typedef long long li;

const int mod = 1e9 + 7, inv2 = mod + 1 >> 1;
inline int Add(int x) { return x >= mod ? x - mod : x; }
inline void Add(int &x, int y) { x += y; if (x >= mod) x -= mod; }
inline int Sub(int x) { return x < 0 ? x + mod : x; }
inline void Sub(int &x, int y) { x -= y; if (x < 0) x += mod; }
inline int Mul(int x, int y) { return (li)x * y % mod; }

int Pow(int x, int y) {
  int z = 1;
  for (; y; y >>= 1) {
    if (y & 1) z = Mul(z, x);
    x = Mul(x, x);
  }
  return z;
}

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

const int maxn = 3000;

int n, q;
int origin[maxn];
int p[maxn][maxn];

void Change(int x, int y) {
  p[x][y] = p[y][x] = Mul(Add(p[x][y] + p[y][x]), inv2);
  for (int z = 0; z < n; ++z) {
    if (z == x || z == y) continue;
    int p1 = Mul(Add(p[x][z] + p[y][z]), inv2);
    int p2 = Mul(Add(p[z][x] + p[z][y]), inv2);
    p[x][z] = p[y][z] = p1;
    p[z][x] = p[z][y] = p2;
  }
}

int main(void) {
  scanf("%d%d", &n, &q);
  for (int i = 0; i < n; ++i) {
    scanf("%d", origin + i);
  }
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      p[i][j] = origin[i] < origin[j];
    }
  }

  for (int i = 0; i < q; ++i) {
    int x, y;
    scanf("%d%d", &x, &y);
    --x; --y;
    Change(x, y);
  }
  int ans = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
      Add(ans, p[j][i]);
    }
  }
  ans = Mul(ans, Pow(2, q));
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 35328
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef tuple<int,int,int> T;
signed main(){
  int a,b,c;
  cin>>a>>b>>c;
  if(a%2||b%2||c%2){
    cout<<0<<endl;
    return 0;
  }
  int ans=1;
  int a2,b2,c2;
  a2=b/2+c/2;
  b2=a/2+c/2;
  c2=a/2+b/2;
  set<T> s;
  while(!(a2%2||b2%2||c2%2)){
    ans++;
    if(s.count(make_tuple(a2,b2,c2))){
      cout<<-1<<endl;
      return 0;
    }
    s.insert(make_tuple(a2,b2,c2));
    a=a2;b=b2;c=c2;
    a2=b/2+c/2;
    b2=a/2+c/2;
    c2=a/2+b/2;
  }
  cout<<ans<<endl;
  return 0;
}


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

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

    map<int, int> mp;
    
    for (int i = 0; i < n; i++){
        int a;
        cin >> a;
        mp[a] = i+1;
    }

    for (auto p : mp){
         cout << p.second << " ";
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 5504
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <sstream>

using namespace std;

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

typedef vector<int> vi;

int main()
{
	char str[81];
	while(fgets(str, 81, stdin) != NULL){
		stringstream sstr(str);
		vector<string> words;

		string tmp;
		while(sstr >> tmp)
			words.push_back(tmp);

		rep(i, 26){
			rep(j, words.size()){
				if(words[j] == "the" || words[j] == "this" || words[j] == "that"){
					rep(k, strlen(str))
						putchar(isalpha(str[k]) ? (str[k]-'a'+i)%26+'a' : str[k]);
					//puts("");
					i = 26;
					break;
				}

				rep(k, words[j].size())
					words[j][k] = (words[j][k]-'a'+1)%26 + 'a';
			}
		}
	}

	return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <cmath>
using namespace std;
int main(){
  int d, n;
  cin >> d >> n;
  int ret = 0;
  if(d) ret = pow(100, d);
  else ret = 1;

  if(n == 100) ret = ret*101;
  else ret = ret*n;
  cout << ret << endl;
  return 0;
}


Measured memory_bytes: 256
a=int(input())
b=0
c=0
list=list(map(int,input().split()))
for i in range(a-1):
    if list[i]-list[i+1]<=0:
        continue
    elif list[i]-list[i+1]==1:
        if b-list[i+1]==2:
            c=1
            print("No")
            break
        b=list[i]
        if i+2<=a-1:
            if list[i+1]-list[i+2]==1:
                c=1
                print("No")
                break
        
    elif list[i]-list[i+1]>=2:
        c=1
        print("No")
        break
if c==0:
    print("Yes")


Measured memory_bytes: 14400
h, w = map(int, input().split())
s = [input() for _ in range(h)]

dh = [0, 1, 0, -1]
dw = [1, 0, -1, 0]
flag = 0

for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            cnt = 0
            for p in range(4):
                if i + dh[p] < 0 or i + dh[p] >= h or j + dw[p] < 0 or j + dw[p] >= w:
                    continue
                else:
                    if s[i + dh[p]][j + dw[p]] == '#':
                        cnt += 1
            if cnt == 0:
                flag = 1
                break
        if flag == 1:
            break
    if flag == 1:
        print('No')
        break
else:
    print('Yes')
        


Measured memory_bytes: 9232
A, B, H, M = gets.chomp.split.map(&:to_i)

minutes = H * 60 + M

aAngle = 0.5 * minutes
bAngle = 6.0 * M
theta = [(aAngle - bAngle).abs, 360 - (aAngle - bAngle).abs].min

# p aAngle, bAngle, theta

ans = Math.sqrt(A ** 2 + B ** 2 - 2 * A * B * Math.cos(theta * Math::PI / 180))

puts ans.to_s


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

int main(){
    long long n, d;
    cin >> n >>d;
    int ans = 0;
    vector<long double> x(n), y(n);
    for(int i=0; i<n; i++){
        cin >> x[i] >> y[i];
        if( d*d >= x[i]*x[i] + y[i]*y[i] )   ans++;
    }
    cout << ans << endl;
}

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

int main() {
  int a,b,c,d;
  cin >> a >> b >> c >> d;
  int l = a+b;
  int r = c+d;
  if (l > r){
    cout << "Left" << endl;
  }
  else if(l < r){
    cout << "Right" << endl;
  }
  else{
    cout << "Balanced" << endl;
  }
}


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



int main()
{
int N;
cin>>N;
if(N==1){cout<<1<<endl;}
if(N>1&&N<4){cout<<2<<endl;}
if(N>3&&N<8){cout<<4<<endl;}
if(N>7&&N<16){cout<<8<<endl;}
if(N>15&&N<32){cout<<16<<endl;}
if(N>31&&N<64){cout<<32<<endl;}
if(N>63){cout<<64<<endl;}
}


Measured memory_bytes: 256
// AtCoder template
// sabaより胡蝶しのぶさんの方が可愛いのではないか？
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i = 0; i < n; ++i)


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int l,n; cin >> n >> l;
    vector<string> s(n); rep(i,n) cin >> s[i];
    sort(s.begin(), s.end());
    string ans = "";
    rep(i,n) ans += s[i];
    cout << ans << endl;
}

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

long long sum(long long a){
  if(a%4 == 0)return a;
  else if(a%4 == 1)return 1;
  else if(a%4 == 2)return a+1;
  else return 0;
}

int main(void){
  long long  A,B;
  long long  N;

  cin >> A>> B;

  long long ans = sum(B)^sum(A-1);
  cout <<  ans << endl;


}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;


int main()
{

    char a[5];
    while(scanf("%s",a)==1)
    {
        if(a[0]=='9'||a[1]=='9')
            printf("Yes\n");
        else
            printf("No\n");
    }



    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9+7,MAX = 1e5;

int main()
{
	string s;
	cin >> s;
	int n = s.size();
	string ans;
	for(int i =0;i<n;i++)
	{
		if(s[i]=='B')
		{
			if(ans.empty())continue;
			ans.pop_back();
		}
		else
		{
			ans.push_back(s[i]);
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
         
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int  long long
#define rep(i,a,b)    for(int i=a;i<b;i++)
#define repn(i,a,b)   for(int i=a;i>=b;i--)
#define F first
#define S second
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define pb push_back
#define mp  make_pair
#define all(v) (v).begin(), (v).end()
#define endl "\n"
#define mod 1000000007  
#define mod2 998244353 
const int N = 100001; 



void solve(){
    int n;cin>>n;
    int ans;
    ans=n+(n*n)+(n*n*n);
    cout<<ans;
    return ;
}
         
signed main(){
        IOS;
        
        // vi f(2e6+1);
        // f[0]=0;f[1]=0;f[2]=0;f[3]=4;
        // rep(i,4,2e6+1){
        //     f[i]=(f[i-1]+2*f[i-2])%mod;
        //     if(i%3==0)f[i]=(f[i]+4)%mod;
        // }
        int t=1;
        // cin>>t;
        rep(i,0,t){
            solve();
            // int temp;cin>>temp;
            // cout<<f[temp];

            cout<<"\n";
        //   cout<<" * "<<t<<"\n";
        }
    //    return 0;
}

Measured memory_bytes: 3640