akhauriyash/Code-Regression huggingface dataset:
#pragma GCC target ("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define _USE_MATH_DEFINES
#include<iostream>
#include<string>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<random>
#include<functional>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<unordered_map>
#include<climits>
#include<fstream>
#include<complex>
#include<time.h>
#include<cassert>
#include<functional>
#include<numeric>
#include<tuple>

using namespace std;
using ll = int_fast64_t;
using ld = long double;
#define int ll
#define all(a) (a).begin(),(a).end()
#define fs first
#define sc second
#define xx first
#define yy second.first
#define zz second.second
#define H pair<int, int>
#define P pair<int, pair<int, int>>
#define Q(i,j,k) mkp(i,mkp(j,k))
#define rep(i,n) for(int (i) = 0 ; (i) < (n) ; (i)++)
#define rng(i,s,n) for(int (i) = (s) ; (i) < (n) ; (i)++)
#define mkp make_pair
#define vec vector
#define pb emplace_back
#define crdcomp(b) sort(all((b)));(b).erase(unique(all((b))),(b).end())
#define getidx(b,i) lower_bound(all(b),(i))-b.begin()
#define ssp(i,n) (i==(ll)(n)-1?"\n":" ")
#define ctoi(c) (int)(c-'0')
#define itoc(c) (char)(c+'0')
#define pp(x,y) pb(H{x,y})
#define ppp(x,y,z) pb(Q(x,y,z))
#define cdf int q810; cin>>q810; rep(q114,q810) 
//#define endl "\n"
constexpr int mod = 1e9 + 7;
constexpr int Mod = 998244353;
constexpr int MXN = 500000 + 100;
constexpr ld EPS = 1e-10;
constexpr ll inf = 3 * 1e18;
constexpr int Inf = 15 * 1e8;
const vec<int>dx{ -1,1,0,0 }, dy{ 0,0,-1,1 };
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 read() { ll u, k = scanf("%lld", &u); return u; }
string reads() { string s; cin >> s; return s; }
H readh(bool g = 0) { H u; ll k = scanf("%lld %lld", &u.fs, &u.sc); if (g) u.fs--, u.sc--; return u; }
void printh(H t) { printf("%lld %lld\n", t.fs, t.sc); }
bool inarea(H t, int h, int w) { return 0 <= t.fs && t.fs < h && 0 <= t.sc && t.sc < w; }
ll gcd(ll i, ll j) { return j ? gcd(j, i % j) : i; }
ll mod_pow(ll x, ll n, ll p = mod) {
	ll res = 1; x %= p;
	while (n > 0) {
		if (n & 1) res = res * x % p;
		x = x * x % p;
		n >>= 1;
	}
	return res;
}//x^n%p
ll bitcount(ll x) {
	int sum = 0; for (int i = 0; i < 60; i++)if ((1ll << i) & x) sum++;
	return sum;
}
/*constexpr int fn_ = 1000005;
ll fact_[fn_], comp_[fn_];
ll comb(ll x, ll y, ll Mod = mod) {
	if (!fact_[0]) {
		fact_[0] = 1; comp_[0] = 1;
		for (int i = 1; i < fn_; i++)
			fact_[i] = fact_[i - 1] * i % Mod;
		comp_[fn_ - 1] = mod_pow(fact_[fn_ - 1], Mod - 2, Mod);
		for (int i = fn_ - 2; i > 0; i--)
			comp_[i] = comp_[i + 1] * (i + 1) % Mod;
	}
	if (x < y) return 0;
	return fact_[x] * comp_[x - y] % Mod * comp_[y] % Mod;
}*/
//--------------------------------------------------------------
signed main() {
	int n, k; cin >> n >> k;
	n = n % k;
	cout << min(n, k - n) << endl;
}


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

int main() {
    #ifdef DEBUG
        freopen("in.txt", "r", stdin);
    #endif
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    int a[101];
    int n, d, x; cin >> n >> d >> x;
    int sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        int k = 1;
        while (k <= d) {
            sum++;
            k += a[i];
        }
    }

    cout << sum + x << '\n';


    return 0;
}


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

int main() {
  long h,w,ans=0;
  cin >> h >> w;
  vector<vector<long>> c(10,vector<long>(10));
  vector<vector<long>> a(h,vector<long>(w));
  for(long i=0;i<10;i++) for(long j=0;j<10;j++) cin >> c[i][j];
  for(long i=0;i<h;i++) for(long j=0;j<w;j++) cin >> a[i][j];

  for(long i=0;i<10;i++) {
    for(long j=0;j<10;j++) {
      for(long k=0;k<10;k++) c[j][k]=min(c[j][k],c[j][i]+c[i][k]);
    }
  }

  for(long i=0;i<h;i++) for(long j=0;j<w;j++) if(a[i][j]>-1) ans+=c[a[i][j]][1];

  cout << ans << endl;
}

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

typedef long long int ll;
typedef pair<ll,ll> pll;

#define FOR(i,n,m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i,n) FOR(i,n,0)

const ll MOD = 1000000007;
const ll INF = 2<<30;

int main()
{
    string S;
    cin>>S;
    ll sum=0;
    ll w=0;
    REP(i,S.length())
    {
        if(S[i]=='W')
        {
            sum+=(i-w);
            w++;
        }
    }
    cout<<sum<<endl;
    return 0;
}

Measured memory_bytes: 640
#include <stdio.h>

int    main(void)
{
      int    N;
      char    S[100001];
      int    num;
     int    i;
      char    tmp;
      int    count;
      int flag;
  
      num = scanf("%d\n", &N);
      if (num != 1)
          return (0);
  
      for (i=1; i<=N; i++)
    {
          num = scanf("%c", &S[i]);
          if (num != 1)
              return (0);
    }

    flag = 0;
    for (i=1; i<=N - 1; i++)
    {
        if (S[i] == S[i + 1])
            flag = 1;
        else
        {
            flag = 0;
            break ;
        }
    }
    if (flag == 1)
    {
        printf("1");
        return (0);
    }
    
      tmp = '\0';
      count = 0;
    for (i=1; i<=N; i++)
    {
        if (tmp != S[i])
        {
              tmp = S[i];
              count++;
        }
    }
      printf("%d", count);
      return (0);
}


Measured memory_bytes: 256
#include <stdio.h>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
using namespace std;
const int maxn = 2e5+10;
long long A[maxn];
map<long long, int> mp;
int main(){
    int n;
    cin>>n;
    mp.clear();
    long long ans = 0;
    for(int i=1; i<=n; i++){
        cin>>A[i];
        ans += mp[i-A[i]];
        mp[i + A[i]]++;
    }
    mp.clear();
    for(int i=n; i>=1; i--){
        ans += mp[-i-A[i]];
        mp[A[i] - i]++;
    }
    cout<<ans/2<<endl;
    return 0;
}


