akhauriyash/Code-Regression huggingface dataset:
from sys import stdin
import math
from operator import itemgetter
from bisect import bisect_left, bisect_right
readline = stdin.readline

def main():
    xy = [tuple(map(int, readline().split())) + (i,) for i in range(int(readline()))]
    xy.sort()
    root = int(math.sqrt(len(xy)))

    low = [x for x, y, i in xy[::root]]
    high = [x for x, y, i in xy[root - 1::root]] + [float('inf')]

    xy = [sorted(xy[i:i+root], key=itemgetter(1)) for i in range(0,len(xy),root)]
    xy = [([y for x, y, i in xyi], xyi) for xyi in xy]
    for sx, tx, sy, ty in (map(int, readline().split()) for _ in range(int(readline()))):
        ret = []
        for i in range(bisect_left(high, sx), bisect_right(low, tx)):
            k, v = xy[i]
            for i in range(bisect_left(k, sy), bisect_right(k, ty)):
                if sx <= v[i][0] <=tx:
                    ret.append(v[i][2])
        if ret:
            ret.sort()
            print('\n'.join(map(str,ret)))
        print()
main()

Measured memory_bytes: 99692
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
const int inf = 1e9 + 7;
const ll INF = 1e18;
const int mod = 1000000007;
#define abs(x) (x >= 0 ? x : -(x))
#define lb(v, x) (int)(lower_bound(all(v), x) - v.begin())
#define ub(v, x) (int)(upper_bound(all(v), x) - v.begin())
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<typename T> T pow(T a, int b) { return b ? pow(a * a, b / 2) * (b % 2 ? a : 1) : 1; }
ll modpow(ll a, ll b, ll _mod) { return b ? modpow(a * a % _mod, b / 2, _mod) * (b % 2 ? a : 1) % _mod : 1; }
template<class T> ostream& operator << (ostream& os, const vector<T>& vec) { for (auto &vi: vec) os << vi << " "; return os; }
template<class T, class U> ostream& operator << (ostream& os, const pair<T, U>& p) { os << p.F << " " << p.S; return os; }
template<typename T >inline istream& operator >> (istream& is, vector<T>& v) { rep(j, sz(v)) is >> v[j]; return is; }
template<class T> inline void add(T &a, int b) { a += b; if (a >= mod) a -= mod; }


void solve();

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

    int T;
    // cin >> T;
    T = 1;

    while (T--) {
        solve();
    }
}


void solve() {
  int n;
  cin >> n;
  vector<int> a(n);
  cin >> a;
  vector<int> b(n);
  cin >> b;

  ll ans = 0;
  // ai+bj で k bit目が 1 のものが何個あるか
  // その xor
  rep(k, 30) {
    vector<int> a2 = a, b2 = b;
    ll t = (1LL << k);
    // 2^(k+1) までに制限することで, 範囲が狭まる
    // しかも, k bit 目 (ほぼ最高桁) だから, 見るべき範囲が狭い
    rep(i, n) a2[i] %= t * 2;
    rep(i, n) b2[i] %= t * 2;
    sort(all(b2));

    int tmp = 0;
    rep(i, n) {
      int it = lb(b2, t - a2[i]);
      int it2 = lb(b2, 2 * t - a2[i]);
      tmp += it2 - it;

      it = lb(b2, 3 * t - a2[i]);
      it2 = lb(b2, 4 * t - a2[i]);
      tmp += it2 - it;
    }
    
    if (tmp % 2) ans += 1LL << k;
  }
  cout << ans << endl;
}


Measured memory_bytes: 3456
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
typedef vector<ll> VI;
typedef vector<VI> VVI;
const ll MOD = 1000000007;
const ll INF = 2147483647;
const ll LINF = 9223372036854775807;
#define REP(i, n) for (int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()

int main() {
	int s, w; cin >> s >> w;
	if(s<=w)
		cout << "unsafe" << endl;
	else
		cout << "safe" << endl;
	return 0;
}


Measured memory_bytes: 3640
t = int(input())
scale = 64
#scale = 4
double = [2**d for d in range(scale)]
double.reverse()
for _ in range(t):
    n = int(input())
    a = list(map(int,input().split()))
    s = input()
    base = [0 for _ in range(scale)]
    for i in range(n)[::-1]:
        now = a[i]
        for d in range(scale):
            if now & double[d]:
                if base[d]:
                    now ^= base[d]
                else:
                    base[d] = now
                    break
        else:
            continue
        if s[i] == '1':
            print(1)
            break
    else:
        print(0)

Measured memory_bytes: 9180
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, [ $t:tt ]) => {
        {
            let len = read_value!($next, usize);
            (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
        }
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        a: usize,
        b: usize,
    }
    if b % a == 0 {
        println!("{}", a + b);
    } else {
        println!("{}", b - a);
    }
}


Measured memory_bytes: 4352
#include <iostream>
#include <string>

int main()
{
    using namespace std;
    string str;
    string s1, s2;

    cin >> str;
    //cout << str << " " << str.size() << endl;

    // 0 ~ str.size / 2 - 1
    s1 = str.substr(0, (str.size() / 2));
    s2 = str.substr(str.size() / 2 + 1);
    //cout << s1 << endl;
    //cout << s2 << endl;

    if (s1 == s2)
    {
      cout << "Yes";
      return 0;
    } else
    {
      cout << "No";
    }
    return 0;
}


Measured memory_bytes: 256
n = int(input())
x = []
y = []
h = []
for i in range(n):
    temp = [int(_) for _ in input().split(' ')]
    x.append(temp[0])
    y.append(temp[1])
    h.append(temp[2])

for cx in range(101):
    for cy in range(101):
        correctness = True
        for i in range(n):
            if h[i] > 0:
                ch = h[i] + abs(cx - x[i]) + abs(cy - y[i])
        for i in range(n):
            if h[i] != max(ch - abs(cx - x[i]) - abs(cy - y[i]), 0):
                correctness = False
        if correctness:
            print('{0} {1} {2}'.format(cx, cy, ch))


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

