akhauriyash/Code-Regression huggingface dataset:
n,m = map(int,input().split())

mod = 10**9 + 7
l = 10**6
fac = [1]*l
facr = [1]*l

for i in range(l-1):
    fac[i+1] = fac[i]*(i+1)%mod
facr[l-1] = pow(fac[l-1],mod - 2,mod)
for i in range(1,l)[::-1]:
    facr[i-1] = facr[i]*i%mod

def combi(N,K):
    return fac[N]*facr[N-K]%mod*facr[K]%mod
def per(N,K):
    return fac[N]*facr[N-K]%mod

ans = 0
for i in range(n+1):
    ans += combi(n,i)*per(m,i)%mod*(per(m-i,n-i)**2%mod)%mod*((-1)**i)%mod
    ans %= mod
print(ans)


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

int main() {
	int N;
	cin >> N;
	// N の-2進表現
	vector<int> ans;
	int temp = N;
	/*
	cout << (-5 / -2) << endl; //  2
	cout << (-5 % -2) << endl; // -1 .. あまりは0, -1のいずれかであり, 1にはならない.
	cout << (5 / -2) << endl;  // -2
	cout << (5 % -2) << endl;  //  1 .. あまりは0, -1のいずれかであり, 1にはならないと思ったがそうではないようだ....
	*/
	if (temp == 0) {
		cout << 0 << endl;
		return 0;
	}
	while (temp != 0) {
		// temp = a * (-2) + b;
		if ((temp - 1) % (-2) == 0) {
			ans.push_back(1);
			temp = (temp -1) / (-2);
		} else {
			ans.push_back(0);
			temp = temp / (-2);
		}
	}
	for (int i=ans.size()-1; i>=0; --i) {
		cout << ans[i];
	}
	cout << endl;
	return 0;
}



Measured memory_bytes: 256
# -*- coding: utf-8 -*-
S = str(input())
a = S[0]
b = S[1]
c = S[2]
d = S[3]
f = S[5]
g = S[6]
i = S[8]
j = S[9]
D = int(d) + 1
print(str(a)+str(b)+str(c)+str(D)+"/"+str(f)+str(g)+"/"+str(i)+str(j))


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int main(void)
{
	int i,j,k,left[4]={0},right[4]={0};
	double s1,s2;
	while(scanf("%lf %lf",&s1,&s2)!=EOF) {
		if(s1>=1.1) right[0]++;
		else if(s1>=0.6) right[1]++;
		else if(s1>=0.2) right[2]++;
		else right[3]++;
		if(s2>=1.1) left[0]++;
		else if(s2>=0.6) left[1]++;
		else if(s2>=0.2) left[2]++;
		else left[3]++;
	}
	for(i=0;i<4;i++) cout<<right[i]<<" "<<left[i]<<endl;
}
	
	

Measured memory_bytes: 3220
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<queue>
#include<stack>
#include<string>
#include<map>

using namespace std;
const int INF = 1<<30;
typedef long long int ll;

int main(){
	string s;cin>>s;
	map<char, bool> count;
	for(int i=0;i<(int)s.size();i++){
		count[s[i]]=true;
	}
	cout << ((count['N']!=count['S']||count['W']!=count['E'])?"No":"Yes")<<endl;
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

long long HELL(int n){
	if(n==0){return 100000;}
	return ((HELL(n-1)*21/20+999)/1000)*1000;
}

int main(){
	int n;
	cin>>n;
	cout<<HELL(n)<<endl;

	return 0;
}

Measured memory_bytes: 1156
#include "bits/stdc++.h"
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
using ll = long long int;

ll mpow(ll a, ll n, ll mod)
{
	ll r = 1;
	while (n) {
		if (n&1) r = r*a%mod;
		a = a*a%mod;
		n >>= 1;
	}
	return r;
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	
	int n; cin >> n;
	int a[n][2];
	bool good = 0;
	for (int i = 0; i < n; ++i) {
		cin >> a[i][0] >> a[i][1];
		if (i < 2) continue;
		good = 1;
		for (int j = i-2; j <= i; ++j)
			good &= a[j][0] == a[j][1];
		if (good) return cout << "Yes\n", 0;
	}
	cout << "No\n";
}

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

int main()
{
  string s;
  int a,b;
  cin >> a >> b >> s;
  s[b - 1] = s[b - 1]  - 'A' + 'a';
  cout << s << endl;
  return 0;
}


Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (lli i = 0; i < (n); i++)
#define rrep(i, n) for (lli i = (n)-1; i >= 0; i--)

void solve(long long N, long long K)
{
  int ans = 0;
  if (N == 0)
  {
    cout << 1 << endl;
    return;
  }
  while (N)
  {
    N /= K;
    ans++;
  }
  cout << ans << endl;
}

int main()
{
  long long N;
  scanf("%lld", &N);
  long long K;
  scanf("%lld", &K);
  solve(N, K);
  return 0;
}


Measured memory_bytes: 256
use std::io;


fn main() {
    let n = read_one::<usize>();
    let an = read::<usize>();

    let mut ans: usize = 0;
    let mut r = 0;
    let mut s = 0;

    for l in 0..n {
        while r < n && (s ^ an[r] == (s + an[r])) {
            s += an[r];
            r += 1;
        }

        ans += r - l;
        if l == r { r += 1; }
        else { s -= an[l]; }
    }

    println!("{}", ans);
}


#[allow(dead_code)]
fn read<T>() -> Vec<T>
where T:
std::str::FromStr,
T::Err: std::fmt::Debug {

    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.split_whitespace()
        .map(|s| s.trim().parse().unwrap())
        .collect()
}

#[allow(dead_code)]
fn read_one<T>() -> T
where T:
std::str::FromStr,
T::Err: std::fmt::Debug {

    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.trim().parse().unwrap()
}

Measured memory_bytes: 10492
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
 
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<pair<int, int> > vpii;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
#define INF 0x3f3f3f3f
#define MOD 998244353
#define EPSILON 0.00001
#define f first
#define s second
#define pb push_back
#define mp make_pair
 
#define FOR(i, a, b) for (int i=(a); i<=(signed)(b); i++)
#define F0R(i, a) for (int i=0; i<(signed)(a); i++)
#define RFOR(i, a, b) for (int i=(a); i >= b; i--)

#define MN 100005
int n, m;
pair<pll, ll> ed[MN];

bool mar[MN];
vector<int> tree[3*MN];
void upd(int node, int a, int b, int l, int r, int val){
    if(a > r || b < l || a > b) return;

    //cout << "doing " << node << " " << a << " " << b << "\n";

    if(l <= a && b <= r){
        tree[node].pb(val);
        return;
    }

    upd(node*2, a, (a+b)/2, l, r, val);
    upd(node*2+1, 1+(a+b)/2, b, l, r, val);
}

ll dist[MN];
priority_queue<pll, vector<pll>, greater<pll> > pq;

void que(int node, int a, int b, int i, pll top){
    if(a > i || b < i || a > b) return;

    for(auto u : tree[node]){
        if(mar[u]) continue;
        pq.push({top.f+ed[u].s, ed[u].f.s});
        mar[u] = true;
    }
    if(a == b) return;
    que(node*2, a, (a+b)/2, i, top);
    que(node*2+1, 1+(a+b)/2, b, i, top);
}

ll dijk(){
    memset(dist, -1, sizeof dist);
    pq.push({0, 1});
    while(!pq.empty()){
        pll top = pq.top();
        pq.pop();
        int cn = top.s;
        if(dist[cn] != -1) continue;
        dist[cn] = top.f;
        //cout << "on " << cn << "\n";
        if(cn == n) return dist[cn];
        que(1, 1, n, cn, top);
    }
    return -1;
}

//REP WITH LL
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    F0R(i, m){
        cin >> ed[i].f.f >> ed[i].f.s >> ed[i].s;
        upd(1, 1, n, ed[i].f.f, ed[i].f.s, i);
    }

    cout << dijk() << "\n";

    return 0;
}