Measured memory_bytes: 27712
n=int(input())
dict={}
count=0
for i in range(0,n):
  temp=str(input())
  temp=sorted(list(temp))
  temp="".join(temp)
  if temp in dict:
    dict[temp]=dict[temp]+1
    count=count+dict[temp]
  else:
    dict[temp]=0
print(count)

Measured memory_bytes: 17808
#define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
#include <bits/stdc++.h>
#define f first
#define s second
#define ms(a, b) memset(a,b,sizeof(a))
typedef long long ll;

using namespace std;

char _;
int main(){
    cin.sync_with_stdio(0);
    cin.tie(0);

    string a,b;

    cin >> a >> b;

    string c = b.substr(0, b.length()-1);

    if(a==c) cout << "Yes" << "\n";
    else cout << "No" << "\n";

    return 0;
}


Measured memory_bytes: 3664
#include <iostream>
#include <algorithm>
#define maxn 300010
using namespace std;
int n,m=0,e,ans=maxn;
char s[maxn];
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>s;
	for(int i=0;i<n;i++)
		e+=s[i]=='E';
	ans=e-(m=s[0]=='E');
	for(int i=1;i<n;i++){
		m+=s[i]=='E';
		ans=min(ans,i+1+e-2*m);
	}
	cout<<ans<<endl;
}


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

#define rep(i, j, n) for(int i=j;i<n;++i)
#define all(i) i.begin(),i.end()
#define rall(i) i.rbegin(),i.rend()
#define INF 1e9
const int mod = 1e9 + 7;

typedef long long i64;
typedef pair<int, int> pi;

template <class T> using vt = vector<T>;
template <class T> using vvt = vector<vector<T>>;

i64 gcd(i64 n, i64 m) {return (m == 0? n : gcd(m, n % m));}
i64 lcm(i64 n, i64 m) {return (n / gcd(n, m) * m);}
int dx[] = {0, 1, 0, -1, 1, 1, -1, -1};
int dy[] = {1, 0, -1, 0, 1, -1, 1, -1};

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

  int t;
  cin >> t;

  rep(i, 0, t) {
    i64 a, b, c, d;
    cin >> a >> b >> c >> d;

    if(b > a) {
      cout << "No\n";
      continue;
    }
    else if(b > d) {
      cout << "No\n";
      continue;
    }

    i64 tmp = b - gcd(b, d) + a % gcd(b, d);
    if(tmp > c) cout << "No\n";
    else cout << "Yes\n";
  }
}


Measured memory_bytes: 256
#include<stdio.h>
char s[20]={"a"};
int n;
void f(int a,int m){
    int i;
    if(a==n){
        s[a]=0;
        printf("%s\n",s);
        return ;
    }
    for(i=0;i<m;i++){
        s[a]='a'+i;
        f(a+1,m);
        s[a]=0;
    }
    s[a]='a'+m;
    f(a+1,m+1);
    s[a]=0;
    return ;
}
int main(){
    scanf("%d",&n);
    f(1,1);
    return 0;
}

Measured memory_bytes: 1408
def solve():
    n = int(input())
    if n <= 599:
        print(8)
    elif n <= 799:
        print(7)
    elif n <= 999:
        print(6)
    elif n <= 1199:
        print(5)
    elif n <= 1399:
        print(4)
    elif n <= 1599:
        print(3)
    elif n <= 1799:
        print(2)
    else:
        print(1)


solve()


Measured memory_bytes: 9172
n,m = map(int,input().split())
left = 0
right = 1000000000
for _ in range(m):
    a, b = (int(x) for x in input().split())
    left = max(left, a)
    right = min(right, b)
if right-left+1 < 0:
    print(0)
else:
    print(right-left+1)

Measured memory_bytes: 45800
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
typedef long long ll;

using namespace std;

int main() {
    string s, t;
    cin >> s >> t;
    
    string ss = s + s;
    vector<vector<int>> index = vector<vector<int>>(26, vector<int>(0));
    for(int i = 0; i < ss.size(); i++) {
        index[ss[i] - 'a'].push_back(i);
    }
    
    vector<vector<int>> next = vector<vector<int>>(s.size(), vector<int>(26, 0));
    for(int i = 0; i < s.size(); i++) {
        for(int j = 0; j < 26; j++) {
            if(!index[j].empty()) {
                next[i][j] = *upper_bound(index[j].begin(), index[j].end(), i) - i;
            }
        }
    }
    
    int now = 0;
    ll ans = 0;
    for(int i = 0; i < t.size(); i++) {
        if(next[now][t[i] - 'a'] == 0) {
            ans = -1;
            break;
        }
        
        if(i == 0) {
            ans += index[t[i] - 'a'][0] + 1;
            now += index[t[i] - 'a'][0];
            continue;
        }
        
        ans += next[now][t[i] - 'a'];
        now += next[now][t[i] - 'a'];
        now %= s.size();
    }
    
    cout << ans << endl;
    return 0;
}


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