typedef long long int ll;
typedef vector<int> vi;			typedef vector<ll> vl;
typedef vector<vi> vvi; 		typedef vector<vl> vvl;
typedef pair<int, int> 	pii;	typedef pair<ll, ll> pll;
typedef vector<pii> vii; 		typedef vector<pll> vll;
typedef map<int,int> mii;
typedef vector<char> vc;
typedef vector<bool> vb;
#define endl '\n'
#define forn(i,n) for(int i=0;i<n;i++)
#define rforn(i,n) for(int i=n-1;i>=0;i--)
#define forne(i,n) for(int i=1;i<=n;i++)
#define rforne(i,n) for(int i=n;i>=1;i--)
#define forse(i,s,e) for(int i=s;i<e;i++)
#define rforse(i,s,e) for(int i=e-1;i>=s;i--)
#define all(x) x.begin(),x.end()
#define sz(x) (ll)x.size()
#define MOD 1000000007
#define F first
#define S second
#define pb push_back
#define pf push_front
#define rb pop_back
#define rf pop_front
#define in insert
#define mp make_pair
#define fill(a,x) memset(a,x,sizeof a);
#define trav(a,x) for(auto &a:x)
#define min3(a, b, c) min(min(a, b), c)
#define min4(a, b, c, d) min(min(a, b), min(c, d))
#define max3(a, b, c) max(max(a, b), c)
#define max4(a, b, c, d) max(max(a, b), max(c, d))
const ll INFL = 1e18;
const int INFI = 1e9;
#ifdef KARAN
	#include "../../trace.h"
#else
    #define trace(args...)
#endif

ll div_floor(const ll &a,const ll &b) { return a / b - (((a ^ b) < 0) and a % b);}
ll div_ceil(const ll &a,const ll &b) { return a / b + (((a ^ b) >= 0) and a % b);}
ll modpow(ll a, ll b, ll m = MOD){a %= m; ll res = 1; 
	while (b) {if (b & 1)res = (res * a) % m; a = (a * a) % m; b >>= 1;} return res;}
ll bpow(ll a, ll b){ll res = 1; while (b) {if (b & 1)res = res * a; a = a * a; b >>= 1;} return res;}
ll modinv(ll a, ll m = MOD) {return modpow(a, m - 2, m);}
void graph(vvi &adj, int m) {int x, y; forn(i, m){cin>>x>>y; adj[--x].pb(--y); adj[y].pb(x);}}

void solve(){
	int n; cin>>n;
	cout<<(1000-(n%1000))%1000<<endl;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	#ifdef KARAN
		freopen("inp.txt", "r", stdin);
    	freopen("out.txt", "w", stdout);
    	freopen("err.txt", "w", stderr);
	#endif
	int t=1;
	while(t--)
		solve();
}

Measured memory_bytes: 3640
fun main() {
    var (a,b,c,d) = readLine()!!.split(" ").map { it.toInt() }
    while (true){
        c -= b
        if (c <= 0){
            println("Yes")
            break
        }
        a -= d
        if (a <= 0){
            println("No")
            break
        }
    }
}

Measured memory_bytes: 36384
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		for(int i = 0; ; i++) {
			if(i * i > N) {
				System.out.println((i - 1)*(i - 1));
				break;
			}
		}
	}
}


Measured memory_bytes: 23764
#include <iostream>
#include <iomanip>
#include <string>
typedef long long ll;
using namespace std;
const  ll INF = 1e9;
const  ll MOD = 1e9 + 7;
#define repi(i,n,init) for(ll i=init;i<(n);i++)

int main()
{
    string s,t,u;
    int a,b;
    cin >> s >> t >> a >> b >> u;
    cout << (s == u? --a : a) << " " << (t == u? --b : b) << endl;
    return 0;
}

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

int main() {

    int a, b, c, d;
    cin >> a >> b >> c >> d;

    if(a+1 == c && d == 1){
        cout << 1 << endl;
    }
    else{
        cout << 0 << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#![allow(unused, non_snake_case, dead_code, non_upper_case_globals)]
#![macro_use]

use std::cmp::*;
use std::collections::*;
use std::io::*;
use std::mem::*;
use std::num::*;
use std::slice::*;

fn main() {
    let (r, w, e) = (stdin(), stdout(), stderr());
    let mut io = IO::new(r.lock(), w.lock(), e.lock());
    // =============================================== //
    let (n, m): (usize, usize) = (io.read(), io.read());
    let mut hm = BinaryHeap::new();
    for _ in 0..n {
        let k: i64 = io.read();
        hm.push(k);
    }
    for _ in 0..m {
        let now = hm.pop().unwrap();
        hm.push(now / 2);
    }
    io.writeln(hm.iter().fold(0, |sm, x| sm + x));
}

// IO
struct IO<R: Read, W: Write, E: Write> {
    Read: R,
    Write: BufWriter<W>,
    Error: BufWriter<E>,
}
impl<R: Read, W: Write, E: Write> IO<R, W, E> {
    fn new(r: R, w: W, e: E) -> IO<R, W, E> {
        IO {
            Read: r,
            Write: BufWriter::new(w),
            Error: BufWriter::new(e),
        }
    }
    fn read<T>(&mut self) -> T
    where
        T: std::str::FromStr,
    {
        let next: String = self
            .Read
            .by_ref()
            .bytes()
            .map(|c| c.unwrap() as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect();
        next.parse().ok().unwrap()
    }
    fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
    fn readn<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read::<T>()).collect::<Vec<_>>()
    }
    fn readmat<T: std::str::FromStr>(&mut self, n: usize, m: usize) -> Vec<Vec<T>> {
        (0..n).map(|_| self.readn(m)).collect()
    }
    fn write<S: ToString>(&mut self, val: S) {
        self.Write.write(val.to_string().as_bytes());
    }
    fn writeln<S: ToString>(&mut self, val: S) {
        self.Write.write(val.to_string().as_bytes());
        self.Write.write(b"\n");
    }
    fn debug<S: std::fmt::Debug>(&mut self, val: S) {
        writeln!(self.Error, "(debug ) {:?}", &val);
    }
    fn debug2<S: std::fmt::Debug, T: std::fmt::Debug>(&mut self, val1: S, val2: T) {
        writeln!(self.Error, "(debug2) {:?} -> {:?}", val1, val2);
    }
}


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

using namespace std;

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

	string s = to_string(num);

	int n = s.length();

	if (s[n - 1] == '3') cout << "bon";
	else if (s[n - 1] == '0' || s[n - 1] == '1' || s[n - 1] == '6' || s[n - 1] == '8') cout << "pon";
	else cout << "hon";
}