Measured memory_bytes: 23828
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    ll n, z = 328;
    cin >> n;
    for (ll i = 1; i * i <= n; i++) if (n % i == 0) {
        z = min(z, max((ll)to_string(i).length(), (ll)to_string(n / i).length()));
    }
    cout << z;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
string n;
int a,i;
int main()
{
    cin>>n;
    a=n.length();
   for(i=0;i<a;i++)
   {
       if(n[i]==',')
       cout<<" ";
       else
       cout<<n[i];
   }
   cout<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cctype>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <utility>
#include <string>
#include <functional>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <bitset>
#define mp make_pair
#define YES cout<<"YES"<<endl
#define Yes cout<<"Yes"<<endl
#define NO cout<<"NO"<<endl
#define No cout<<"No"<<endl
#define rep(i,n) for(ll i=0;i<n;i++)
#define INF (1<<30)
#define LLINF (1LL<<60)
//#define MOD 998244353
#define MOD 1000000007
#define PI 3.14159265358979
using ll = long long;
using namespace std;

int main(){
    ll count[100005]={},n;
    ll sum=0;
    cin>>n;
    rep(i,n){
        ll t;
        cin>>t;
        count[t]++;
        sum+=t;
    }

    ll q;
    cin>>q;
    rep(i,q){
        ll b,c;
        cin>>b>>c;
        sum-=b*count[b];
        sum+=c*count[b];
        cout<<sum<<endl;
        count[c]+=count[b];
        count[b]=0;
    }
    return 0;
}



Measured memory_bytes: 4372
k,n = map(int,input().split())
a = list(map(int,input().split()))
b = []

for i in range(1,n):
    b.append(a[i]-a[i-1])
b.append(k-a[-1]+a[0])
b = sorted(b)
b1 = b[:-1]
print(sum(b1))

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

int main() {
  long long int n,m;
  cin>>n>>m;
  if(n<m-1 || m+1<n){
    cout<<0<<endl;
    return 0;
  }
  
  long long int ans=1;
  if(n==m)ans*=2;
  for(long long int i=1;i<=max(n,m);i++){
    if(i<=min(n,m))ans*=i;
    if(ans>=1000000007)ans%=1000000007;
    ans*=i;
    if(ans>=1000000007)ans%=1000000007;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
Module Module1

    Sub Main()
        Dim readline As String
        Dim len As Integer = 0
        Dim hogehoge() As String

        hogehoge = Console.ReadLine.Split(" "c)

        Dim log As Double = Math.Log(CType(hogehoge(0), Double), CType(hogehoge(1), Double))
        Dim ans As Integer

        If Math.Ceiling(log) <= 0 Then
            ans = 1

        End If

        Console.WriteLine(Math.Floor(log + 1))


    End Sub


End Module


Measured memory_bytes: 11220
N,K = map(int,input().split())
A = list(map(int, input().split()))
B = len(set(A))
from collections import Counter
if B <= K:
    print(0)
    exit()
C = Counter(A)

C = sorted(C.items(), key=lambda x:x[1],reverse=True)

count = 0
for key, value in C[K:]:
    count += value

print(count)

Measured memory_bytes: 49788
using System;
using System.Collections.Generic;
using System.Linq;
using BitArray = System.Collections.BitArray;
using BigInteger = System.Numerics.BigInteger;

namespace AtCoderProject
{
    public class Program
    {
        public object Calc()
        {
            var line = consoleReader.SplitInt();
            var M = line[0];
            var K = line[1];

            var T = (int)Math.Pow(2, M);
            if (T <= K) return -1;
            if (M == 1) return K == 0 ? "1 0 0 1" : "-1";

            var list = Enumerable.Range(0, T).Where(i => i != K).ToArray();
            var listR = list.Reverse().ToArray();
            return string.Join(" ", list.Concat(new[] { K }).Concat(listR).Concat(new[] { K }));
        }

        public const int mod = 1000000007;
        #region いつもの
        private readonly ConsoleReader consoleReader;
        public Program() : this(new ConsoleReader()) { }
        public Program(ConsoleReader consoleReader) { this.consoleReader = consoleReader; }
        static void Main() => Console.WriteLine(new Program().Calc()); static string MultiLine<T>(IEnumerable<T> source) => string.Join("\n", source);
        #endregion
    }

    #region Console
    public class ConsoleReader { public virtual string String() => Console.ReadLine(); public int Int() => int.Parse(String()); public long Long() => long.Parse(String()); public ulong ULong() => ulong.Parse(String()); public double Double() => double.Parse(String()); public string[] Split() => String().Split().ToArray(); public int[] SplitInt() => String().Split().Select(int.Parse).ToArray(); public long[] SplitLong() => String().Split().Select(long.Parse).ToArray(); public ulong[] SplitULong() => String().Split().Select(ulong.Parse).ToArray(); public double[] SplitDouble() => String().Split().Select(double.Parse).ToArray(); public IEnumerable<string> Repeat(int count) { for (int i = 0; i < count; i++) yield return String(); } public IEnumerable<int> RepeatInt(int count) { for (int i = 0; i < count; i++) yield return Int(); } public IEnumerable<long> RepeatLong(int count) { for (int i = 0; i < count; i++) yield return Long(); } public IEnumerable<string[]> RepeatSplit(int count) { for (int i = 0; i < count; i++) yield return Split(); } public IEnumerable<int[]> RepeatSplitInt(int count) { for (int i = 0; i < count; i++) yield return SplitInt(); } }
    #endregion
}

Measured memory_bytes: 32088
# Your code here!
n=gets.to_f


s=n**0.5
i=s.floor
n=n.to_i

loop{
    
   if n%i==0 
       break
   else
       i-=1
   end
    
    
    
    
    
if i==1
    i=1
    break
end
    
    
    
    
}

ss=n/i


puts ss.to_s.length










Measured memory_bytes: 1788
CONST = 10**9 + 7
n,m = map(int,input().split())

dp = [-1 for _ in range(n+1)]
dp[0] = 1
dp[1] = 1
for _ in range(m):
  a = int(input())
  dp[a] = 0


for i in range(2,n+1):
  if dp[i] == 0:
    continue
  dp[i] = (dp[i-1] + dp[i-2]) % CONST
print(dp[n])




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


int main() {
    int n,m;
    cin>>n>>m;
    vector<int> a(n);
    int sum=0;
    rep(i,n){
        cin>>a.at(i);
        sum+=a.at(i);
    }
    int count=0;
    rep(i,n){
        if(a.at(i)*4*m>=sum){
            count++;
        }
    }
    if(count>=m){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long n, a, b;
  	cin>>n>>a>>b;
  	if((a%2 && b%2) || (a%2==0 && b%2==0)){
    	cout<<(b-a)/2<<'\n';
      	return 0;
    }
  	cout<<min(a-1,n-b)+1+(b-a-1)/2<<'\n';
  	return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC114A
{
    class Program
    {
        static void Main(string[] args)
        {
           
           int  x = int.Parse(Console.ReadLine());

            if (x == 7 || x == 5 || x == 3)

                Console.WriteLine("YES");

            else
                Console.WriteLine("NO");

            Console.ReadKey();
        }
    }
}



Measured memory_bytes: 13140
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
typedef long long ll;
const int mod = 1e9 + 7;
int main()
{
  int N;
  cin >> N;
  ll T[N], A[N];
  FOR(i,0,N) cin >> T[i];
  FOR(i,0,N) cin >> A[i];
  if(N==1) {
    if(A[0]==T[0]) {
      cout << 1 << endl;
    } else {
      cout << 0 << endl;
    }
    return 0;
  }
  if(N==2) {
    if(T[1]!=A[0]) {
      cout << 0 << endl;
      return 0;
    }
  }
  bool kakutei[N];
  FOR(i,0,N) kakutei[i] = false;
  kakutei[0] = kakutei[N-1] = true;
  int mxj = 0;
  FOR(i,1,N-1) {
    if(T[i]!=T[i-1]) {
      kakutei[i] = true;
      mxj = i;
    }
  }
  for(int i = N - 1; i > 0; i--) {
    if(A[i-1] != A[i]) {
      if(i - 1 < mxj) {
        cout << 0 << endl;
        return 0;
      }
      kakutei[i-1] = true;
    }
  }
  ll ans = 1;
  FOR(i,0,N) {
    if(kakutei[i]) continue;
    ans *= min(T[i], A[i]);
    ans %= mod;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1920
#include <iostream>
#include <vector>

int main(){
    int n;
    std::cin >> n;
    std::vector<int> Adj[n];
    //input_graph
    int u, k, v;
    for(int i=0; i<n; i++){
        std::cin >> u >> k;
        for(int j=0; j<k; j++){
            std::cin >> v;
            Adj[u-1].push_back(v);
        }
    }

    //input_A
    int A[n][n];
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            A[i][j] = 0;
        }
    }
    for(int i=0; i<n; i++){
        int len = Adj[i].size();
        for(int j=0; j<len; j++){
            A[i][Adj[i][j]-1] = 1;
        }
    }

    //output_A
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(j+1==n)  std::cout << A[i][j] << '\n';
            else        std::cout << A[i][j] << " ";
        }
    }
    return 0;
}


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

int mod = 998244353;

map<pair<long long, long long>, long long> mp;
long long modpow(long long x, long long y){
    if (mp[{x, y}]) return mp[{x, y}];
    if (y == 0) return 1;
    if (y % 2) {
        long long res = x * modpow(x, y - 1) % mod;
        mp[{x, y}] = res;
        return res;
    }
    long long res = modpow(x, y / 2) * modpow(x, y / 2) % mod;
    mp[{x, y}] = res;
    return res;
}

int main(){
    int k, n;
    cin >> k >> n;
    vector<long long> fac(4001, 1);
    for (int i = 1; i <= 4000; i++) fac[i] = fac[i - 1] * i % mod;
    vector<long long> div(4000, 1);
    for (int i = 2; i <= 4000; i++) div[i] = (mod - (mod / i) * div[mod % i] % mod) % mod;
    long long all =  fac[k + n - 1] * modpow(fac[n] * fac[k - 1] % mod, mod - 2) % mod;
    vector<long long> cmbs(1001);
    cmbs[0] = all;
    for (int i = 1; i <= 1000; i++) cmbs[i] = (((cmbs[i - 1] * (n - 2 * i + 2) % mod) * (n - 2 * i + 1) % mod) * div[k + n - 2 * i + 1] % mod) * div[k + n - 2 * i] % mod;
    for (int num = 2; num <= 2 * k; num++){
        int cnt = 0;
        for (int i = 1; i <= k; i++){
            if (num - i > k) continue;
            if (num < 2 * i) break;
            cnt++;
        }
        vector<long long> cmb(cnt + 1, 1);
        for (int i = 1; i <= cnt; i++) cmb[i] = (cmb[i - 1] * (cnt - i + 1) % mod) * div[i] % mod;
        long long res = all;
        for (int i = 1; i <= k; i++){
            if (n < 2 * i) break;
            if (i > cnt) break;
            //cntからi個を選ぶ
            long long a = cmb[i];
            //残りの選び方
            long long b = cmbs[i];
            res += mod + (1 - 2 * (i % 2)) * (a * b % mod + mod) % mod;
            res %= mod;
        }
        cout << res << endl;
    }
}

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

class Node {
	public:
		int location;
		int p, l, r;
		Node() {};
};

class Point {
	public:
		int id, x, y;
		Point() {};
		Point(int id, int x, int y): id(id), x(x), y(y) {}
};

const int NMAX = 500000;
const int QMAX = 20000;
const int NIL = -1;
int n;
Point p[NMAX];
Node t[NMAX];
int q;
int np = 0;
vector<int> ans;

bool lessX(const Point &p1, const Point &p2) { return p1.x < p2.x; }
bool lessY(const Point &p1, const Point &p2) { return p1.y < p2.y; }

int makeKDtree(int l, int r, int depth) {
	if (l >= r) { return NIL; };
	int num = np++;

	if (depth % 2 == 0) {
		sort(p + l, p + r, lessX);	
	} else {
		sort(p + l, p + r, lessY);	
	}

	int mid = (l + r) / 2;
	t[num].location = mid;	
	t[num].l = makeKDtree(l, mid, depth + 1);
	t[num].r = makeKDtree(mid + 1, r, depth + 1);

	return num;
}

void find(int sx, int tx, int sy, int ty, int tnum, int depth) {
	if (tnum == NIL) { return; }
	Point point = p[t[tnum].location];
	if (sx <= point.x && point.x <= tx && sy <= point.y && point.y <=ty) {
		ans.push_back(point.id);
	}
	
	if (depth % 2 == 0) {
		if (point.x >= sx) {
			find(sx, tx, sy, ty, t[tnum].l, depth + 1);
		}
		if (tx >= point.x) {
			find(sx, tx, sy, ty, t[tnum].r, depth + 1);
		}
	} else {
		if (point.y >= sy) {
			find(sx, tx, sy, ty, t[tnum].l, depth + 1);
		}
		if (ty >= point.y) {
			find(sx, tx, sy, ty, t[tnum].r, depth + 1);
		}
	}
}

int main() {
	scanf("%d", &n);
	int x, y;
	for (int i = 0; i < n; i++) {
		scanf("%d %d", &x, &y);
		p[i] = Point(i, x, y);
		t[i].l = t[i].r = t[i].p = NIL;
	}

	makeKDtree(0, n, 0);

	scanf("%d", &q);
	int sx, tx, sy, ty;
	for (int i = 0; i < q; i++) {
		scanf("%d %d %d %d", &sx, &tx, &sy, &ty);
		ans.clear();
		find(sx, tx, sy, ty, 0, 0);
		sort(ans.begin(), ans.end());
		for (int a = 0; a < ans.size(); a++) {
			printf("%d\n", ans[a]);
		}
		printf("\n");
	}

	return 0;
}



Measured memory_bytes: 16480
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
typedef int ll;
typedef pair<ll,ll> P;
typedef double db;
const ll INF = 0xfffffff;
ll n,k;
ll c[5000],r[5000];
ll d[5000];
ll a[10000],b[10000];
ll tmax[5000];
vector<ll> G[5000];
priority_queue<P,vector<P>,greater<P> > q;queue<P> q2;
int main()
{
	scanf("%d%d",&n,&k);
	for(ll i=0;i<n;i++) scanf("%d%d",&c[i],&r[i]);
	for(ll i=0;i<k;i++){
		scanf("%d%d",&a[i],&b[i]);
		a[i]--;
		b[i]--;
		G[a[i]].push_back(b[i]);
		G[b[i]].push_back(a[i]);
	}
	fill(d,d+n,INF);
	d[0]=0;
	tmax[0]=0;
	q.push(P(d[0]+c[0],0));
	while(!q.empty()){
		P p=q.top();
		q.pop();
		if(d[p.second]+c[p.second]<p.first) continue;
		q2.push(P(p.second,r[p.second]));
		while(!q2.empty()){
			P t=q2.front();
			q2.pop();
			if(d[t.first]>p.first){
				d[t.first]=p.first;
				tmax[t.first]=t.second;
				q.push(P(d[t.first]+c[t.first],t.first));
			}
			if(t.second) for(ll i=0;i<G[t.first].size();++i) if(d[G[t.first][i]]>p.first||tmax[G[t.first][i]]<t.second-1) q2.push(P(G[t.first][i],t.second-1));
		}
	}
	printf("%d\n",d[n-1]);
}

Measured memory_bytes: 45256
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define Sort(Array) sort(Array.begin(), Array.end())
#define Reverse(a) reverse(a.begin(), a.end())
#define out(ans) cout << ans << endl;
const int MOD = 1000000007;
const int INF = 2147483647;
const ld PI = 3.14159265358979323846;

//------------↓------------- M -------------- E ---------------- M --------------- O ---------------↓--------------//
// コンパイル 
// g++ -std=c++1z
//
// -------型変換--------
// int を string に変換
// string s = to_string(n);
// string を int に変換
// int n = stoi(s);
//
// -------二分探索---------
// k以上の値が最初に現れる時のイテレータ
// lower_bound(data.begin(), data.end(), k)
// kより大きい値が最初の現れる時のイテレータ O(logN)
// upper_bound(data.begin(), data.end(), k)
// kがdataに存在するかをtrue or falseで返す O(logN)
// binary_search(data.begin(), data.end(), k)
// 
//
//
//
//
//
// 
//------------↑------------- M -------------- E ---------------- M --------------- O ---------------↑--------------//



int main() {

    int N; cin >> N;
    ll a[N]; rep(i,N) cin >> a[i];

    ll ans = 1000;
    int i = 0;
    while (i < N) {

        int k = i;
        while (1) {
            if (k == N || a[i] < a[k]) {
                break;
            }
            ++k;
        }
        
        bool flag = true;
        for (int j = i; j < k; ++j) {
            if (a[i] > a[j]) {
                flag = false;
            }
        }
        if (k == N) {
            flag = false;
        }

        if (flag) {
            ll stock = ans / a[i];
            ans -= a[i] * stock;
            i = k;
            ans += a[i] * stock;
        } else {
            ++i;
        }
    }

    cout << ans << endl;
    


    return 0;
}



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

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;

#define pb push_back

ll a, b, c, d;

ll f() {
	set<ll> res;
	res.insert(a * c);
	res.insert(a * d);
	res.insert(b * c);
	res.insert(b * d);
	return *res.rbegin();
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
   cin >> a >> b >> c >> d;
   cout << f();
   return 0;
}

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

int main(){
  int A,B;
  cin >> A >> B;
  if(A>B){cout << (2*A)-1 << endl;}
  else if(B>A){cout << (2*B)-1 << endl;}
  else{cout << A+B << endl;}
  return 0;
}

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

#define pb push_back
#define mp make_pair
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()

using namespace std;

typedef long long int64;
typedef pair<int, int> ii;
typedef vector<int> vi;

const int maxn = 1010 * 2010;

int main() {
  int n;
  cin >> n;
  vi a(n);
  int s = 0;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    s += a[i];
  }
  bitset<maxn> u;
  u[0] = true;
  for (int i = 0; i < n; ++i)
    u |= (u << a[i]);
  int res = -1;
  for (int i = maxn - 1; i >= 0; --i) if (u[i]) {
//    cerr << i << "\n";
    if (abs(2 * i - s) < abs(2 * res - s))
      res = i;
  }
  cout << res << "\n";
  return 0;
}

Measured memory_bytes: 1400
package main

import (
	. "fmt"
)

// github.com/EndlessCheng/codeforces-go
func main() {
	a := [3]int{}
	var k int
	Scan(&a[0], &a[1], &a[2], &k)
	ans := 0
	for i, v := range a {
		if k <= v {
			ans += (1 - i) * k
			break
		}
		ans += (1 - i) * v
		k -= v
	}
	Print(ans)
}


Measured memory_bytes: 1756
import java.util.*;

class TwoNode{
	int p;
	int l,r;
	TwoNode(){
		p = -1;
		l = r = -1;
	}
}

public class Main {
	Scanner sc = new Scanner(System.in);
	TwoNode[] T;
	int n;
	int id, left, right;
	int root;
	
	public void input() {
		n = sc.nextInt();
		T = new TwoNode[n];
		for(int i=0; i<n; i++) { T[i] = new TwoNode(); }
	}
	
	public void solve() {
		for(int i=0; i<n; i++) {
			id = sc.nextInt();
			left = sc.nextInt();
			right = sc.nextInt();
			if(left != -1) {T[left].p = id;}
			if(right != -1) {T[right].p = id;}
			T[id].l = left;
			T[id].r = right;
		}
	}
	
	public void output() {
		for(int i=0; i<n; i++) { if(T[i].p == -1) root = i; }
		System.out.println("Preorder");
		preOutput(root);
		System.out.println("\nInorder");
		inOutput(root);
		System.out.println("\nPostorder");
		postOutput(root);
		System.out.println();
	}
	
	public void preOutput(int u) {
		if(u == -1) {
			return;
		}else {
			System.out.print(" "+u);
			preOutput(T[u].l);
			preOutput(T[u].r);
		}
	}
	
	public void inOutput(int u) {
		if(u == -1) {
			return;
		}else {
			inOutput(T[u].l);
			System.out.print(" "+u);
			inOutput(T[u].r);
		}
	}
	
	public void postOutput(int u) {
		if(u == -1) {
			return;
		}else {
			postOutput(T[u].l);
			postOutput(T[u].r);
			System.out.print(" "+u);
		}
	}
	
	public static void main(String[] args) {
		Main obj = new Main();
		obj.input();
		obj.solve();
		obj.output();
	}
}



Measured memory_bytes: 26292
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
P = list(map(int, input().split()))

INF = 2**31 - 1
N0 = 1 << (n-1).bit_length()
seg_min = [INF]*(N0 << 1)
seg_max = [0]*(N0 << 1)

def update_min(i, x):
    i += N0
    seg_min[i] = x
    while i > 1:
        y = seg_min[i ^ 1]
        if y <= x:
            break
        i >>= 1
        seg_min[i] = x
            
def query_min(l, r):
    res = INF
    l += N0
    r += N0
    while l < r:
        if r & 1:
            res = min(res, seg_min[r-1])
        if l & 1:
            res = min(res, seg_min[l])
            l += 1
        l >>= 1
        r >>= 1
 
    return res

def init_min(original):
    for i, x in enumerate(original):
        update_min(i, x)
        
def update_max(i, x):
    i += N0
    seg_max[i] = x
    while i > 1:
        y = seg_max[i ^ 1]
        if y >= x:
            break
        i >>= 1
        seg_max[i] = x
            
def query_max(l, r):
    res = 0
    l += N0
    r += N0
    while l < r:
        if r & 1:
            res = max(res, seg_max[r-1])
        if l & 1:
            res = max(res, seg_max[l])
            l += 1
        l >>= 1
        r >>= 1
 
    return res

def init_max(original):
    for i, x in enumerate(original):
        update_max(i, x)
        
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

init_min(P)
init_max(P)

uf = UnionFind(n-k+1)

for i in range(n-k):
  m = query_min(i, i+k+1)
  M = query_max(i, i+k+1)
  if m == P[i] and M == P[i+k]:
    uf.unite(i, i+1)

q = -1
s = 0
for i in range(k-1):
  if P[i] < P[i+1]:
    s += 1
if s == k-1:
  q = 0
for i in range(n-k):
  s -= int(P[i] < P[i+1])
  s += int(P[i+k-1] < P[i+k])
  if s == k-1:
    if q == -1:
      q = i+1
    else:
      uf.unite(q, i+1)
ans = uf.group_count()
print(ans)

Measured memory_bytes: 111236
#include<bits/stdc++.h>
using namespace std;
int main()
{
	string x;
	cin>>x;
	if(x[0]=='S'||x[0]=='s')
	{
		cout<<"Cloudy";
	}
	else if(x[0]=='C'||x[0]=='c')
	{
		cout<<"Rainy";
	}
	else if(x[0]=='R'||x[0]=='r')
		cout<<"Sunny";

}


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


struct _dice
{
	int num[6];
};

//type definition
typedef struct _dice dice_t;

//structure declaration
dice_t dice1;
dice_t dice2;

//function
void vertical()
{
	int cmp = dice2.num[0];
	dice2.num[0] = dice2.num[4];
	dice2.num[4] = dice2.num[5];
	dice2.num[5] = dice2.num[1];
	dice2.num[1] = cmp;
}

void horizontal()
{
	int cmp = dice2.num[1];
	dice2.num[1] = dice2.num[2];
	dice2.num[2] = dice2.num[4];
	dice2.num[4] = dice2.num[3];
	dice2.num[3] = cmp;
}

//main
int main()
{
	for (int i = 0; i < 6; i++)
	{
		cin >> dice1.num[i];
	}
	for (int i = 0; i < 6; i++)
	{
		cin >> dice2.num[i];
	}

	for (int i = 0; i < 5; i++)
	{
		for (int j = 0; j < 5; j++)
		{
			if (dice1.num[0] == dice2.num[0]) break;
			vertical();
		}
		for (int j = 0; j < 5; j++)
		{
			if (dice1.num[1] == dice2.num[1]) break;
			horizontal();
		}
	}

	if (dice1.num[0] == dice2.num[0] && dice1.num[1] == dice2.num[1] && dice1.num[2] == dice2.num[2])
	{
		cout << "Yes" << endl;
	}
	else cout << "No" << endl;

	return 0;
}



Measured memory_bytes: 3100
# -*- coding: utf-8 -*-

## Library

from fractions import gcd
import math
from math import ceil,floor
import collections

## input

# n=int(input())
# A,B,C,D=map(int, input().split())
# string = input()
# list = list(map(int, input().split()))

N=int(input())

## Logic

ans=N%10

## output

if ans == 3:
    print("bon")
elif ans == 0 or ans == 1 or ans == 6 or ans == 8:
    print("pon")
else:
    print("hon")


Measured memory_bytes: 72912
using System;
using System.Linq;
class c
{
    static void Main()
    {
        {
            int n = int.Parse(Console.ReadLine());
            var a = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            Console.WriteLine(Math.Pow(3, n) - Math.Pow(2, a.Count(f => f % 2 == 0)));
        }
    }
}

Measured memory_bytes: 14036
# ITP1_2_C
# Sorting 
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_2_B
# encode : utf-8
numberList = list(map(int, input().split()))
numberList.sort()
print("{0[0]} {0[1]} {0[2]}".format(numberList))


Measured memory_bytes: 5580
N = int(input())
H = list(map(int, input().split()))

ans = "Yes"
for n in range(N):
    if n >= 1:
        if H[n] > H[n - 1]:
            H[n] -= 1
        if n < N-1 and H[n] > H[n + 1]:
            ans = "No"
            break

print(ans)
        

Measured memory_bytes: 14396
x, n = map(int, input().split())
ps = list(map(int, input().split()))
pss = [i for i in range(-1000, 1000)]
ps = list(filter(lambda i: i not in ps, pss))
ans = x

for i, p in enumerate(ps):
    temp = abs(x-p)
    if i == 0:
        mins = temp
        ans = p
    else:
        if mins > temp:
            mins = temp
            ans = p
        elif mins == temp:
            if ans > p:
                ans = p

print(ans)

Measured memory_bytes: 9044
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
using namespace __gnu_pbds;
using namespace std;
typedef tree<
    pair<int, int>,
    null_type,
    less_equal<pair<int, int>>,
    rb_tree_tag,
    tree_order_statistics_node_update>
    ordered_set;
#define int long long
#define double long double
#define all(a) (a).begin(), (a).end()
#define x first
#define y second
#define lb(v, z) lower_bound(all(v), z)
#define ub(v, z) upper_bound(all(v), z)
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define rdp(i, a, b) for (int i = (a); i >= (b); i--)
#define rlt(i, a, b) for (int i = (a); i < (b); i++)
#define cns(z) cout << (z) << ' '
#define cnl(z) cout << (z) << '\n'
#define M1 1000000007
#define M2 998244353
#define MAXN 300005
#define INF (1ll << 60)
#define endl "\n"
#define garr(ip)       \
    for (auto &x : ip) \
        cin >> x;
#define parr(ip)          \
    for (auto &x : ip)    \
        cout << x << " "; \
    cout << endl;
#define nl cout << endl
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pair<int, int>> vp;

void solve(int testCaseNumber = 1)
{
    int n, x;
    cin >> x >> n;
    vi arr(n);
    garr(arr);
    sort(all(arr));
    rep(i, 0, 200)
    {
        if (!binary_search(all(arr), x - i))
        {
            cnl(x - i);
            return;
        }
        if (!binary_search(all(arr), x + i))
        {
            cnl(x + i);
            return;
        }
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    solve();
}

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

int main(void){
	double a,b,c,d,e,f;
	//int X[2][2]={ {c,b}, {f,e} };
	//int Y[2][2]={ {a,c}, {d,f} };
	double x,y;
	double A,X,Y;
	while(cin>>a>>b>>c>>d>>e>>f){
		A=a*e-b*d;
		X=c*e-b*f;
		Y=a*f-c*d;
		x=(1/A)*X;
		y=(1/A)*Y;
		if(x==-0)
			x=0;
		if(y==-0)
			y=0;

		cout << fixed << setprecision(3) << x << ' ' << y << endl;
	}
	
	return 0;
}

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

#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 ms(a, x) memset(a, x, sizeof(a))
#define F first
#define S second
#define endl '\n'
#define all(x) (x).begin(),(x).end()

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());
template<typename... Args>
void write(Args... args) { ((cout << args << " "), ...); cout<<endl;}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    const double pi=3.1415927;
    int x;
    cin>>x;
    cout<<2*pi*x;
    return 0;
}



Measured memory_bytes: 3800
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <utility>
#include <algorithm>
#include <cstdio>
#include <iomanip>
#include <queue>
#include <deque>
#include <stack>
#include <fstream>
#include <cmath>
#include <random>
#include <complex>
#include <functional>

#define ll int64_t
#define Rep(i, n) for (ll i = 0; i < n; i++)
using namespace std;
typedef vector<ll> vec;
typedef vector<vec> mat;

const ll inf = 1LL << 60;

template<class T> inline void chmin(T& a, T b) {
    if (a > b) {
        a = b;
    }
}
template<class T> inline void chmax(T& a, T b) {
    if (a < b) {
        a = b;
    }
}

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

    set<ll> a;
    Rep (i, 3) {
        ll n;
        cin >> n;
        a.insert(n);
    }

    if (a.size() == 2) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
}

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