signed main()
{
    int N; cin>>N;
    int ans=0;
    map<vector<int>,int> cnt;
    for(int i=0;i<N;i++){
        string s; cin>>s;
        vector<int> v(26);
        for(char c:s) v[c-'a']++;
        ans+=cnt[v];
        cnt[v]++;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 29952
N = int(input())
A = list(map(int, input().split()))

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

ans = A[0]
for i in range(1, N):
    ans = gcd(ans, A[i])

print(ans)

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

int main() {
  int h, w;
  cin >> h >> w;

  string board[50];

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

  const int dy[8]={1, 0, -1, 0, 1, -1, -1, 1};
  const int dx[8]={0, 1, 0, -1, 1, 1, -1, -1};

  for (int i=0; i<h; i++) {
    for (int j=0; j<w; j++) {
      if (board[i][j]=='#') continue;

      int cnt=0;
      for (int d=0; d<8; d++) {
        int ni=i+dx[d];
        int nj=j+dy[d];

        if (ni<0 or h<=ni) continue;
        if (nj<0 or w<=nj) continue;
        if (board[ni][nj]=='#') cnt++;
      }

      board[i][j]='0'+cnt;
    }
  }

  for (int i=0; i<h; i++) {
    cout << board[i] << endl;
  }
}

Measured memory_bytes: 256
import Control.Monad
import Data.List
main = do
    [n, m] <- map read . words <$> getLine
    l <- map (map (read :: String -> Int) . words) <$> replicateM m getLine
    print $ (\[x, y] -> sub2 x y) $ foldl1' sub l
    where sub [a, b] [c, d] = [max a c, min b d]
          sub2 a b | b - a < 0 = 0
                   | otherwise = b - a + 1


Measured memory_bytes: 100732
import java.math.BigDecimal;
import java.util.Scanner;

public class Main {
	private static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {
		double a = sc.nextDouble();
		double b = sc.nextDouble();
		int C = sc.nextInt();

		double S = (a * b * Math.sin(Math.toRadians(C))) /2 ;
		double c = Math.sqrt(Math.pow(a, 2) + Math.pow(b, 2) - 2 * a * b * Math.cos(Math.toRadians(C)));
		double L = a + b + c;
		double h = 2 * S / a;

		System.out.println(BigDecimal.valueOf(S).toPlainString() + " " + BigDecimal.valueOf(L).toPlainString() + " " + BigDecimal.valueOf(h).toPlainString());

	}

}

Measured memory_bytes: 28308
n, k = map(int, input().split())
A = list(map(int, input().split()))
a = [0] * n
for i in range(n-1):
    for j in range(i+1, n):
        if A[i] > A[j]:
            a[i] += 1

a2 = [0] * n
for i in range(n):
    for j in range(n):
        if A[i] > A[j]:
            a2[i] += 1

print(int(sum(a2)*(k*(k-1)//2) + sum(a)*k) % (10**9+7))

Measured memory_bytes: 9268
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

const int INF = (int)1e9;

int main(){
  int n;

  scanf("%d",&n);

  for(int i=0;i<n;i++){
    int x,y,b,p,ans=INF,calc;
    scanf("%d%d%d%d",&x,&y,&b,&p);

    for(int i=b;i<=6;i++){
      for(int j=p;j<=6;j++){
	calc = i*x+j*y;
	if(i>=5 && j>=2) calc = calc*4/5;
	ans = min(ans,calc);
      }
    }

    cout << ans << endl;
  }

  return 0;
}

Measured memory_bytes: 1212
import sys
import os

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A = il()
    ans = 0
    for a in A:
        while a % 2 == 0:
            ans += 1
            a //= 2

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3956
#include<algorithm>
#include<string>
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;
 
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};
 
 
int main(){
    
    string S;
    cin >> S;
    int f=0;
    int i=2;
    while(i<=3){
        REP(j,S.size()-i+1){
            string s=S.substr(j,i);
            if(s[0]==s[i-1]){
                cout << j+1 << " " << j+i << endl;
                j=S.size();
                f=1;
                i=3;
            }
        }
        i++;
    }
    if(f==0){
        cout << -1 << " " << -1 << endl;
    }
 
    return 0;
}

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

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

  int out=0;

  rep(l, n){
    int dej=l;
    vector<int> to(n);
    rep_in(r, l+1, n){
      if(to[r-dej]+dej < to[l+dej]){
        to[r]=to[r-dej]+dej;
      }else{
        int j = max(r, to[l+dej]);
        while(j<n && s[j-r+l]==s[j]) j++;
        to[r]=j;
        dej=r-l;
        if(j-r>out && l+j-r<=r) out=j-r;
      }
    }
  }

  cout<<out<<endl;
}


Measured memory_bytes: 256
def gs() gets.chomp end
def gi() gets.to_i end
def gsmi() gets.chomp.split.map(&:to_i) end
def ang(n) Array.new(n){gsmi} end
def debug(k,v) puts "#{k}: #{v}" end
def desc(ar) ar.sort!{|x,y|y<=>x} end
def min(a,b) a<=b ? a : b end
def max(a,b) a>=b ? a : b end
def sum(ar) ar.inject(:+) end

$stdin = File.open('input.txt') if File.exist?('input.txt')
a,b,c,d = gsmi
puts [a*c,a*d,b*c,b*d].max


Measured memory_bytes: 14380
import java.util.Arrays;
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner stdIn=new Scanner(System.in);
		int N=stdIn.nextInt();
		int A[]=new int[N];
		int z=0,y=0;
		long ans=0;
		while(z<N){
			A[z]=stdIn.nextInt();
			if(A[z]<0){
				A[z]*=-1;
				y++;
			}
			ans+=A[z];
			z++;
		}
		Arrays.sort(A);
		if(y%2==1)
			ans-=A[0]*2;
		System.out.println(ans);
	}
}

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

const int MOD = 1000000007;


int gcd(int a, int b) {
    if (b==0) return a;
   	else return gcd(b, a%b);
}
int lcm(int a, int b) {
    return a * b / gcd(a, b);
}


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

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
char arr[1005][1005];
int dp[1005][1005];
int main(){
    int a,b;
    cin>>a>>b;
    for(int x=0; x<a; x++){
        for(int y=0; y<b; y++){
            cin>>arr[x][y];
           
        }
        
    }
    dp[0][0]=1;
    for(int x=1; x<a; x++){
         if(arr[0][x]=='#'){
                dp[0][x]=0;
            }else{
           dp[0][x]=dp[0][x-1];
        }
        
    }
   
        
        for(int x=1; x<b; x++){
         if(arr[x][0]=='#'){
                dp[x][0]=0;
            }else{
           dp[x][0]=dp[x-1][0];
        }
          
        }
        cout<<endl;
        for(int x=1; x<a; x++){
          for(int y=1; y<b; y++){
             if(arr[x][y]=='#'){
                dp[x][y]=0;
            }else{
           dp[x][y]=(dp[x-1][y]+dp[x][y-1])%1000000007;
        }
       
    }
   
    }
    
    cout<<dp[a-1][b-1];
}
    
    

Measured memory_bytes: 5120
#include <iostream>
#include <cstdio>
#include <cmath>
#define INF 100000000
using namespace std;

int main(){
	int cost[100][100],tim[100][100];
	int n,m,l;
	while(1){
		cin >> n >> m;
		if(n == 0 && m == 0) break;
	for(int i = 0;i < m;i++){
		for(int j = 0;j < m;j++) {
			cost[i][j] = INF;
			tim[i][j] = INF;
		}
		cost[i][i] = 0;
		tim[i][i] = 0;
	}
	for(int i = 0;i < n;i++){
		int a,b,c,d;
		cin >> a >> b >> c >> d;
		cost[a - 1][b - 1] = c;
		cost[b - 1][a - 1] = c;
		tim[a - 1][b - 1] = d;
		tim[b - 1][a - 1] = d;
	}
	for(int k = 0;k < m;k++){
		for(int i = 0;i < m;i++){
			for(int j = 0;j < m;j++) {
				cost[i][j] = min(cost[i][j],cost[i][k] + cost[k][j]);
				tim[i][j] = min(tim[i][j],tim[i][k] + tim[k][j]);
			}
		}
	}
	cin >> l;
	for(int i = 0;i < l;i++){
		int a,b,c;
		cin >> a >> b >> c;
		if(!c) cout << cost[a - 1][b - 1] << endl;
		else cout << tim[a - 1][b - 1] << endl;
	}
	}
	return 0;
}

Measured memory_bytes: 3112
class WeightedUnionFind:
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0]*size
        self.diff_weight = [0]*size
    
    def find(self, x):
        if self.parent[x] == x:
            return x
        r = self.find(self.parent[x])
        self.diff_weight[x] += self.diff_weight[self.parent[x]]
        self.parent[x] = r
        return r
    
    def unite(self, x, y, w):
        w += self.weight(x) - self.weight(y)
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            x, y = y, x
            w = -w
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        self.parent[y] = x
        self.diff_weight[y] = w

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def weight(self, x):
        self.find(x)
        return self.diff_weight[x]

    def diff(self, x, y):
        return self.weight(y)-self.weight(x)