Measured memory_bytes: 3696
#include <iostream>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;

int main(){
    long long h;
    long long mul = 1,ans = 0;

    cin >> h;

    while(h){
        if(h==1){
            cout << ans+mul;
            return 0;
        }
        else{
            h = h/2;
            ans+=mul;
            mul*=2;
        }
    }
}


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


#define _USE_MATH_DEFINES_
#define ll long long
#define ld long double
#define Accepted 0
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x.size())
#define every(x) x.begin(),x.end()
#define F first
#define S second
#define For(i,x,y)  for (ll i = x; i <= y; i ++) 
#define FOr(i,x,y)  for (ll i = x; i >= y; i --)
#define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0)
// ROAD to...                                                                                                                                                                                                                Red

using namespace std;

inline bool isvowel (char c) {
	c = tolower(c);
    if (c == 'a' || c == 'e' || c == 'i' || c == 'y' || c == 'o' || c == 'u') return 1;
    return 0;
}

const double eps = 0.000001;
const ld pi = acos(-1);
const int maxn = 1e7 + 9;
const int mod = 1e9 + 7;
const ll MOD = 1e18 + 9;
const ll INF = 1e18 + 123;
const int inf = 2e9 + 11;
const int mxn = 1e6 + 9;
const int N = 1e6 + 123;                                          
const int M = 22;
const int pri = 997;
const int Magic = 2101;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
int n;
int a[N], b[N];

int main () {
	cin >> n;
	For (i, 1, n) cin >> a[i];
	For (i, 1, n) {
		cin >> b[i];
	}
	
	ll r = 0;
	For (i, 1, n) {
		if (a[i] > b[i]) {
			r -= (a[i] - b[i]);
		} else if (b[i] > a[i]) {
			r += (b[i] - a[i]) / 2;
		}
	}
 
	if (r >= 0) puts("Yes");
	else puts("No");	
}