#define ALL(v) v.begin(), v.end()
#define V vector
#define P pair
using ll = long long;
using ld = long double;
const int MOD = 1e9+7;


int main() {
    int n, m; cin >> n >> m;
    V<int> sum(n, 1);
    V<bool> red(n, false);

    red[0] = true;
    for(int i = 0; i < m; i++){
        int x, y; cin >> x >> y;
        x--, y--;
        if(red[x]) red[y] = true;
        sum[x]--;
        sum[y]++;
        if(sum[x] == 0) red[x] = false;
    }

    int ans = 0;
    for(int i = 0; i < n; i++) if(red[i]) ans++;
    cout << ans << endl;

    return 0;
}


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

//ループマクロ
#define FOR(i , a , b)  for(int i = (a) ; i < (b) ; i++)
#define REP(i , n)      for(int i = 0 ; i < n ; i++)
#define REPR(i , n)     for(int i = n ; 0 <= i ; i--)
#define ROP(i, n)       for(int i = 1 ; i <= n ; i++)

//入出力
#define SCOUT(x) cout << (x) << " "
#define VECCIN(x) for(auto& ele : (x) ) cin >> ele
#define VECOUT(x) for(auto& ele : (x) ) cout << ele << " "; cout << endl;

//その他
#define ALL(obj) (obj).begin() , (obj).end() 
#define SORT(obj) sort(ALL(obj))
#define GSORT(obj) sort(ALL(obj) , greater<int>())
#define P pair<int , int>
#define V vector<int>
#define VLL vector<long long>
#define M map<int, int>
#define S set<int>
#define PQ priority_queue<int>
#define PQG priority_queue<int , V , greater<int>>