N, M = map(int,input().split())
uf = WeightedUnionFind(N)
for _ in range(M):
    l,r,d = map(int,input().split())
    l -= 1
    r -= 1
    if uf.same(l,r) and uf.diff(l,r) != d:
        print("No")
        exit()
    uf.unite(l,r,d)
print("Yes")


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

int main(){
    int n;
    cin >>n ;
    int a[n];
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    int ans=0;
    for(int i=0;i<n-1;i++){
        for(int j=i+1;j<n;j++){
            ans+=a[i]*a[j];
        }
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a) for(int i = 0; i < a; i++)
#define all(v) v.begin(), v.end()
#define dcout cout << fixed << setprecision(15)
#define arep(i, a) for(auto i : a)
#define F first
#define S second
#define VE vector<int>
#define pb(x) push_back(x)
#define MOD 1000000007
#define INF 10000000000
#define int long long
#define KETA(n) floor(log10(n) + 1)
using namespace std;
signed main() {
    int a, b, c;
    cin >> a >> b >> c;
    cout << c / a * b;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <sstream>
#include <cstring>
#include <cstdlib>

using namespace std;

#define ALL(c) c.begin(),c.end()
#define RALL(c) c.rbegin(),c.rend()
#define SORT(x) sort((x).begin(),(x).end())
#define REP(i,x,y) for(int i=(x);i<(y);++i)
#define MP(a,b) make_pair((a),(b))
#define debug(x) #x << "=" << (x)
 
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define dump(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define dump(x)
#endif

typedef long long int ll;
typedef pair<int,int> pii;
//template<typename T> using vec=std::vector<T>;

const int INF=1<<30;
const long long int INF_=1LL<<58;
const double EPS=1e-9;
const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
	os << "[";
	for (const auto &v : vec) {
		os << v << ",";
	}
	os << "]";
	return os;
}

void Solve(){
	while(true){
		int n,t,l,b,grid[101]={};
		cin >> n >> t >> l >> b;
		if(n==0&&t==0&&l==0&&b==0) break;

		REP(i,0,l){
			int idx; cin >> idx;
			grid[idx]=1;
		}

		REP(i,0,b){
			int idx; cin >> idx;
			grid[idx]=2;
		}

		double dp[102][101]={};
		dp[0][0]=1;
		REP(i,0,t){
			REP(j,0,n){
				REP(k,1,7){
					int idx=j+k;
					if(idx>n) idx=n-(idx-n);
					if(grid[idx]==0) dp[i+1][idx]+=dp[i][j]/6;
					else if(grid[idx]==1) dp[i+2][idx]+=dp[i][j]/6;
					else dp[i+1][0]+=dp[i][j]/6;
				}
			}
		}

		double ans=0;
		REP(i,0,t+1) ans+=dp[i][n];
		cout << setprecision(10) << fixed << ans << endl;
	}
}

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

Measured memory_bytes: 1344
#include <iostream>
#include <iomanip>
#include <complex>
using namespace std;
#define X real()
#define Y imag()
typedef complex<double> P;

int main(){
    while(1){
        int n;
        cin >> n;
        if(n == -1) break;

        P p(0, 0), dir(1, 0);
        for(int i=0; i<n; i++){
            p += dir;
            dir = p *P(0, 1);
            dir /= abs(dir);
        }
        cout << fixed << setprecision(10);
        cout << p.X << endl << p.Y << endl;
    }
    return 0;
}



Measured memory_bytes: 3296
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0; i<n; i++)
typedef long long ll;
typedef long long unsigned int llu;
ll MOD = 1000000007;
ll INF = 1000000009;

ll a[100010];
ll dp[100010];

void solve(){

    ll n;
    cin >> n;
    rep(i,n){
        cin >> a[i];
    }
    rep(i,100010){
        dp[i]=INF;
    }
    rep(i,n){
        auto itr = lower_bound(dp,dp+n,a[i]);
        *itr=min(*itr, a[i]);
        /*
        rep(j,n){
            cout << dp[j] << " ";
        }
        cout << endl;
        */
    }
    
    auto itr = lower_bound(dp,dp+n,INF);
    cout << itr-dp << endl;

}


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



Measured memory_bytes: 4792
import std.stdio;
import std.string;
import std.conv;
import std.typecons;
import std.algorithm;
import std.functional;
import std.bigint;
import std.numeric;
import std.array;
import std.math;
import std.range;
import std.container;
import std.ascii;
void times(alias pred)(int n) {
    foreach(i; 0..n) pred();
}
auto rep(alias pred, T = typeof(pred()))(int n) {
    T[] res = new T[n];
    foreach(ref e; res) e = pred();
    return res;
}

void main() {
    int H, W;
    readf("%d %d\n", &H, &W);

    H.rep!(() => readln.chomp.map!(c => c=='#').array).repeat.take(2).enumerate.each!((a) {
        H.iota.map!(i => W.iota.map!(j =>
            j==0   ? a.index==0 :
            j==W-1 ? a.index==1 :
            (i%2==a.index || a.value[i][j])
        ).map!(b => b ? '#':'.').to!string).each!writeln;
        if (a.index==0) writeln();
    });
}


Measured memory_bytes: 2044
#include<bits/stdc++.h> 
typedef long long LL;
using namespace std;
namespace IO{
	const int __buffsize = 1000000;char __buff[__buffsize];char *__buffS, *__buffT;
	char getch(){if (__buffS == __buffT){__buffT = (__buffS = __buff) + fread(__buff,1,__buffsize,stdin);if (__buffS == __buffT) return EOF;}return *__buffS++;}
	#define getch getchar
	int read(){int T = 0,f = 1;char c = getchar();while((c<'0'||c>'9')&&(c!='-'))c=getchar();if(c=='-')f=-1,c=getchar();while(c>='0'&&c<='9'){T=((T<<1)+(T<<3))+c-48;c=getchar();}return T*f;}
	void write(int x){if(x < 0) putchar('-'),x = -x;if (x>=10) write(x / 10);putchar((x % 10)+'0');}
	void writeln(int x){write(x);puts("");}
};
using namespace IO;
inline bool cmp(pair<int,int> a,pair<int,int> b){
	return a.second<b.second;
}
#define mid ((l+r)>>1)
#define lson (o<<1)
#define rson (o<<1|1)
const int maxn = 300005;
int t[300005 << 2],add[300005 << 2];
int h,w;
pair<int,int> a[maxn],q1[maxn],q2[maxn];
int top1,top2;
#define mp make_pair
void build(int o,int l,int r){
	if (l==r) {
		t[o] = w - a[l].second;
		return ;
	}
	build(lson,l,mid);
	build(rson,mid+1,r);
	add[o] = 0;
	t[o] = max(t[lson],t[rson]);
}
void del(int o,int l,int r,int x,int y,int s){
	if(x>y) return;
	if (l == x && y == r){
		t[o] += s;
		add[o] += s;
		return;
	}
	if (l<=x&&y<=mid) del(lson,l,mid,x,y,s); else
	if (mid+1<=x&&y<=r) del(rson,mid+1,r,x,y,s); else
	del(lson,l,mid,x,mid,s),del(rson,mid+1,r,mid+1,y,s);
	t[o] = max(t[lson],t[rson]) + add[o];
}
 
int n,ans;
 
void solve(){
	sort(&a[1],&a[n+1],cmp);
	build(1,0,n);
	q1[0].first = q2[0].first = -1;
	q1[top1 = 1] = mp(0,0);
	q2[top2 = 1] = mp(0,w);
	for (int i=1;i<=n;i++){
		ans = max(ans,t[1] + a[i].second);
		if (a[i] . first <= (w>>1)){
			while (top1 && a[i].first > q1[top1] . second){
				del(1,0,n,q1[top1-1].first+1,q1[top1].first,q1[top1].second - a[i].first);
				top1--;
			}
			q1[++top1] = mp(i-1,a[i].first);
		} else{
			while (top2 && a[i].first < q2[top2] . second){
				del(1,0,n,q2[top2-1].first+1,q2[top2].first,a[i].first - q2[top2].second);
				top2--;
			}
			q2[++top2] = mp(i-1,a[i].first);
		}
		q1[++top1] = mp(i,0);
		q2[++top2] = mp(i,w);
	}
	ans = max(ans,t[1] + h);
}
 
int main(){
	w = read();
	h = read();
	n = read();
	for (int i=1;i<=n;i++)
		a[i].first = read(),a[i].second = read();
	solve();
	swap(w,h);
	for (int i=1;i<=n;i++)
		swap(a[i].first,a[i].second);
	solve();
	printf("%lld\n",ans*2);
	return 0;	
}

Measured memory_bytes: 15488
using System;
    using System.Linq;
    using System.Collections.Generic;
    using System.Text.RegularExpressions;
    using System.Text;
     
    public class Program
    {
        public void Proc() {
            Reader.IsDebug = false;
            string ans = string.Join(string.Empty, Reader.ReadLine().Split(' ').Select(a=>a.ToUpper()[0]));
            Console.WriteLine(ans);

        }

        public class Reader {
            public static bool IsDebug = true;
            private static System.IO.StringReader SReader;
            private static string InitText = @"




atcoder beginner contest





";
            public static string ReadLine() {
                if(IsDebug) {
                    if(SReader == null) {
                        SReader = new System.IO.StringReader(InitText.Trim());
                    }
                    return SReader.ReadLine();
                } else {
                    return Console.ReadLine();
                }
            }
        }
        public static void Main(string[] args)
        {
            Program prg = new Program();
            prg.Proc();
        }
    }

Measured memory_bytes: 13268
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
import math
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
from collections import deque

inf = 10 ** 15
mod = 10 ** 9 + 7

h,w,k = map(int, input().split())
s = [input() for i in range(h)]
ans = [[0 for j in range(w)]for i in range(h)]
count = 1
for i in range(h):
    counts = 0
    for a in range(w):
        if s[i][a] == '#':
            counts+=1
    if counts == 0:
        if count != 1:
            for j in range(w):
                ans[i][j] = ans[i-1][j]
    elif counts == 1:
        if count != 1:
            for j in range(w):
                ans[i][j] = count
        else:
            for g in range(i+1):
                for j in range(w):
                    ans[g][j] = count
        count+=1
    else:
        if count != 1:
            end = 0
            endcount = 0
            for b in range(w):
                if s[i][w-1-b] == '#':
                    endcount+=1
                    if endcount == 2:
                        end = w-1-b
                        break
                ans[i][w-1-b] = count
            count+=1
            for j in range(end+1):
                if s[i][j] == '#':
                    ans[i][j] = count
                    count+=1
                else:
                    ans[i][j] = count
        else:
            end = 0
            endcount = 0
            for b in range(w):
                if s[i][w - 1 - b] == '#':
                    endcount += 1
                    if endcount == 2:
                        end = w-1-b
                        break
                for g in range(i+1):
                    ans[g][w-1-b] = count
            count += 1
            for j in range(end + 1):
                if s[i][j] == '#':
                    for g in range(i + 1):
                        ans[g][j] = count
                    count += 1
                else:
                    for g in range(i + 1):
                        ans[g][j] = count

for i in range(h):
    print(*ans[i], sep=' ')


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

#define int long long
#define rep(i,l,r) for(int i=(int)(l);i<(int)(r);i++)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)x.size())
template<class T>bool chmax(T &a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a,T b){if(a>b){a=b;return 1;}return 0;}

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;

const int inf = 1LL<<60;
const int mod = 1e9 + 7;
const double eps = 1e-9;

/*{
  }*/

bool check(int x, vi &a, vi &f, int k){
  int n = sz(a);
  int res = 0;
  rep(i, 0, n){
    res += max(0LL, a[i]-x/f[i]);
  }
  return res <= k;
}

signed main(){
  int n, k;
  cin >> n >> k;

  vi a(n), f(n);
  rep(i, 0, n) cin >> a[i];
  rep(i, 0, n) cin >> f[i];

  sort(all(a));
  sort(all(f));
  reverse(all(f));

  int l = -1, r = 1e13;
  while(r-l > 1){
    int m = (l+r)/2;
    if(check(m, a, f, k)) r = m;
    else l = m;
  }

  cout << r << endl;

  return 0;
}


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

const long long MAX = -1e18;
const long long MAXN = 3e5 + 5;
long long dp_f[MAXN],dp_e[MAXN],a[MAXN];

priority_queue<long long , vector<long long> , greater<long long> > que;
priority_queue<long long>pque;

void Slove_f(int n){
	long long sum_f = 0;
	for(int i = 1;i <= 3 * n;i++){
		que.push(a[i]);
		sum_f += a[i];
		dp_f[i] = sum_f;
		if(que.size() > n){
			sum_f -= que.top();
			que.pop();
			dp_f[i] = sum_f;
		}
	}

}

void Slove_e(int n){
	long long sum_e = 0;
	for(int i = 3 * n;i >= 1;i--){
		pque.push(a[i]);
		sum_e += a[i];
		dp_e[i] = sum_e;
		if(pque.size() > n){
			sum_e -= pque.top();
			pque.pop();
			dp_e[i] = sum_e;
		}
	}

}

int main(){
	int n;
	scanf("%d",&n);
	for(int i = 1;i <= 3 * n;i++) scanf("%lld",&a[i]);

	Slove_f(n);	
	Slove_e(n);

	long long ans = MAX;
	for(int i = n;i <= 2 * n;i++){
		ans = max(ans,dp_f[i] - dp_e[i + 1]);
	}
	printf("%lld",ans);
}

Measured memory_bytes: 9588
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a),i##_end=(b);i<=i##_end;++i)
#define per(i,a,b) for(int i=(b),i##_end=(a);i>=i##_end;--i)
#define For(i,a,b) for(int i=(a),i##_end=(b);i<i##_end;++i)
#define fo(i,a) for(__typeof(a.begin())i=a.begin();i!=a.end();++i)
#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
typedef double ld;
typedef long long L;
typedef vector<int> VI;
typedef pair<int,int> pa;
const int N=311,P=998244353;
int n,a[N];
int f[N][2*N*N+5];
inline void inc(int &x,int y){x=x+y>=P?x+y-P:x+y;}
inline void dec(int &x,int y){x=x-y<0?x-y+P:x-y;}
int main(){
	cin>>n;
	rep(i,1,n)cin>>a[i];
	int s=N*N;
	f[0][s]=1;
	rep(i,0,n-1){
		rep(J,-i*300,i*300){
			int j=J+s,t=f[i][j];
			inc(f[i+1][j+a[i+1]],t);
			inc(f[i+1][j-a[i+1]],2ll*t%P);
		}
	}
	int ans=1;
	rep(i,1,n)ans=3ll*ans%P;
	rep(j,0,s)dec(ans,3ll*f[n][s+j]%P);
	//cout<<ans<<endl;
	memset(f,0,sizeof f);
	f[0][s]=1;
	rep(i,0,n-1){
		rep(J,-i*300,i*300){
			int j=J+s,t=f[i][j];
			inc(f[i+1][j+a[i+1]],t);
			inc(f[i+1][j-a[i+1]],t);
		}
	}
	inc(ans,3ll*f[n][s]%P);
	cout<<ans<<endl;
}