Measured memory_bytes: 2304
while True:
    a, op, b = input().split()
    a,b = int(a), int(b)
    op_dict = {'+': (lambda x,y: x + y),
               '-': (lambda x,y: x - y),
               '*': (lambda x,y: x * y),
               '/': (lambda x,y: x // y),
               '?': '?'}
    func = op_dict[op]
    if func == '?': break 
    print('%d' % int(func(a, b)))

Measured memory_bytes: 7728
from sys import stdin
from sys import setrecursionlimit
from functools import cmp_to_key
from collections import Counter, deque, defaultdict
from math import floor, ceil
from bisect import bisect_left
from itertools import combinations
setrecursionlimit(100000)

INF = int(1e10)
MOD = int(1e9 + 7)
MAX_N = 200000 + 5

def main():
    from builtins import int, map
    N = int(input())
    A, B = [], []
    for i in range(N):
        ai, bi = map(int, input().split())
        A.append(ai)
        B.append(bi)
    A.sort()
    B.sort()
    ans = 0

    if N % 2 == 1:
        l = A[N // 2]
        r = B[N // 2]
        ans = r - l + 1
    else:
        l = A[N // 2 - 1] + A[N // 2]
        r = B[N // 2 - 1] + B[N // 2]
        ans = r - l + 1
    print(ans)


if __name__ == '__main__':
    main()

Measured memory_bytes: 100756
#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)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll)1e15;

string W[105];

int main()
{
    int N;
    cin >> N;
    REP(i, N)
    {
        cin >> W[i];
    }

    string ans = "Yes";
    REP(i, N)
    {
        FOR(j, N, i + 1)
        {
            if (W[i] != W[j])
                continue;
            ans = "No";
            break;
        }
    }

    FOR(i, N, 1)
    {
        if (W[i][0] != W[i - 1][W[i - 1].length() - 1])
        {
            ans = "No";
            break;
        }
    }
    cout << ans << endl;
    return 0;
}

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

#define ll long long
#define ld long double
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define PI 3.14159265358979323846
#define sz(x) ((int)(x).size())

const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LINF = 1e18;

vector<int> e;

void prime_factor(int num)
{
    for (int i = 2; i*i <= num; i++)
    {
        while(num%i==0)
        {
            e[i]++;
            num/=i;
        }
    }
    if(num!=1)e[num]++;
}

int kosu(int num)
{
    int ret=0;
    num--;
    for(auto& u: e)
    {
        if(u>=num) ret++;
    }
    return ret;
}

int main()
{
    int n;
    cin >> n;
    e.resize(n+1,0);
    for (int i = 2; i < n+1; i++)
    {
        prime_factor(i);
    }
    //for(auto u: e) cout << u << " ";
    //cout << endl;
    int ans = 0;
    ans += kosu(75) + (kosu(15)*(kosu(5)-1)) + (kosu(25)*(kosu(3)-1)) + (kosu(5)*(kosu(5)-1)*(kosu(3)-2)/2);
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
#define int         long long
#define uint        unsigned int
#define ld          long double
#define showoff     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb          push_back
#define pii         pair<int,int>
#define FOR(i,a,b)  for(int i=a;i<b;++i)
#define RFOR(i,a,b) for(int i=a;i>b;--i)
#define f           first
#define se          second
#define maxn        200005
#define all(v)      v.begin(),v.end()
#define sz(x)       (int)x.size()
#define mod         1000000007
#define pqueue      priority_queue<int>
#define pdqueue     priority_queue< int,vector<int> ,greater< int >>
 
using namespace std;
 
 
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
 
int power(int a,int n)
{
    a %= mod;
    if(n == 1)return a;
    if(n == 0)return 1;
    if(n%2)return (a*(power((a*a)%mod,n/2)%mod))%mod;
    return power((a*a)%mod,n/2)%mod;
}
const int inf = (int) 1e18;
 
int inverse(int x){
    return power(x,mod-2)%mod;//little fermat....
}


signed main()
{
    showoff;
    int n,ans = 0;
    cin >> n;
    string s;
    cin >> s;
    FOR(i,0,n){
        ++ans;
        while(i+1 < sz(s) && s[i] == s[i+1])++i;
    }
    cout << ans;
    return 0;

}
//*->for large size of matrix take int not long long if possible......
//*->always take maximum as inf for safer side ....s

Measured memory_bytes: 512
#!/usr/bin/env python3
import sys
# import math
# import numpy as np
# from functools import lru_cache

args = sys.argv
if len(args) == 2:
  from IPython import embed
  em = True
else:
  em = False

# sys.setrecursionlimit(10000)

#### input
N = int(input())
# a, b = map(int, input().split())
# a = list(map(int, input().split()))
# a = list(map(lambda x: int(x)*(-1), a))  # 各要素を-1倍


# n = int(input())
# t = [int(input()) for i in range(n)]
if em: sys.stdin = open('/dev/tty')

#### function
# @lru_cache(maxsize=10000)

#### process

if N % 2 == 0:
  tmp = int(N/2)
  print(int(tmp*(N-1)))
else:
  tmp = int((N-1)/2)
  print(int(tmp*N))

# I = [i for i in range(1, N+1)]
# P = [i for i in range(2, N+1)]
# P.append(1)

# rems = [I[i] % P[i] for i in range(0, len(I))]
# print(sum(rems))

# if em: embed()

## heapsort, O(NlogN)
# import heapq
# heapq.heapify(A)
# min = heapq.heappop(A)
# heapq.heappush(A, new_element)


Measured memory_bytes: 3060
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		
		char[] s = stdIn.next().toCharArray();
		
		if(s[0]==s[1] || s[1] == s[2] || s[2]==s[3]) {
			System.out.println("Bad");
		}else {
			System.out.println("Good");
		}
		
		
	}

}


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

N = int(input())
A = [None] + [int(x) for x in input().split()]

answer = []
choose = [0] * (N+1)

for n in range(N,0,-1):
    x = sum(choose[2*n::n])
    if x % 2 == A[n]:
        continue
    choose[n] += 1
    answer.append(str(n))

print(len(answer))
print(' '.join(answer))



Measured memory_bytes: 17184
/* ex 7_1
   kohei0713 */

#include <stdio.h>

typedef struct point
{
    int x_elem;
    int y_elem;
}point;

//座標を回転させる関数
point shift_point(point point_1, point point_0){

    point new_point;

    //新しい座標
    new_point.x_elem = point_1.y_elem - point_0.y_elem + point_0.x_elem;
    new_point.y_elem = -point_1.x_elem + point_0.x_elem + point_0.y_elem;

    return new_point;
}

int main(void){

    point point_1, point_2, point_3, point_4;

    //input
    scanf("%d %d %d %d", &point_1.x_elem, &point_1.y_elem, &point_2.x_elem, &point_2.y_elem);

    //座標の回転
    point_3 = shift_point(point_1, point_2);
    point_4 = shift_point(point_2, point_3);

    //答えを出力する
    printf("%d %d %d %d\n", point_3.x_elem, point_3.y_elem, point_4.x_elem, point_4.y_elem);

    return 0;
}

Measured memory_bytes: 1704
#include <iostream>
#include <string>
#include <vector>
#include <fstream>
#include <algorithm>
#include <math.h>
#include <map>
#include <set>
using namespace std;
typedef long long ll;

ll lcm(ll a,ll b){
    return a/__gcd(a,b)*b;
}

int main(){
int n;cin>>n;ll ans=1;
for(int i=0;i<n;i++){
    ll a;cin>>a;
    ans=lcm(ans,a);
}
cout<<ans;
}

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

using namespace std;

#define rep(i , n) for(int i=0 ; i<n ; i++)
#define rep1(i , n) for(int i=1 ; i<=n ; i++)

typedef long long int ll;


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

	int arr[101],n;
	cin >> n;
	rep(i , n)
		cin >> arr[i];


	int diff = 0;
	rep(i , n-1)
	{
	    for(int j=i+1 ; j<n ; j++)
		    diff = max(diff , abs(arr[i]-arr[j]));
	}
	cout << diff;
	return 0;
}

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

int main(){
	int A,B,x;
  cin >> A >> B;
  for(int i=A;i<B+1;i++){
  	 if((i/1000 == i%100*10 && i%100 < 10)||
        i/10000+i/1000%10*10 == i%100) x++;
     }
  	  cout << x;
}

Measured memory_bytes: 256
n, k = map(int, input().split())
a = list(map(int, input().split()))
if min(a) <= 0:
    print(-1)
    exit()
s = sorted(enumerate(a), key = lambda x: x[1], reverse = True)
def check(s, k, ans, exc):
    news = []
    if k < 0:
        return ans
    for i in range(n):
        if s[i][0] == exc:
            news.append(s[i])
        else:
            if s[i][1] <= 0:
                print(-1)
                exit()
            news.append((s[i][0], s[i][1] - 1))
            ans.append(s[i][0] + 1)
    news.sort(key = lambda x: x[1], reverse = True)
    if exc == news[n-1][0]:
        exc = news[n-2][0]
    else:
        exc = news[n-1][0]
    return check(news, k-1, ans, exc)
ans = check(s, k, [], n + 1)
print(n + (n-1) * k)
for ansint in ans:
    print(ansint, end = ' ')
print()


Measured memory_bytes: 3700
#include <cmath>
#include<iostream>
#include <functional>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <iomanip>
using namespace std;
 
int main(){    
  int N;
  cin >> N;
  string S,T;
  cin >> S >>T;
  
  for(int i=0;i<N;i++){
    cout <<S[i]<<T[i];  
  }
  
}


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

enum{
    TOP, FRONT, RIGHT, LEFT, REAR, BOTTOM
};

class Dice{
private:
    std::vector<int> faces;

public:
    Dice(){
        for(int i = 0; i < 6; ++i){
            faces.push_back(i);
        }
    }

    Dice(std::vector<int> readVec){
        int sz = readVec.size();
        for(int i = 0; i < sz; ++i){
            faces.push_back(readVec.at(i));
        }
    }

    void roll(int readVal){
        std::vector<int> index{0, 2, 5, 3};
        switch(readVal){
            case 78: // 'N'
                index.at(1) = 1; index.at(3) = 4; 
                break;
            case 87: // 'W'
                index.at(1) = 2; index.at(3) = 3; 
                break;
            case 69: // 'E'
                index.at(1) = 3; index.at(3) = 2; 
                break;
            case 83: // 'S'
                index.at(1) = 4; index.at(3) = 1; 
                break;
            case 82: // 'R' (rotate the dice clockwisely)
                index.at(0) = 1; index.at(2) = 4; 
                break;
        }

        for(int i = 0; i < 3; ++i){
            std::swap(faces.at(index.at(i)), faces.at(index.at(i + 1)));
        }
    }

    void show(int i){
        std::cout << faces.at(i) << std::endl;
    }
};

int main(){
    std::vector<int> vec(6);
    for(int i = 0; i < 6; ++i){
        std::cin >> vec.at(i);
    }

    Dice dice(vec);

    std::string cmd;
    std::cin >> cmd;

    int sz = cmd.size();
    for(int i = 0; i < sz; ++i){
        dice.roll(cmd.at(i));
    }

    dice.show(TOP); // TOP, FRONT, RIGHT, LEFT, REAR, or BOTTOM

    return 0;
}



Measured memory_bytes: 3212
//ヘッダー
#include<bits/stdc++.h>
using namespace std;

//型定義
typedef long long ll;

//定数
const int INF=1e+9;
const int MOD=1e+9+7;

//REPマクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define REP2(i,a,b) for(ll i=a;i<(ll)(b);i++)
#define REPD2(i,a,b) for(ll i=a;i>(ll)(b);i--)

//vectorの扱い
#define ALL(x) (x).begin(),(x).end() //sortなどの引数省略
#define SIZE(x) ((ll)(x).size()) //size
#define MAX(x) *max_element(ALL(x)) //最大値
#define MIN(x) *min_element(ALL(x)) //最小値

int main(){
    int N,K;
    cin >> N >> K;
    string S;
    cin >> S;
    int ans=0;
    REP(i,N){
        if(i>=1&&S[i]=='L'&&S[i-1]=='L'){
            ans++;
        }else if(i<N-1&&S[i]=='R'&&S[i+1]=='R'){
            ans++;
        }
    }
    cout<<min(ans+2*K,N-1)<<endl;
    

   
}

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

#define debug(x) cerr << #x << ": " << x << endl
#define debugArray(x, n)                                                       \
    for(long long hoge = 0; (hoge) < (n); ++(hoge))                            \
    cerr << #x << "[" << hoge << "]: " << x[hoge] << endl
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> vll;
const ll INF = LLONG_MAX / 2;
const ll MOD = 1e9 + 7;

ll H, W, K;

ll fib[10] = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55};
ll dp[110][10];
ll dfs(ll i, ll j) {
    if(i == 0)
        return j == K;
    if(dp[i][j] > 0) {
        return dp[i][j];
    }
    ll ret = 0;
    ret = (ret + dfs(i - 1, j) * fib[W - j] % MOD * fib[j - 1] % MOD) % MOD;
    if(j > 1)
        ret = (ret + dfs(i - 1, j - 1) * fib[W - j] % MOD * fib[j - 2] % MOD)
              % MOD;
    if(j < W)
        ret =
            (ret + dfs(i - 1, j + 1) * fib[W - j - 1] % MOD * fib[j - 1] % MOD)
            % MOD;
    return dp[i][j] = ret;
}

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> H >> W >> K;
    cout << dfs(H, 1) << endl;
    return 0;
}


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

int main(void){
  int A,B,C;
  int max;
  
  cin >> A >> B >> C;
  
  if(C>A+B+1){
    max=B+A+B+1;
  }else if(C<=A+B+1){
    max=B+C;
  }
  
  cout << max << endl;
  
  return 0;
}

Measured memory_bytes: 256
import itertools

N = int(input())

P = tuple(map(int, input().split()))
Q = tuple(map(int, input().split()))
d = {}

pattern = itertools.permutations(range(1,N+1),  N)
i = 1
for p in pattern:
    d[p] = i
    i += 1

print(abs(d[P]-d[Q]))




Measured memory_bytes: 42864
#include <iostream>
#include <string>
#include <cmath>
#include <vector>
#include <algorithm>
#include <functional>
#include <cstdio>
#include <iomanip>

using namespace std;
// for loop
#define F(i, L, R) for(int i = L; i < R; i++)
#define FE(i, L, R) for(int i = L; i <= R; i++)
// for (reversed)
#define FR(i, L, R) for(int i = L; i > R; i--)
#define FRE(i, L, R) for(int i = L; i >= R; i--)

// data types
#define ul unsigned long
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define us unsigned shoft

// vectors
typedef vector<int> vi;
typedef vector<long> vl;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
#define ALL(c) (c).begin(),(c).end()
#define last(vec) vec.size()-1
#define lastEle(vec) vec[last(vec)]

// debug
#define DBG(vari) cerr<<#vari<<" = "<<(vari)<<endl;
#define printA(a, L, R) FE(i, L, R) cout << a[i] << (i==R?'\n':' ')
#define printAF(a, L) printA(a, 0, L-1)
#define printV(a) printA(a, 0, a.size()-1)

// utils
#define char2int(c) (c-'0')
#define bit(x, i) (x&(1<<i))
#define space ' '
#define PI 3.14159265358979323

int main() {
    long n;
    vl data(10000);
    cin >> n;
    long first;
    cin >> first;

    long max = first;
    long min = first;
    long sum = first;
    F(i, 1, n){
        cin >> data[i];
        sum += data[i];
        if(max < data[i]){
            max = data[i];
        }else if(min > data[i]){
            min = data[i];
        }
    }

    cout << min << space << max << space << sum << endl;
        
    return 0;
}


Measured memory_bytes: 3176
//
// Created by Tzyark on 2018/9/19.
//
#include <iostream>
#include <set>
using namespace std;
int main() {
    set<int> s;
    s.clear();
    int a, b, c;
    cin >> a >> b >> c;
    s.insert(a), s.insert(b), s.insert(c);
    cout << s.size() << endl;
    return 0;
}


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

const ll MOD = 1000000007;

ll modInv(ll a, ll m){
    ll b = m, u = 1, v = 0;
    while(b){
        ll t = a / b;
        a -= t * b; swap(a,b);
        u -= t * v; swap(u,v);
    }
    u %= m;
    if(u < 0) u += m;
    return u;
}

ll nCrModFermat(ll n, ll r, ll mod){
    if(r == 0) return 1;

    ll fac[n + 1];
    fac[0] = 1;
    for(ll i = 1; i <= n; i++){
        fac[i] = fac[i - 1] * i % mod;
    }
    return (fac[n] * modInv(fac[r],mod) % mod * modInv(fac[n - r], mod) % mod) % mod;
}


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

    ll n,k;
    cin >> n >> k;

    ll c = n - k + 1;
    for(ll i = 1; i <= k; i++){
        if(n - k + 1 >= i) cout << nCrModFermat(c , i, MOD) * nCrModFermat(k - 1, i - 1, MOD) % MOD << endl;
        else {
            cout << 0 << endl;
        }
    }
}