#define MAX_H 1000
#define MAX_W 1000
int main(void) {

	ios::sync_with_stdio(false);	cin.tie(0);
    int H, W, A, B;  cin >> H >> W >> A >> B;

    int field[MAX_H][MAX_W];
    for(int i = 0 ; i < MAX_H ; i++)
      for(int j = 0 ; j < MAX_W ; j++)  field[i][j] = 0;

    for(int i = 0 ; i < H ; i++){
		for(int j = 0 ; j < W ; j++){
          if(i < B && j < A) 			field[i][j] = 1;
          else if(B <= i && A <= j) 	field[i][j] = 1;
          else                          field[i][j] = 0;
        }
    }


    for(int i = 0 ; i < H ; i++){
      for(int j = 0 ; j < W ; j++)  cout << field[i][j];
      cout << endl;
    }

              
	return 0;
}

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

int ss(int a[],int n){
	for(int i = 1;i < n;i++){
		if(a[i] <= a[i - 1]) return 0;
	}
	return 1;
}

int main()
{	
	int n;
	cin >> n;
	int a[n];
	for(int i = 0;i < n;i++) cin >> a[i];
	
	for(int i = 0;i < n;i++){
		for(int j = i;j < n;j++){
			swap(a[i],a[j]);
			if(ss(a,n)){
				cout << "YES" << endl;
				return 0;
			}
			swap(a[i],a[j]);
		}
	}
	cout << "NO" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <limits.h>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <string>
using namespace std;
#define ll long long
int main()
{
    ll n , m;
    cin>>n>>m;
    if(n == 1 && m == 1){
        cout<<"1"<<endl;
        return 0;
    }
    if(n == 2 || m == 2){
        cout<<"0"<<endl;
        return 0;
    }
    if(n == 1){
        cout<<m - 2<<endl;
        return 0;
    }
    if(m == 1){
        cout<<n-2<<endl;
        return 0;
    }
    cout<<1ll*(n-2)*(m-2)<<endl;
    return 0;
}


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

using namespace std;


int main()
{
	long long W,H,x,y;

	cin >> W >> H >> x >> y;	

	double A;

	A = (double)(W * H / 2.0);

	int ans = 0;

	if (x*2 == W && y * 2 == H){
		ans = 1;
	}

	printf("%9f %d",A,ans);

	return 0;
}



Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pli = pair<ll, int>;
using pil = pair<int, ll>;
using uint = unsigned int;
template <typename T>
using Graph = vector<vector<T>>;
const int MOD = 1e9 + 7;
const ld PI = acosl(-1);

struct COM {
    vector<ll> inv, fac, finv;
    COM(int N) : inv(N), fac(N), finv(N) {
        inv[1] = 1;
        fac[0] = fac[1] = 1;
        finv[0] = finv[1] = 1;
        for (int i = 2; i < N; ++i) {
            inv[i] = MOD - (MOD / i) * inv[MOD % i] % MOD;
            fac[i] = fac[i - 1] * i % MOD;
            finv[i] = finv[i - 1] * inv[i] % MOD;
        }
    }

    ll calc(int a, int b) {
        return (fac[a] * finv[b] % MOD) * finv[a - b] % MOD;
    }
};

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

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

    ll ans = 0;
    auto func = [&]() -> ll {
        ll res = 0;
        for (int i = 1; i < M; ++i)
            (res += (ll)i * (M - i)) %= MOD;
        (res *= (ll)N * N) %= MOD;
        return res;
    };

    ans += func();
    swap(N, M);
    ans += func();

    COM com(N * M);
    (ans *= com.calc(N * M - 2, K - 2)) %= MOD;

    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 7924
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using P = pair<ll,ll>;
using um = unordered_map<ll,ll>;
#define fl cout<<flush;
#define endl '\n'
template <typename T> inline void prt(T v){cout<<v<<'\n';}
template <typename T> inline bool chmax(T &a, const T &b){if (a<b){a=b;return 1;}return 0;}
template <typename T> inline bool chmin(T &a, const T &b){if (a>b){a=b;return 1;}return 0;}
const ll INF=1LL<<60;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ld pi=3.14159265358979323846;
const ld eps=1e-10;
#define debug(v) cout<<#v<<": ",prt(v);
template <typename A,typename B>
inline void prt(pair<A,B> p){cout<<"("<<p.first<<", "<<p.second<<")\n";}
template <typename A,typename B,typename C>
inline void prt(tuple<A,B,C> p){cout<<"("<<get<0>(p)<<", "<<get<1>(p)<<", "<<get<2>(p)<<")\n";}
inline void prt(bool p){if(p)cout<<"True"<<'\n';else cout<<"False"<<'\n';}
template <typename T> 
inline void prt(vector<T> v){cout<<'{';for(ll i=0;i<v.size();i++){cout<<v[i];if(i<v.size()-1)cout<<", ";}cout<<'}'<<'\n';}
template <typename T> 
inline void prt(deque<T> v){cout<<'{';for(ll i=0;i<v.size();i++){cout<<v[i];if(i<v.size()-1)cout<<", ";}cout<<'}'<<'\n';}
template <typename A,typename B>
inline void prt(map<A,B> v){cout<<'{';ll c=0;for(auto &p: v){cout<<p.first<<":"<<p.second;c++;if(c!=v.size())cout<<", ";}cout<<'}'<<'\n';}
template <typename A,typename B>
inline void prt(unordered_map<A,B> v){cout<<'{';ll c=0;for(auto &p: v){cout<<p.first<<":"<<p.second;c++;if(c!=v.size())cout<<", ";}cout<<'}'<<'\n';}
template <typename T> 
inline void prt(set<T> v){cout<<'{';for(auto i=v.begin();i!=v.end();i++){cout<<*i;if(i!=--v.end())cout<<", ";}cout<<'}'<<'\n';}
template <typename T> 
inline void prt(multiset<T> v){cout<<'{';for(auto i=v.begin();i!=v.end();i++){cout<<*i;if(i!=--v.end())cout<<", ";}cout<<'}'<<'\n';}
signed main(void){
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    ll M;
    cin >> M;
    if(M<N){
        prt(0);
        return 0;
    }
    if(N==1){
        prt(M*(M-1)%MOD);return 0;
    }
    //以上はAのきめかた
    //dp[i]はi個を適当にM-N+i個で
    vector<ll> dp(N+1,0);
    dp[1]=(M-N+1)*(M-N+1-1)%MOD;
    dp[2]=(M-N+2)*(M-N+1)%MOD*(M-N+1)%MOD+(M-N+2)*(M-N+1)%MOD*(M-N)%MOD*(M-N)%MOD;
    dp[2]%=MOD;
    for(ll i=3;i<=N;++i){
        dp[i]=(M-N+i)*(M-N+i-1)%MOD*((i-1)*dp[i-2]%MOD+dp[i-1])%MOD;
    }
    prt(dp[N]);




    return 0;
}



Measured memory_bytes: 7056
#include<map>
#include<set>
#include<list>
#include<cmath>
#include<queue>
#include<stack>
#include<cstdio>
#include<string>
#include<vector>
#include<complex>
#include<cstdlib>
#include<cstring>
#include<numeric>
#include<sstream>
#include<iostream>
#include<algorithm>
#include<functional>

#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

typedef    long long          ll;
typedef    unsigned long long ull;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      pii;

const int INF=1<<29;
const double EPS=1e-9;

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

const int MAX_N =10010;
int prime[MAX_N+500];//i番目の素数
bool is_prime[MAX_N+100];//is_prime[i]がtrueならiは素数

//n以下の素数の数を返す
int sieve(int n){
	int p = 0;
	for(int i = 0;i <=n;i++){
		is_prime[i] =true;
	}
	is_prime[0] = false;
	is_prime[1] = false;
	for(int i = 2;i <=n;i++){
		if(is_prime[i]){
			prime[p++] = i;
			for(int j = 2*i;j <=n;j +=i){
				is_prime[j] =false;
			}
		}
	}
	return p;
}
int n;
int main(){
	int kkkk = sieve(10010);
	while(cin>>n){
		if(n==0){
			break;
		}
		int s = 0;
		int t = 0;
		int sum = 2;
		int ans = 0;
		do{
			if(sum > n){
				sum -=prime[s++];
			}
			if(sum <n){
				sum +=prime[++t];
			}
			if(sum ==n){
				ans++;
				sum -=prime[s++];
			}
		}while(prime[t]<=n&&s !=t);
		cout <<ans<<endl;
	}
	return 0;
}

Measured memory_bytes: 1176
use proconio::input;
use proconio::marker::{Chars};
use std::iter::Iterator;
use std::collections::HashSet;

fn main() {
    input! {
    n: i32,
    k: i32,
    }
    let mut ans = 0;
    let mut sunuke = vec![0; n as usize];

    dbg!(&n);
    dbg!(&k);
    dbg!(&sunuke);

    for i in 1..=k {
        input! {
            d: i32,
            a: [i32; d],
            }
        
        dbg!(&d);
        dbg!(&a);
        
        for s in a {
            dbg!(&s);
            sunuke[(s - 1) as usize] =  sunuke[(s - 1) as usize] + 1;
        }
    }

    for v in sunuke {
        if v == 0{
            ans = ans + 1;
        }
    }

     println!("{}", ans);
}


Measured memory_bytes: 2200
import sys
import math
import itertools

n = int(input())
lucas = [
    1,
    3,
    4,
    7,
    11,
    18,
    29,
    47,
    76,
    123,
    199,
    322,
    521,
    843,
    1364,
    2207,
    3571,
    5778,
    9349,
    15127,
    24476,
    39603,
    64079,
    103682,
    167761,
    271443,
    439204,
    710647,
    1149851,
    1860498,
    3010349,
    4870847,
    7881196,
    12752043,
    20633239,
    33385282,
    54018521,
    87403803,
    141422324,
    228826127,
    370248451,
    599074578,
    969323029,
    1568397607,
    2537720636,
    4106118243,
    6643838879,
    10749957122,
    17393796001,
    28143753123,
    45537549124,
    73681302247,
    119218851371,
    192900153618,
    312119004989,
    505019158607,
    817138163596,
    1322157322203,
    2139295485799,
    3461452808002,
    5600748293801,
    9062201101803,
    14662949395604,
    23725150497407,
    38388099893011,
    62113250390418,
    100501350283429,
    162614600673847,
    263115950957276,
    425730551631123,
    688846502588399,
    1114577054219522,
    1803423556807921,
    2918000611027443,
    4721424167835364,
    7639424778862807,
    12360848946698171,
    20000273725560978,
    32361122672259149,
    52361396397820127,
    84722519070079276,
    137083915467899403,
    221806434537978679,
    358890350005878082,
    580696784543856761,
    939587134549734843,
]
print(lucas[n-1])


Measured memory_bytes: 38384
#include<iostream>
#include<math.h>
#include<vector>
#include<algorithm>
#include<numeric>
#include<map>
using namespace std;

int main(){
    int X,Y,Z,K;
    cin>>X>>Y>>Z>>K;
    long long A[X],B[Y],C[Z];
    vector <long long>D(X*Y),E(K*Z);
    for(int i=0;i<X;++i)cin>>A[i];
    for(int i=0;i<Y;++i)cin>>B[i];
    for(int i=0;i<Z;++i)cin>>C[i];

    for(int i=0;i<X;++i){
        for(int j=0;j<Y;++j)
            D.push_back(A[i]+B[j]);
    }
    sort(D.begin(),D.end(),greater<long long>());
    sort(C,C+Z,greater<long long>());

    for(int i=0;i<K;++i){
        for(int j=0;j<Z;++j)
            E.push_back(D[i]+C[j]);
    }
    sort(E.begin(),E.end(),greater<long long>());

    for(int i=0;i<K;++i)
        cout<<E[i]<<endl;
    
    return 0;
}

Measured memory_bytes: 64760