Measured memory_bytes: 235392
#include<bits/stdc++.h>
 using namespace std;
#define INF 1000000000
#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
typedef long long LL;
LL R,C;
int N;
map<LL,int>x;
map<LL,int>y;
LL x1[100001];
LL x2[100001];
LL yy1[100001];
LL y2[100001];
int imos[800500];

//typedef pair<int,int>P;
//vector<P>line;

int trans(LL xx,LL yy){
	if(yy==0)return xx;
	if(yy==C)return 600010-xx;
	if(xx==0)return 800015-yy;
	return 200005+yy;
}

void plot(int a,int b,int a2,int b2){
	int aa=trans(a,b);
	int bb=trans(a2,b2);
	if(aa>bb)swap(aa,bb);
	imos[aa]++;
	imos[bb]--;
	//cout<<aa<<" "<<bb<<endl;
}

bool check(LL x,LL y){
	if(x==0||y==0)return true;
	if(x==R||y==C)return true;
	return false;
}

int main(){
	cin>>R>>C>>N;
	x[0]++;
	y[0]++;
	x[R]++;
	y[C]++;
	REP(i,N){
		cin>>x1[i]>>yy1[i]>>x2[i]>>y2[i];
		x[x1[i]]++;
		x[x2[i]]++;
		y[yy1[i]]++;
		y[y2[i]]++;
	}

	
	int x_size=0;
	for(auto it: x){
		x[it.first]=x_size;x_size++;
		//cout<<it.first<<" it "<<it.second<<endl;
	}
	int y_size=0;
	for(auto it:y){
		y[it.first]=y_size;y_size++;
	}
	REP(i,800500){
		imos[i]=0;
	}
	R=x[R];
	C=y[C];
	
	

	REP(i,N){
		x1[i]=x[x1[i]];
		yy1[i]=y[yy1[i]];
		x2[i]=x[x2[i]];
		y2[i]=y[y2[i]];
	}

	
	
	REP(i,N){
		if(check(x1[i],yy1[i])&&check(x2[i],y2[i])){
			//cout<<i<<" aaa ";
			plot(x1[i],yy1[i],x2[i],y2[i]);
		}
	}
	
	REP(i,800500){
		if(i==0)continue;
		imos[i]+=imos[i-1];
	}
	REP(i,N){
		if(check(x1[i],yy1[i])&&check(x2[i],y2[i])){
			int a=trans(x1[i],yy1[i]);
			int b=trans(x2[i],y2[i]);
			//cout<<i<<x1[i]<<yy1[i]<<x2[i]<<y2[i]<<endl;
			//cout<<a<<" "<<b<<endl;
			if(a>b)swap(a,b);
			//cout<<imos[a]<<" "<<imos[b]<<endl;
			if(imos[a]!=imos[b]+1){
				cout<<"NO"<<endl;
				return 0;
			}
		}
	}
	cout<<"YES"<<endl;
    return 0;
}