Measured memory_bytes: 256
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <climits>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
#include <random>
#include <complex>
#include <regex>

using namespace std;

#define SHOW_VECTOR(v) {std::cerr << #v << "\t:";for(const auto& xxx : v){std::cerr << xxx << " ";}std::cerr << "\n";}
#define SHOW_MAP(v){std::cerr << #v << endl; for(const auto& xxx: v){std::cerr << xxx.first << " " << xxx.second << "\n";}}

constexpr long long MOD = 1000000007;

vector<pair<long, long>> factorization(long long N) {
    vector<pair<long, long>> P;
    for (long long i = 2; i * i <= N; i++) {
        if (N % i == 0) {
            long long count = 0;
            while (N % i == 0) count++, N /= i;
            P.push_back(make_pair(i, count));
        }
    }
    if (N != 1) P.push_back(make_pair(N, 1));
    return P;
}

long long pow_mod(long long N, long long p, long long M) {
    long long res = 1;
    while (p > 0) {
        if (p & 1) res = (res * N) % M;
        N = (N * N) % M;
        p >>= 1;
    }
    return res;
}

long long ncm_mod(long long N, long long R, long long M) {
    long long numerator = 1;
    long long dominator = 1;
    if (N / 2 < R) R = N - R;
    for (long long i = 0; i < R; i++) {
        numerator = (numerator * (N - i)) % M;
        dominator = (dominator * (R - i)) % M;
    }
    return (numerator * pow_mod(dominator, M - 2, M)) % M;
}