Measured memory_bytes: 31232
# https://atcoder.jp/contests/abc099/tasks/abc099_b

a, b = map(int, input().split())

num = 0
for i in range(1, 999):
    if b - a == i + 1:
        num = i
        break
ans = num * (num + 1) // 2 - a
print(ans)

Measured memory_bytes: 38384
S = list(input())
#print(S)
list = []
temp = ""
for i in range(len(S)):
    if S[i] == 'A' or S[i] == 'T' or S[i] == 'G' or S[i] == 'C':
        temp += S[i]
        list.append(temp)
    else:
        list.append(temp)
        temp = ""
#print(list)
ans = []
for i in range(len(list)):
    ans.append(len(list[i]))
#print(ans)
print(max(ans))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;


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

  int ans = 0;
  REP(i,n+1) {
    REP(j,n+1) {
      int z = (y - (i*10000) -(j*5000)) / 1000;
      if((i+j+z) == n && z >= 0) {
        cout << i << " " << j << " " << z <<endl;
        return 0;
      }
    }
  }

  cout << -1 << " " << -1 << " " << -1 <<endl;
  
}

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

int main(){

  string s;
  cin >> s;
  int cnt = 0;

  for (int i = 0; i < s.size(); i++) {
    if (s[i] == 'A') {
      cnt = i;
      break;
    }
  }

  for (int i = s.size();i > 0; i--) {
    if (s[i] == 'Z') {
      cout << i - cnt + 1 << endl;
      return 0;
    }
  }



}


Measured memory_bytes: 640
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
using namespace std;
int main(){
	long long int n;
	cin >>n;
	int t=1;
	rep(i,sqrt(n+1))
		if (n%(i+1)==0)
			t=i+1;
	cout << (n/t)+(t)-2<<endl;

}

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

#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<limits.h>

using namespace std;
int main(){
  int k,n,ii;
  string s;
  char c;
  char* res;
  cin >> k >> s >> n;
  c = s [n-1];
  res = (char*)malloc(sizeof(char)*(k+1));
  memset(res,0,sizeof(char)*(k+1));

  for(ii=0;ii<k;ii++){
    if(c == s[ii]){
      res[ii] = s[ii];
    }
    else{
      res[ii] = '*';
    }
  }
  cout << res << endl;
  return 0;
}


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

using namespace std;

int main(){
    string str[2];
    for(auto&& i : str){
        cin >> i;
    }
    map<string, int> cnt;
    for(auto&& i : str){
        int n;
        cin >> n;
        cnt[i] = n;
    }
    string input;
    cin >> input;
    cnt[input]--;
    cout << cnt[str[0]] << " " << cnt[str[1]] << "\n";
}

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

using namespace std;

typedef long long ll;

const ll INF = 1e17;

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

  vector<vector<ll>> dist(N, vector<ll>(N, INF));

  for (int i = 0; i < M; i++) {
    int A, B;
    ll C;
    cin >> A >> B >> C;

    A--;
    B--;
    dist[A][B] = C;
    dist[B][A] = C;
  }

  for (int k = 0; k < N; k++) {
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        if (i == j) {
          dist[i][j] = 0;
        } else {
          dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
        }
      }
    }
  }

  vector<vector<ll>> edge(N, vector<ll>(N, INF));
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      if (i == j) {
        edge[i][j] = 0;
      } else if (dist[i][j] <= L){
        edge[i][j] = 1;
      }
    }
  }

  for (int k = 0; k < N; k++) {
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        if (i == j) continue;
        edge[i][j] = min(edge[i][j], edge[i][k] + edge[k][j]);
      }
    }
  }

  int Q;
  cin >> Q;
  for (int i = 0; i < Q; i++) {
    int s, t;
    cin >> s >> t;

    s--;
    t--;
    if (edge[s][t] < INF) {
      cout << (edge[s][t] - 1) << endl;
    } else {
      cout << -1 << endl;
    }
  }

  return 0;
}


Measured memory_bytes: 1920
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {

    	Scanner sc = new Scanner(System.in);
    	int a,b,c;
    	int count=0;
    	a = sc.nextInt();
    	b = sc.nextInt();
    	c = sc.nextInt();

    	for(int i=a;i<=b;i++){
    		if(c%i == 0)count++;
    	}
    	System.out.println(count);
    }
}

Measured memory_bytes: 26228
#include <iostream>
#include <vector>
 
using namespace std;
 
#define MAX 110
 
struct Page{
    int sx,sy,tx,ty;
    string next;
    Page(int sx,int sy,int tx,int ty,string next)
	: sx(sx),sy(sy),tx(tx),ty(ty),next(next) {}
};
 
vector<Page> vec[MAX];
 
void init(){
    for(int i = 0 ; i < MAX ; i++){
	vec[i].clear();
    }
}
 
int main(){
    int N,W,H,b,sx,sy,tx,ty;
    string str[MAX],s;
 
    while(cin >> N,N){
	int p = 0;
	cin >> W >> H;
	init();
	for(int i = 0 ; i < N ; i++){
	    cin >> str[i] >> b;
	    for(int j = 0 ; j < b ; j++){
		cin >> sx >> sy >> tx >> ty >> s;
		vec[i].push_back(Page(sx,sy,tx,ty,s));
	    }
	}
	int m,w,h,now = 0;
	vector<int> now_page;
	now_page.push_back(now);
	string next;
	cin >> m;
	for(int I = 0 ; I < m ; I++){
	    cin >> s;
	    if(s == "click"){
		bool found = false;
		cin >> w >> h;
		for(int i = 0 ; i < vec[now_page[p]].size() ; i++){
		    sx = vec[now_page[p]][i].sx, sy = vec[now_page[p]][i].sy;
		    tx = vec[now_page[p]][i].tx, ty = vec[now_page[p]][i].ty;
		    next = vec[now_page[p]][i].next;
		    if(sx <= w && w <= tx && sy <= h && h <= ty){
			for(int j = 0 ; j < N ; j++){
			    if(str[j] == next){
				now = j;
				found = true;
				break;
			    }
			}
		    }
		    if(found){
			p++;
			while(p < now_page.size()){
			    now_page.pop_back();
			}
			now_page.push_back(now);
			break;
		    }
		}
	    }else if(s == "show"){
		cout << str[now_page[p]] << endl;
	    }else if(s == "back"){
		if(p > 0) p--;
	    }else{
		if(p+1 < now_page.size()) p++;
	    }
	}
    }
    return 0;
}

Measured memory_bytes: 3176
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb emplace_back
#define INF (1e9+1)
//#define INF (1LL<<59)