int main() {

    long long N, M;
    cin >> N >> M;

    auto fact = factorization(M);
    long long ans = 1;
    for (int i = 0; i < fact.size(); i++) {
        long long d = fact[i].second;
        d = ncm_mod(d + (N - 1), (N - 1), MOD);
        ans = (ans * d) % MOD;
    }

    cout << ans << endl;

    return 0;
}











































































Measured memory_bytes: 256
package main

import (
	"fmt"
	"math"
)

func main() {
	var S string
	fmt.Scan(&S)

	num := make([]int, len(S))
	for i, r := range S {
		num[i] = int(r - '0')
	}

	arr := make([]int, 0, (1 << uint(len(S))))
	for bit := 0; bit < (1 << uint(len(S)-1)); bit++ {
		s := 0
		for i := 0; i < len(S); i++ {
			if bit&(1<<uint(i)) == (1 << uint(i)) {
				p := pow(num[s : i+1])
				arr = append(arr, p)
				s = i + 1
			}
		}
		arr = append(arr, pow(num[s:len(num)]))
	}

	sum := 0
	for i := range arr {
		sum += arr[i]
	}
	fmt.Println(sum)

}

func pow(data []int) int {
	if len(data) == 1 {
		return data[0]
	}

	sum := 0
	for i := 0; i < len(data); i++ {
		sum += data[i] * int(math.Pow10(len(data)-i-1))
	}
	return sum
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define NIL -1
#define MAX 1000

int main()
{
    int n;
    cin >> n;
    
    int h[n], c[n];
    rep(i, n) cin >> h[i];

    c[0] = 0;
    c[1] = abs(h[1] - h[0]);
    for(int i = 2; i < n; ++i){
        c[i] = min(c[i-2] + abs(h[i] - h[i-2]), c[i-1] + abs(h[i] - h[i-1]));
    }

    cout << c[n-1] << endl;

    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
	string s;
	cin >> s;
	ll a = 0;
	for (char c : s) a += c - '0';
	if (a % 9 == 0) printf("Yes\n");
	else printf("No\n");
}

Measured memory_bytes: 3676
#n=int(input())
ans=10**6
n,k=map(int,input().split())
p=[int(i) for i in input().split()]
s=[]
for i in range(10):
    if i not in p:
        s.append(str(i))
        
for a in s+['0']:
    for b in s:
        for c in s:
            for d in s:
                for e in s:
                    x=map(int,[a+b+c+d+e,b+c+d+e,c+d+e,d+e,e])
                    for i in x:
                        if i>=n:
                            ans=min(i,ans)
print(ans)


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

int main() {
  int n; cin >> n;
  int a[n];
  int one_cnt = 0;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    if (a[i] == 1) ++one_cnt;
  }
  
  int start = 1;
  int break_num = 0;
  for (int i = 0; i < n; ++i) {
    if (a[i] == start) ++start;
    else ++break_num;
  }
  
  if (one_cnt < 1) cout << -1 << endl;
  else cout << break_num << endl;
  
  return 0;
}

Measured memory_bytes: 4416
#include <stdio.h>
#include <iostream>

using namespace std;

#define REP(a, i, n) for (int i = a; i < n; ++i)

int min(int X, int Y) {
    return X < Y ? X : Y;
}

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

    int ans = 1001;
    REP(0, i, N) {
        int c, t; cin >> c >> t;
        if (t <= T) {
            ans = min(ans, c);
        }
    }

    if (ans > 1000) {
        cout << "TLE" << endl;
    } else {
        cout << ans << endl;
    }

    return 0;
}