int main(){
	int n,ma,mb;
	cin>>n>>ma>>mb;
	
	vector<int> a(n),b(n),c(n);
	rep(i,n)cin>>a[i]>>b[i]>>c[i];
	
	int dp[401][401];
	rep(i,401)rep(j,401)dp[i][j]=INF;
	dp[0][0] = 0;
	
	for(int i=1;i<=n;i++){
		int A=a[i-1],B=b[i-1],C=c[i-1];
		for(int j=400;j>=0;j--){
			for(int k=400;k>=0;k--){
				if(j-A<0||k-B<0)continue;
				dp[j][k] =min( dp[j-A][k-B]+C , dp[j][k] );
			}
		}
	}
	int res = INF;
	int t=1;
	while(t*ma<=400&&t*mb<=400){
		res = min(res,dp[t*ma][t*mb]);
		t++;
	}

	if(res==INF)cout<<-1<<endl;
	else cout<<res<<endl;
}

Measured memory_bytes: 896
#include <iostream>
#include <climits>
#include <stack>
#include <queue>
#include <string>
#include <set>
#include <map>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string.h>
#include <random>
#include <iomanip>
#include <limits>
 
using namespace std;
 
typedef long long ll;
 
typedef pair<ll,ll> P;
long long int INF = 1e18;
double Pi = 3.141592653589;
const int mod = 1000000007;
// memset(a,0,sizeof(a)); →全部０にする
 
vector<int> G[100005];
std::vector<P> tree[100010];
 
int dx[8]={1,0,-1,0,1,1,-1,-1};
int dy[8]={0,1,0,-1,1,-1,-1,1};
 
#define p(x) cout<<x<<endl;
#define el cout<<endl;
#define pe(x) cout<<x<<" ";
#define re(i,a,b) for(i=a;i<=b;i++)
 
ll i,j,k,l,ii,jj;
ll n,m,a,b,c,d,ans,num,ddx,ddy;
ll x[100005],y[100005];
char s[300004];


int main(){
	cin>>s;
	for(i=0;i<=2;i++){
		if(s[i]=='o')a++;
	}
	p(700+100*a);
	return 0;
}

Measured memory_bytes: 4992
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define eps 1e-9
using namespace std;
struct point{
	double x,y;
	void read(){scanf("%lf%lf",&x,&y);}
	void write(){printf("%.9f %.9f\n",x,y);}
	point(double X=0.0,double Y=0.0):x(X),y(Y){}
	point operator +(const point a)const{return point(x+a.x,y+a.y);}
	point operator -(const point a)const{return point(x-a.x,y-a.y);}
	point operator *(double a)const{return point(x*a,y*a);}
	point operator /(double a)const{return point(x/a,y/a);} 
};
double dis(point a){return sqrt(a.x*a.x+a.y*a.y);}
double dot(point a,point b){return a.x*b.x+a.y*b.y;}
double cross(point a,point b){return a.x*b.y-a.y*b.x;}

point p1,p2;
int main()
{
	int n;
	p1.read();p2.read();
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		point p;
		p.read();
		double len=dot(p2-p1,p-p1)/dis(p2-p1);
		((p1+(p2-p1)/dis(p2-p1)*len)*2-p).write();
	}
	return 0;
}



Measured memory_bytes: 3248
#include <bits/stdc++.h>
#define Rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef int64_t intl;


int main(){
 int N,K;
  cin >>N>>K;
  vector<int> P(N);
  vector<double> kitai(N);
  Rep(i,N){
    cin >> P.at(i);
    kitai.at(i) = (P.at(i) + 1.0)/2.0;
  }
  double maxA=0;
  double sum=0;
  
  Rep(i,K){
    sum += kitai.at(i);
  }
  
  maxA = sum;
  
  Rep(j,N-K){
    sum -= kitai.at(j);
   sum += kitai.at(j+K);
    maxA = max( maxA , sum );
  }
  cout << fixed << setprecision(7);
  cout << maxA;
}


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

#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

using namespace std;
typedef long long ll; typedef vector<ll> VI; typedef pair<int,int> pii;
void dbg(){ cerr << "\n"; }  template <typename T,typename ...T2> void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }
template <class T> void amin(T& a,T b){ a=min(a,b);}
template <class T> void amax(T& a,T b){ a=max(a,b);}

int main()
{
	//cin.tie(0); ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	VI h(n);
	rep(i,n) cin >>h[i];
	ll ans =0;
	int hmx = *max_element(all(h));
	
	auto hh =h;
	while(1){
		bool msw=true;
		if(count(all(hh),0)==n) break;
		rep(j, n){
			if(hh[j] > 0){
				if(msw) ans++;
				hh[j]--; msw=false;
			}else{
				msw=true;
			}
		}
		//for(auto x :hh) printf("%d, ",x); printf("     %d\n",ans);
	}
	cout << ans <<"\n";
	return 0;
}




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

#define rep(i,n) for (int i=0; i< int (n); i++)
int main(){
long long int n, k;
cin >> n>> k;
if(k==1 || n==k) cout << 0 << endl;
else if(n<k) cout << min(n, abs(k-n)) << endl;
else cout << min(n%k, abs(k-(n%k))) << endl;


}

Measured memory_bytes: 256
#include <stdio.h>

using namespace std;

int main() {

    char s[4];
    scanf("%s", s);

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

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

    return 0;
}


Measured memory_bytes: 128
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<tuple>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<deque>
#include<cmath>
#include<stack>
#include<string.h>
#include <iomanip>
#define rep(i,n) for(int i = 0;i<n;i++)
using ll = long long; 
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
	string s,t;
	cin >> s >> t;
	bool ans =true;
	rep(i,s.size()) {
		if(s[i] != t[i]) ans = false;
	}
	if(ans) cout << "Yes" << endl;
	else cout << "No" << endl;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
#define rep1(i,N) for(int i=1;i<int(N);++i)
#define all(a) (a).begin(),(a).end()		//sort(all(vi S)) sort(all(string S))

typedef long long ll;
typedef vector<int> vi;
typedef set<int> seti;
typedef vector<string> vs;

const int MOD = 1e9+7;
const int INF = 1e9;

int main() {
	int H,W;
	string ans="Possible";
	cin>>H>>W;
	vector<string> A(H);
	rep(i,H)cin>>A[i];
	rep(x,H-1)rep(y,W-1){
		if(A[x+1][y]=='#'&&A[x][y+1]=='#')ans="Impossible";
	}
	cout<<ans<<endl;
}
//右だけ、下だけっていうの以外だったらNo

Measured memory_bytes: 256