Measured memory_bytes: 256
from collections import deque
s = list(input())
n = len(s)
d = deque(s)
d1 = deque(s[: (n-1)//2])
d2 = deque(s[(n+1)//2 :])
while len(d) > 1:
  if d.pop() != d.popleft():
    print('No')
    exit()
while len(d1) > 1:
  if d1.pop() != d1.popleft() or d2.pop() != d2.popleft():
    print('No')
    exit()
print('Yes')

Measured memory_bytes: 3316
#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<cstdlib>
#include<string>
#include<algorithm>
#include<climits>
#include<map>
#include<queue>
#include<iomanip>

using namespace std;

int main(){

	int N;
	string S;

	cin >> N >> S;

	int ans = INT_MIN;
    int count;

	for(int i = 0;i < N;i++){
		string left;
		string right;
		left  = S.substr(0,i+1);
		right = S.substr(i+1,N-i);
		count = 0;
		vector<string> vec;
	    for(int j = 0;j < left.size();j++){
	    	string target = left.substr(j,1);
	        auto itr = find(vec.begin(),vec.end(),target);
	        if(itr != vec.end()){
	        	continue;
	        }
	    	if(right.find(target) != string::npos){
	    		count++;
	    	}
	    	vec.push_back(target);
	    }
	    ans = max(count,ans);
	}

	cout << ans << endl;

	return 0;


}


Measured memory_bytes: 256
parseInt(x) = parse(Int, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)

function main()
	n = readline() |> parseInt
	a = zeros(Int,n)
	for i in 1:n
		a[i] = readline() |> parseInt
	end
	now = 2
	total = a[1]-1
	for i in 2:n
		if a[i]>now
			if a[i]%now==0
				total += div(a[i],now)-1
			else
				total += div(a[i],now)
			end
		elseif a[i] == now
			now += 1
		end
	end
	println(total)
end

main()

Measured memory_bytes: 123816
#include <iostream>
#include <fstream>
#include <cmath>  
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <numeric>
#include <functional>
#include <string> 
#include <vector>
#include <bitset>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>

using namespace std;
using ll = long long;

#define REP(i,n) for(long long i = 0; i < (n); i++)
#define FOR(i, m, n) for(long long i = (m);i < (n); ++i)
#define ALL(obj) (obj).begin(),(obj).end()

template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;

const ll MOD = (ll)1e9 + 7;
const ll HINF = (ll)1e18;
const ll LINF = (ll)1e9;
const long double PI = 3.1415926535897932384626433;

template <class T> void corner(bool flg, T hoge) { if (flg) { cout << hoge << endl; exit(0); } }
template <class T, class U>ostream &operator<<(ostream &o, const map<T, U>&obj) { o << "{"; for (auto &x : obj) o << " {" << x.first << " : " << x.second << "}" << ","; o << " }"; return o; }
template <class T>ostream &operator<<(ostream &o, const set<T>&obj) { o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o; }
template <class T>ostream &operator<<(ostream &o, const vector<T>&obj) { o << "{"; for (int i = 0; i < (int)obj.size(); ++i)o << (i > 0 ? ", " : "") << obj[i]; o << "}"; return o; }
template <class T, class U>ostream &operator<<(ostream &o, const pair<T, U>&obj) { o << "{" << obj.first << ", " << obj.second << "}"; return o; }
template <template <class tmp>  class T, class U> ostream &operator<<(ostream &o, const T<U> &obj) { o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr)o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o; }
void print(void) { cout << endl; }
template <class Head> void print(Head&& head) { cout << head; print(); }
template <class Head, class... Tail> void print(Head&& head, Tail&&... tail) { cout << head << " "; print(forward<Tail>(tail)...); }
void YN(bool flg) { cout << ((flg) ? "YES" : "NO") << endl; }
void Yn(bool flg) { cout << ((flg) ? "Yes" : "No") << endl; }
void yn(bool flg) { cout << ((flg) ? "yes" : "no") << endl; }

int main() {
	ll N, W; cin >> N >> W;
	V<ll> w(N + 1,0), v(N + 1,0);
	FOR(i,1,N+1) cin >> w[i] >> v[i];
	V<V<ll>> dp(N + 1, V<ll>(W + 1, 0));

	FOR(i,1,N+1){
		FOR(j,0,W+1){
			dp[i][j] = max(dp[i][j], dp[i - 1][j]);
			if (j + w[i] > W) continue;
			dp[i][j + w[i]] = max(dp[i][j + w[i]], dp[i - 1][j] + v[i]);
		}
	}
	//FOR(i,0,N+1) print(i,dp[i]);
	cout << *max_element(ALL(dp[N])) << endl;

	return 0;
}


Measured memory_bytes: 81012
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

const int mod = 1e9+7;
const int N = 5005;

int dp[N][N]={};

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

    dp[0][0] = 1;
    rep(i,N-1){
        int val = 0;
        rep(j,n){
            if( (j/k)%2==0 ){
                int idx = (0-j+n)%n;
                (val += dp[i][idx]) %= mod;
            }
        }

        int B = 2*k;
        rep(j,B){
            for(int x=j; x<n; x+=B) dp[i+1][x] = val;

            rep(x,n/k){
                int idx = (j+1-x*k+n)%n;
                if(x%2==0) val = (val+dp[i][idx])%mod;
                else val = (val-dp[i][idx]+mod)%mod;
            }
        }
    }

    rep(i,q){
        int a,b,c;
        scanf(" %d %d %d", &a, &b, &c);
        int d = c-a;
        if(d<0) d+=n;
        printf("%d\n", dp[b][d]);
    }

    return 0;
}



Measured memory_bytes: 101060
/*  
*  Sachin Mittal
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define M 998244353
#define mod 1000000007
#define all(v) v.begin(),v.end()
#define rep(i,j,n) for(int i=j;i<n;i++)
#define rrep(i, j, n) for(int i = j; i >= n; i--)
#define F first
#define S second
#define lb lower_bound
#define mem0(dp) memset(dp,0,sizeof(dp))
#define mem1(dp) memset(dp,-1,sizeof(dp))
#define pb push_back
#define sz(s) (int)(s.size())
#define debug(x) cout << #x << " = " << x << '\n';

void solve(){
  int n;
  cin >> n;
  string s;
  cin >> s;
  int j = n - 1, ans = 0;
  rep(i, 0, n){
    if(i >= j){
      break;
    }
    if(s[i] == 'W'){
      while(j > i and s[j] == 'W'){
        j--;
      }
      if(s[j] == 'R'){
        ans++;
        swap(s[i], s[j]);
      }
    }
  }
  cout << ans << '\n';
}

int32_t main(){
  
  ios_base::sync_with_stdio(false); 
  cin.tie(0); cout.tie(0);
  int tst = 1;
  // cin >> tst;
  while(tst--){
    solve();
  }
}

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

int n;
long long int k;
pair<int, int> ab[100000];
int ans;

int main(){
  cin >> n >> k;
  for(int i = 0; i < n; i++){
    cin >> ab[i].first >> ab[i].second;
  }
  sort(ab, ab + n);
  long long int sum = 0;
  for(int i = 0; i < n; i++){
    sum += ab[i].second;
    if(sum >= k){
      ans = ab[i].first;
      break;
    }
  }
  cout << ans << endl;
}

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

int main(void) {
  string S;
  cin >> S;
  if(S == "Sunny") {
      cout << "Cloudy"; return 0;
  }
  if(S == "Cloudy") {
      cout << "Rainy"; return 0;
  }
  if(S == "Rainy") {
      cout << "Sunny"; return 0;
  }
  return 0; 
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
signed main()
{
	ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
	int a,b,c;
	cin>>a>>b>>c;
	if(a<=b*c)cout<<"Yes\n";
	else cout<<"No\n";
    return 0;
}


Measured memory_bytes: 3640
KN=list(map(int,input().strip().split()))
K=KN[0]
N=KN[1]
A_list=list(map(int,input().strip().split()))

Dis_list=[A_list[n]-A_list[n-1] for n in range(1,N)]
Dis_list.append(K-(A_list[N-1]-A_list[0]))

min_distance=K-max(Dis_list)

print(min_distance)


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

int main(){
    double A,B,H,M,AA,AB;
    cin>>A>>B>>H>>M;
    double T;
    T=H*60+M;
    
    //cout<<"T"<<T<<endl;
    
    AA=T*0.5;
    AB=M*6;
    double ans=pow(A*A+B*B-2*A*B*cos(abs(AB-AA)/57.2957795131),0.5);
    //cout<<AA<<" "<<AB<<" "<<abs(AB-AA)/57.2957795131<<endl;
    cout<<setprecision(18)<<ans<<endl;
    
    return 0;
    
}


Measured memory_bytes: 4356
input()
A = list(map(int,input().split()))
input()
M = list(map(int,input().split()))

def makeSum(A,i,T):
    if i == len(A):
        T[sum(A)] = 0
    else:
        makeSum(A,i+1,T)
        ret = A[i]
        A[i] = 0
        makeSum(A,i+1,T)
        A[i] = ret

T = {}
makeSum(A,0,T)
for m in M:
    if m in T:
        print("yes")
    else:
        print("no")

Measured memory_bytes: 7836
#include <stdio.h>
#include <stdlib.h>

void input(int *,int *,int );
int compare_int( const void *a, const void *b); //比較用関数
int search(int *,int ,int );

int main()
{
	int n;
	int *a;
	int *b;
	int t, st;

	scanf("%d",&n);

	a=(int *)malloc(n*sizeof(int));
	b=(int *)malloc(n*sizeof(int));

	input(a,b,n);
	qsort(b,n,sizeof(int),compare_int);
	t=search(a,b[0],n);
	a[t]=0;
	st=search(a,b[1],n);
	a[t]=b[0];

	for(int i=0; i<n; i++){
		if(i!=t)
			printf("%d\n",a[t]);
		else
			printf("%d\n",a[st]);
	}

	return 0;
}

void input(int *a,int *b,int n)
{
	for(int i=0; i<n; i++){
		scanf("%d",&a[i]);
		b[i]=a[i];
	}
}

int compare_int( const void *a, const void *b)
{  //qsort用整数比較関数

	return(*(int *)b-*(int *)a);   //引数はvoid *型と規定されているのでint型にcastする
}

int search(int *a,int target,int n)
{
	int i;

	for(i=0; i<n; i++){
		if(target==a[i])
			break;
	}

	return i;
}

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

int main() {
int N;
cin >> N;
vector<int> a(N);
int sum = 0;

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

int mini = sum;
int prefix_sum = 0;
for (int i = 0; i < N; ++i) {
cin >> a[i];
prefix_sum += a[i];
mini = min(mini, abs(prefix_sum - (sum - prefix_sum)));
}

cout << mini << endl;
return 0;
}

Measured memory_bytes: 3620
n = int(input())
D = list(map(int, input().split()))
D.sort()

d1, d2 = D[n // 2 - 1], D[n // 2]
ans = 0
if d1 != d2:
    ans = len(range(d1 + 1, d2 + 1))

print(ans)

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

int dp[100005][3];
int v[100005][3];
int n;


int MaxHappinessUsingDp()
{
    //for(int i=0;i<3;i++)  dp[0][i] = v[0][i];
    dp[0][0]=v[0][0];
    dp[0][1]=v[0][1];
    dp[0][2]=v[0][2];
    
        for(int i=1;i<n;i++)
        { 
          dp[i][0] = max(dp[i-1][1],dp[i-1][2])+v[i][0];
          dp[i][1] = max(dp[i-1][0],dp[i-1][2])+v[i][1];
          dp[i][2] = max(dp[i-1][1],dp[i-1][0])+v[i][2];
        }
       
     return max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]));
}
int main() {

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

	int ans = MaxHappinessUsingDp();
	cout<<ans;
	return 0;
}

Measured memory_bytes: 2560
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include<cmath>
#include<bitset>
#include<cassert>
#include<algorithm>
#include<string>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<iomanip>
#include<fstream>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

int main()
{
    fast_io;
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif

    int n;
    cin >> n;

    vector<ll> a(n, 0);
    for (int i = 0; i < n; i++)
        cin >> a[i];

    ll h = a[0], res = 0;

    for (int i = 1; i < n; i++)
    {
        if (a[i] < h)
            res += (h - a[i]);
        else 
            h = a[i];
    }

    cout << res << endl;

    return 0;
}

Measured memory_bytes: 4472