<|start_filename|>codeforces/cf1514B_and_0_sum_big.cpp<|end_filename|>
// Vicfred
// https://codeforces.com/contest/1514/problem/B
// math
#include <iostream>

using namespace std;

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

while(t--) {
    long long int n, k;
    cin >> n >> k;

    long long int ans = 1LL;
    const long long int MOD = 1e9 + 7;

    for(int i = 0; i < k; ++i) {
        ans *= n;
        ans %= MOD;
    }

    cout << ans % MOD << endl;
}
}



<|start_filename|>codeforces/cf281A_word_capitalization.cpp<|end_filename|>
// Martin
// https://codeforces.com/contest/281/problem/A
// implementation, strings

#include<iostream>
#include<string>

int main() {
    std::string word;
    std::cin >> word;

    if (word[0] > 96 && word[0] < 123)  // is lower
        word[0] = word[0] - 32;

    std::cout << word << std::endl;

    return 0;
}


<|start_filename|>codeforces/cf520A_pangram.cpp<|end_filename|>
// Martin
// https://codeforces.com/problemset/problem/520/A
// implementation, strings

#include<iostream>
#include<algorithm>
#include<string>

using namespace std;

int main() {
    int n;
    string phrase;
    string alphabet {"abcdefghijklmnopqrstuvwxyz"};

    cin >> n >> phrase;

    if (phrase.length() < alphabet.length()) {
        cout << "NO";
        return 0;
    }

    transform(phrase.begin(), phrase.end(), phrase.begin(), ::tolower);

    bool flag = true;
    for (auto letter : alphabet) {
        if (phrase.find(letter) == string::npos) {  // letter not found.
            flag = false;
            break;
        }
    }

    if (flag) cout << "YES";
    else cout << "NO";

    return 0;
}


<|start_filename|>atcoder/abc141A_weather_prediction_.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc141/tasks/abc141_a
-- implementation

import Data.List
import Data.Maybe

main = do
  let a = ["Sunny", "Cloudy", "Rainy"]
  li <- getLine
  putStrLn $ (!!) a $
    ((+1) $ fromJust $ elemIndex li a) `mod` 3


<|start_filename|>codeforces/cf1401C_mere_array.cpp<|end_filename|>
// Garo9521
// https://codeforces.com/contest/1401/problem/C
// Math

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void solve() {
    int N;
    cin >> N;
    vector <int> A(N), sorted(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i]; 
        sorted[i] = A[i];
    }
    sort(A.begin(), A.end());
    int minimum_number = A[0];
    for (int i = 0; i < N; ++i) {
        if(sorted[i] == A[i] || __gcd(A[i], minimum_number) == minimum_number)
            continue;
        cout << "NO\n";
        return;
    }
    cout << "YES\n"; 
}

int main() {
    int T;
    cin >> T;
    while (T--) {
       solve();
    }
    return 0;
}

<|start_filename|>atcoder/dp_a_frog_1.cpp<|end_filename|>
// Rasec
// https://atcoder.jp/contests/dp/tasks/dp_a
// dynamic programming

#include <bits/stdc++.h>
using namespace std;
#define optimizar_io ios_base::sync_with_stdio(false);cin.tie(0);

typedef long long int ll;
int N;
ll h[100010];

/*int dp(int i) {
	if (i == N - 1) return 0;
	if (i + 2 > N - 1)
		return dp(i + 1) + abs(h[i] - h[i + 1]);
	return min(dp(i + 1) + abs(h[i] - h[i + 1]), dp(i + 2) + abs(h[i] - h[i + 2]));
}*/

int main() {
	optimizar_io
	ll dp[100010];

	cin >> N;
	for (int i = 0; i < N; i++) cin >> h[i];
	dp[0] = 0;
	for (int i = 1; i < N; i++) {
		if (i - 2 >= 0)
			dp[i] = min(dp[i - 1] + abs(h[i] - h[i - 1]), dp[i - 2] + abs(h[i] - h[i - 2]));
		else
			dp[i] = dp[i - 1] + abs(h[i] - h[i - 1]);
	}
	cout << dp[N - 1] << "\n";
	return 0;
}

<|start_filename|>atcoder/abc175C_walking_takahashi.lua<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc175/tasks/abc175_c
-- math

x, k, d = io.read("*n","*n","*n")

x = math.abs(x)

if math.abs(x) // d >= k then
  print(math.abs(x) - k*d)
elseif (k - x // d) % 2 == 0 then
  print(math.abs(x - x // d * d))
else
  print(math.min(math.abs(x - x // d * d - d), math.abs(x - x // d * d + d)))
end


<|start_filename|>codeforces/cf1354A_alarm_clock.cpp<|end_filename|>
// Vicfred
// https://codeforces.com/contest/1354/problem/A
// math
#include <algorithm>
#include <iostream>
#include <cmath>

using namespace std;

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

    while(t--) {
        long long a, b, c, d;
        cin >> a >> b >> c >> d;

        long long ans = 0LL;

        ans += b;

        if(a-b > 0LL and (c-d) <= 0LL) {
            cout << -1 << endl;
            continue;
        }

        if(c > d and a > b)
            ans += ceil(((long double)(a-b))/(c-d))*c;

        cout << ans << endl;
    }

    return 0;
}


<|start_filename|>codeforces/cf1535B_array_reodering.hs<|end_filename|>
-- uninhm
-- https://codeforces.com/contest/1535/problem/B
-- greedy

import Control.Monad (replicateM_)
import Data.List (tails)

solve a = length [ True | (x:rest) <- tails a, y <- rest, gcd x (2*y) > 1 ]

main = do
  t <- read <$> getLine
  replicateM_ t $ do
    n <- getLine
    a <- map read . words <$> getLine
    print $ solve $ filter even a ++ filter odd a


<|start_filename|>atcoder/abc178A_not.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc178/tasks/abc178_a
-- implementation

import Data.Bits (xor)

main = do
  li <- getLine
  let x = read li :: Int
  print $ x `xor` 1


<|start_filename|>codeforces/cf1493B_planet_lapituletti.cpp<|end_filename|>
// Vicfred
// https://codeforces.com/contest/1493/problem/B
// implementation
#include <iostream>
#include <cstdio>
#include <set>
#include <algorithm>
#include <iterator>
#include <string>

using namespace std;

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

    set<char> invalid = {'3', '4', '6', '7', '9'};

    int h, m;
    int s, t;
while(T--) {
    cin >> h >> m;
    scanf("%d:%d\n", &s, &t);

    bool found = false;
    while(s < h) {
        while(t < m) {
            //cout << s << ":" << t << endl;
            string S = to_string(s);
            string T = to_string(t);
            if(S.size() < 2)
                S = '0' + S;
            if(T.size() < 2)
                T = '0' + T;
            string hour = S + T;
            bool valid = true;
            for(int i = 0; i < hour.size(); i++){
                if(invalid.count(hour[i]) > 0)
                    valid = false;
            }
            string ss, tt;
            for(int i = 0; i < S.size(); i++) {
                if(S[i] == '2')
                    ss = '5' + ss;
                else if(S[i] == '5')
                    ss = '2' + ss;
                else
                    ss = S[i] + ss;
            }
            for(int i = 0; i < T.size(); i++) {
                if(T[i] == '2')
                    tt = '5' + tt;
                else if(T[i] == '5')
                    tt = '2' + tt;
                else
                    tt = T[i] + tt;
            }
            //cout << S << ":" << T << endl;
            //cout << tt << ":" << ss << endl;
            if(stoi(ss) >= m) {
                valid = false;
            }
            if(stoi(tt) >= h) {
                valid = false;
            }
            if(valid) {
                cout << S << ":" << T << endl;
                found = true;
                break;
            }
            t++;
        }
        if(found)
            break;
        t = 0;
        s++;
    }
    if(!found)
        cout << "00:00" << endl;
}
    return 0;
}



<|start_filename|>codeforces/cf669C_chocolate_bunny.cpp<|end_filename|>
// ctx_ethanatos
// https://codeforces.com/contest/1407/problem/C
// math
#include <queue>
#include <vector>
#include <iostream>
using namespace std;
 
int main() {
  int n;
  cin >> n;
 
  queue<int> q;
  vector<bool> found(n);
  vector<int> answers(n);
  for (int i = 1; i <= n; ++i)
    q.push(i);
 
  // O(n - 1)
  while (q.size() > 1) {
    int x = q.front(); q.pop();
    int y = q.front(); q.pop();
    cout << "? " << x << " " << y << endl;
    cout << "? " << y << " " << x << endl;
 
    int px_mod_py, py_mod_px;
    cin >> px_mod_py >> py_mod_px;
    if (px_mod_py > py_mod_px) {
      // Encontre el valor de px.
      answers[x - 1] = px_mod_py;
      found[px_mod_py - 1] = true;
      q.push(y);
    } else {
      // Encontre el valor de py.
      answers[y - 1] = py_mod_px;
      found[py_mod_px - 1] = true;
      q.push(x);
    }
  }
 
  for (int i = 0; i < n; ++i) {
    if (!found[i]) {
      answers[q.front() - 1] = i + 1;
      break;
    }
  }
 
  cout << "!";
  for (int a : answers)
    cout << " " << a;
  cout << "\n";
  return 0;
}


<|start_filename|>atcoder/abc154D_dice_in_line.cpp<|end_filename|>
// https://atcoder.jp/contests/abc154/tasks/abc154_d
#include<iostream>
#include<numeric>
#include<iomanip>
#include<vector>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> max_values(n);
    for (auto &it : max_values) cin >> it;

    vector<int> legit(k);
    long long max = 0;
    for (int i = 0; i + k <= n; i++) {
        auto begining = max_values.begin() + i;
        long long current = accumulate(begining, begining+k, 0);
        if (current > max) {
            legit = {begining, begining+k};
            max = current;
        }
    }

    long double sum = 0.0L;
    for (auto v : legit) {
        double factor = 1.0L / v;
        sum += (((v + 1.0L) * v) / 2L) * factor;
    }
    cout << setprecision(15) << sum <<endl;
    return 0;
}


<|start_filename|>atcoder/abc207B_hydrate.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc207/tasks/abc207_b
-- implementation

solve [a, b, c, d] = ceiling $ go 0
  where
    go x
      | x > 10^5 = -1
      | (a+b*x)/(c*x) <= d = x
      | otherwise = go (x+1)

main = interact $ show . solve . map read . words



<|start_filename|>codeforces/cf1360G_ab_matrix.hs<|end_filename|>
--- frederick99, 6/2020
--- https://codeforces.com/contest/1360/problem/G
--- greedy, math

import Control.Monad ( replicateM_ )


abMatrix :: [Int] -> [String]
abMatrix [n, m, a, b]
    | n * a /= m * b = ["NO"]
    | otherwise =
        "YES" : take n (iterate (rotate a) firstRow)
    where
        firstRow = replicate a '1' ++ replicate (m-a) '0'
        rotate = drop <> take


readInput :: IO [Int]
readInput = map read . words <$> getLine

main :: IO ()
main = do
    t <- read <$> getLine
    replicateM_ t (abMatrix <$> readInput >>= putStr.unlines)


<|start_filename|>atcoder/abc175A_rainy_season_.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc175/tasks/abc175_b
-- brute force, recursion

import Data.List

solution' l x y z ans
  | x >= n = ans
  | y >= n = solution' l (x+1) (x+2) (x+2) ans
  | z >= n = solution' l x (y+1) (y+1) ans
  | (l!!y) + (l!!z) > (l!!x) && (l!!y /= l!!z) && (l!!y /= l!!x) && (l!!z /= l!!x) =
    solution' l x y (z+1) (ans+1)
  | otherwise =
    solution' l x y (z+1) ans
			where n = length l

solution l = solution' l 0 1 1 0

main = interact $ show . solution . reverse . sort . map read . words . last . lines


<|start_filename|>atcoder/abc178A_not.lua<|end_filename|>
-- Vicfred
-- https://atcoder.jp/contests/abc178/tasks/abc178_a
-- implementation

x = io.read("*n")

print(x ~ 1)



<|start_filename|>atcoder/abc164D_multiple_of_2019.cpp<|end_filename|>
// Vicfred
// https://atcoder.jp/contests/abc164/tasks/abc164_d
// implementation
#include <iostream>
#include <string>
#include <vector>


using namespace std;

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

    const int mod = 2019;

    vector<int> dp(mod);

    dp[0] += 1;

    int rem = 0;
    int base = 1;

    for(int i = 0; i < n; i++) {
        int d = s[n-i-1]-'0';
        rem = (rem + base * d)%mod;
        dp[rem] += 1;
        base *= 10;
        base %= mod;
    }

    long ans = 0LL;
    for(int i = 0; i < mod; i++) {
        ans += (dp[i]*(dp[i]-1))/2;
    }

    cout << ans << endl;

    return 0;
}



<|start_filename|>codeforces/cf110A_nearly_lucky_number.cpp<|end_filename|>
// Martin
// https://codeforces.com/contest/110/problem/A
// implementation, count

#include<iostream>
#include<algorithm>
#include<string>

using namespace std;

int main() {
    string number;
    cin >> number;

    auto four_cnt = count(number.begin(), number.end(), '4');
    auto seven_cnt = count(number.begin(), number.end(), '7');

    long unsigned int total = four_cnt + seven_cnt;

    if (total == (long unsigned int) 7 || total == (long unsigned int) 4) cout << "YES";
    else cout << "NO";

    return 0;
}


<|start_filename|>atcoder/abc210B_bouzu_mekuri.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc210/tasks/abc210_b
-- implementation

import Data.Bool (bool)

(.>) = flip (.)
infixr 8 .>

main = interact $ lines
  .> last
  .> zip (cycle [1, 0])
  .> filter ((=='1') . snd)
  .> fst . head
  .> bool "Takahashi" "Aoki" . (== 0)


<|start_filename|>codeforces/cf282A_bitpp_.c<|end_filename|>
// https://codeforces.com/problemset/problem/282/A
#include<stdio.h>
#include<string.h>

int main() {
    int n;
    int count = 0;
    scanf("%d\n", &n);

    char line[256];
    while (n > 0) {
        fgets(line, sizeof(line), stdin);

        if (strstr(line, "++")) count++;
        else count--;

        n--;
    }

    printf("%d", count);
    return 0;
}


<|start_filename|>atcoder/abc122A_double_helix.lisp<|end_filename|>
; uninhm
; https://atcoder.jp/contests/abc122/tasks/abc122_a
; implementation

(

let
  ((b (read)))

(cond
  ((string-equal b "A") (write-line "T"))
  ((string-equal b "T") (write-line "A"))
  ((string-equal b "C") (write-line "G"))
  ((string-equal b "G") (write-line "C"))
)

)


<|start_filename|>atcoder/abc142C_go_to_school.cpp<|end_filename|>
// uninhm
// https://atcoder.jp/contests/abc142/tasks/abc142_c
// sorting

#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>

using namespace std;

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

  vector<pair<int, int>> a;
  for(int i = 1; i <= n; ++i) {
    pair<int, int> p;
    cin >> p.first; p.second = i;

    a.push_back(p);
  }

  sort(begin(a), end(a));

  for(pair<int, int> p: a) {
    cout << p.second << " ";
  }
  cout << endl;
}


<|start_filename|>atcoder/abc145B_echo.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc145/tasks/abc145_b
-- implementation

main = do
  li <- getLine
  let n = read li
  li <- getLine
  putStrLn $
    if n `mod` 2 == 1 then
      "No"
    else if take (n `div` 2) li ==
            drop (n `div` 2) li then
      "Yes"
    else
      "No"
  


<|start_filename|>atcoder/abc155B_papers_please.cpp<|end_filename|>
// https://atcoder.jp/contests/abc155/tasks/abc155_b
#include<iostream>
#include<vector>

using namespace std;

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

    vector<int> even;
    for (int i = 0; i < n; i++) {
        cin >> tmp;
        if (tmp % 2 == 0) even.push_back(tmp);
    }

    for (auto number : even) {
        if (number % 3 != 0 && number % 5 != 0) {
            cout << "DENIED" << endl;
            return 0;
        }
    }
    cout << "APPROVED" << endl;

    return 0;
}


<|start_filename|>atcoder/abc145A_circle.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc145/tasks/abc145_a
-- basic math

main = do
  li <- getLine
  let r = read li
  putStrLn $ show $ r^2


<|start_filename|>atcoder/abc132A_fifty_fifty_.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc132/tasks/abc132_a
-- greedy

import Data.Set (fromList, size)

main = do
  s <- getLine
  putStrLn $
    if (size $ fromList s) == 2 then
      "Yes"
    else
      "No"



<|start_filename|>atcoder/abc146B_rot_n.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc146/tasks/abc146_b
-- implementation

import Data.Char

solve n c =
  chr $ ( (ord c) + n - 65 ) `mod` 26 + 65

main = do
  li <- getLine
  let n = read li
  s <- getLine
  putStrLn $ map (solve n) s



<|start_filename|>kattis/workstations.cpp<|end_filename|>
// Vicfred
// https://open.kattis.com/problems/workstations
// prioty queue, heap
#include <iostream>
#include <vector>
#include <utility>
#include <queue>

using namespace std;

typedef pair<long, long> pi;

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

    priority_queue<pi, vector<pi>, greater<pi>> researchers;
    priority_queue<pi, vector<pi>, greater<pi>> computers;

    for(int i = 0; i < n; ++i) {
        int a, s;
        cin >> a >> s;
        researchers.push({a,s});
        //computers.push({a+s,a+s+m});
    }

    long ans = 0;

    while(!researchers.empty()) {
        auto item = researchers.top();
        researchers.pop();
        long a = item.first;
        long s = item.second;
        //cout << item.first << " " << item.second << endl;
        while(!computers.empty()) {
            auto computer = computers.top();
            if(a < computer.first) break;
            computers.pop();
            if(a >= computer.first and a <= computer.second) {
                //cout << "got " << computer.first << endl;
                ans += 1;
                break;
            }
        }
        //cout << "pushed " << a+s << " " << a+s+m << endl;
        computers.push({a+s, a+s+m});
    }

    cout << ans << endl;

    return 0;
}



<|start_filename|>atcoder/abc213B_booby_prize.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc213/tasks/abc213_b
-- implementation

import Data.List (sortBy)

solve :: [Int] -> Int
solve =
  snd . (!! 1) . sortBy (flip compare) . flip zip [1..]

main = getLine >> getLine >>= print . solve . map read . words


<|start_filename|>atcoder/abc181D_hachi.cpp<|end_filename|>
// Vicfred
// https://atcoder.jp/contests/abc181/tasks/abc181_d
// greedy, string manipulation, math
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <map>

using namespace std;

int main() {
    string S;
    cin >> S;

    sort(begin(S), end(S));

    if(S.size() < 3) {
        do {
            if(stoi(S)%8 == 0) {
                cout << "Yes" << endl;
                return 0;
            }
        } while(next_permutation(begin(S), end(S)));

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

    vector<string> multiples;

    for(int i = 1; i*8 <= 999; i++) {
        if(i*8 >= 100 && i*8 <= 999)
            multiples.push_back(to_string(i*8));
    }

    map<char, int> counter;
    for(char c: S)
        counter[c] += 1;

    for(string multiple: multiples) {
        bool valid = true;
        for(char c = '0'; c <= '9'; c++) {
            if(count(begin(multiple), end(multiple), c) >
               counter[c]) {
                valid = false;
            }
        }

        if(valid) {
            cout << "Yes" << endl;
            return 0;
        }
    }

    cout << "No" << endl;

    return 0;
}



<|start_filename|>atcoder/abc213A_bitwise_exclusive_or_.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc213/tasks/abc213_a
-- implementation

import Data.Bits (xor)

main = do
  [a, b] <- map read . words <$> getLine :: IO [Int]
  print $ xor a b


<|start_filename|>atcoder/abc167D_teleporter.cpp<|end_filename|>
// Vicfred
// https://atcoder.jp/contests/abc167/tasks/abc167_d
// implementation
#include <iostream>
#include <vector>

using namespace std;

int main() {
    const long long int MAXN = 2LL*10e5+5LL;

    long long n, k;
    cin >> n >> k;

    vector<long long> A(MAXN);
    for(long long i = 1LL; i <= n; i++)
        cin >> A[i];

    vector<long long> visited(MAXN);

    long long current = 1LL;
    long long steps = 0LL;
    long long cycle_length = 0LL;

    while(visited[current] == 0LL and steps < k) {
        visited[current] = steps;
        steps += 1LL;
        current = A[current];
        cycle_length = steps-visited[current];
    }

    int left = (k-visited[current])%cycle_length;

    while(left > 0) {
        current = A[current];
        left -= 1;
    }

    cout << current << endl;

    return 0;
}



<|start_filename|>codeforces/cf1535A_fair_playoff.hs<|end_filename|>
-- uninhm
-- https://codeforces.com/contest/1535/problem/A
-- implementation

import Data.List (sort)

pairToList (a, b) = [a, b]

solve :: [Int] -> String
solve l =
  if drop 2 (sort l) ==
     sort (map maximum $ pairToList $ splitAt 2 l) then
    "Yes"
  else
    "No"

main = interact $ unlines . map (solve . map read . words) . tail . lines


<|start_filename|>codeforces/cf1324D_pair_of_topics.cpp<|end_filename|>
// Vicfred
// https://codeforces.com/problemset/problem/1324/D
// math, binary search

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

using namespace std;

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

    vector<int> a(n);
    vector<int> b(n);

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

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

    vector<int> c(n);
    for(int i = 0; i < n; i++) {
        c[i] = a[i] - b[i];
    }

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

    long long int ans = 0;
    for(auto i = 0; i < n; i++) {
        int match = c[i]*(-1)+1;

        int left = i+1;
        int right = n-1;

        while(left <= right) {
            int middle = (left+right)/2;

            if(c[middle] < match) {
                left = middle+1;
            } else {
                right = middle-1;
            }
        }

        ans += n-left;
    }

    cout << ans << endl;
}



<|start_filename|>atcoder/abc145B_echo_.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc145/tasks/abc145_b
-- implementation

solve s
	| n `mod` 2 == 1 = "No"
	| take (n `div` 2) s ==
		drop (n `div` 2) s = "Yes"
	| otherwise = "No"
		where n = length s

main = interact $ solve . last . lines


<|start_filename|>atcoder/abc154C_distinct_or_not.cpp<|end_filename|>
// https://atcoder.jp/contests/abc154/tasks/abc154_c
#include<iostream>
#include<set>

using namespace std;

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

    set<int> values;
    int value;
    for (int i = 0; i < n; i++) {
        cin >> value;
        values.insert(value);
    }

    if (int(values.size()) == n) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}


<|start_filename|>codeforces/cf1360H_binary_median.hs<|end_filename|>
--- frederick99, 6/2020
--- https://codeforces.com/contest/1360/problem/H
--- math, simulation, binary

{-# LANGUAGE TupleSections #-}
import           Control.Monad ( replicateM_ )
import           Data.List     ( foldl' )
import qualified Data.Set as Set


type Bit   = Char
type Byte  = [Bit]
type Width = Int


binaryMedian :: Width -> [Byte] -> Byte
binaryMedian width _remove = toByte width median'
    where
        median = 2^(width-1) - 1
        remove = fromByte `map` _remove
        (_, median', _) = foldl' go (False, median, Set.empty) remove

        go (isOdd, med, seen) rem = (isOdd', med', seen') where
                isOdd'= not isOdd
                seen' = Set.insert rem seen
                get f = head $ dropWhile (`Set.member` seen) (tail $ iterate f med)
                med' =
                    if  not isOdd && rem <= med then get succ
                    else if isOdd && rem >= med then get pred
                    else med


fromBit :: Bit -> Integer
fromBit '0' = 0
fromBit '1' = 1


toBit :: Integer -> Bit
toBit 0 = '0'
toBit 1 = '1'


fromByte :: Byte -> Integer
fromByte = foldl' go 0
    where go num bit = 2*num + fromBit bit


toByte :: Width -> Integer -> Byte
toByte m = foldl' go "" . take m . iterate (`div` 2)
    where go bits k = toBit (k `mod` 2) : bits


readInput :: IO (Width, [Byte])
readInput = do
    [n, m] <- map read . words <$> getLine
    (m, ) <$> (sequence $ replicate n getLine)


main :: IO ()
main = do
    t <- read <$> getLine
    replicateM_ t (uncurry binaryMedian <$> readInput >>= putStrLn)


<|start_filename|>codeforces/cf1509B_tmt_document.hs<|end_filename|>
-- user: nel_tu_
-- path: https://codeforces.com/contest/1509/problem/B
-- tags: math, greedy

{-# LANGUAGE ViewPatterns #-}
import Control.Monad ( replicateM_ )
import Data.Bool ( bool )

solve :: Int -> String -> Bool
solve ((`div` 3) -> k) str = valid && t == k
    where
    (t, valid) = foldr loop (0, True) str

    loop x (upd x -> t, valid) = (t, valid && 0<=t && t<=k)

    upd 'T' = succ
    upd 'M' = pred


getInt = read <$> getLine
main = do
    n <- getInt
    replicateM_ n (solve <$> getInt <*> getLine  >>=  putStrLn . bool "NO" "YES")



<|start_filename|>atcoder/abc141C_attack_survival.cpp<|end_filename|>
// uninhm
// https://atcoder.jp/contests/abc141/tasks/abc141_c
// greedy

#include<iostream>

using namespace std;

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

  int scores[n]{};

  int a;
  for(int i = 0; i < q; ++i) {
    cin >> a;
    scores[a-1]++;
  }

  for(int i = 0; i < n; ++i)
    if(q - scores[i] < k)
      cout << "Yes" << endl;
    else
      cout << "No" << endl;
}


<|start_filename|>codeforces/cf1501B_napoleon_cake1.cpp<|end_filename|>
// RasecBadguy
// https://codeforces.com/contest/1501/problem/B
// Data structures, Segment tree
#include <bits/stdc++.h>
using namespace std;
#define optimizar_io ios_base::sync_with_stdio(false);cin.tie(0);
#define MAXN 1000010
 
long long int arr[MAXN];
 
struct SegmentTree {
    
    long long int *stree;
    vector<long long int> lazy;
 
    SegmentTree(int N) {
        stree = new long long int[getSegmentTreeSize(N)];
        lazy.assign(getSegmentTreeSize(N), 0);
        buildTree(1, 0, N - 1);
    }
 
    void buildTree(int nodo, int L, int R) {
 
        if (L == R)
            stree[nodo] = arr[L];
        else {
            int mid = (L + R)/2, leftIdx = 2 * nodo, rightIdx = 2 * nodo + 1;
            buildTree(leftIdx, L, mid);
            buildTree(rightIdx, mid + 1, R);
            stree[nodo] = stree[leftIdx] + stree[rightIdx];
        }
    }
 
    long long int query(int nodo, int L, int R, int i, int j) {
 
        int mid = (L + R) / 2, leftIdx = 2 * nodo, rightIdx = 2 * nodo + 1;
        if (lazy[nodo] != 0) {
            stree[nodo] += (R - L + 1) * lazy[nodo];
            if (L != R) {
                lazy[leftIdx] += lazy[nodo];
                lazy[rightIdx] += lazy[nodo];
            }
            lazy[nodo] = 0;
        }
        
        if (L >= i && R <= j)
            return stree[nodo];
        
        if (j <= mid)
            return query(leftIdx, L, mid, i, j);
        if (i > mid)
            return query(rightIdx, mid + 1, R, i, j);
        
        long long int leftResult = query(leftIdx, L, mid, i, mid);
        long long int rightResult = query(rightIdx, mid + 1, R, mid + 1, j);
        long long int result = leftResult + rightResult;
        return result;
    }
 
    void updateRange(int nodo, int low, int high, int startRange, int endRange, long long int value) {
 
        int mid = (low + high) / 2, leftIdx = 2 * nodo, rightIdx = 2 * nodo + 1;
        if (lazy[nodo] != 0) {
            stree[nodo] += (high - low + 1) * lazy[nodo];
            if (low != high) {
                lazy[leftIdx] += lazy[nodo];
                lazy[rightIdx] += lazy[nodo];
            }
            lazy[nodo] = 0;
        }
        
        if (low > high || startRange > high || endRange < low) {
            return;
        }
        
        if (startRange <= low && endRange >= high) {
            stree[nodo] += (high - low + 1) * value;
            if (low != high) {
                lazy[leftIdx] += value;
                lazy[rightIdx] += value;
            }
            return;
        }
        updateRange(leftIdx, low, mid, startRange, endRange, value);
        updateRange(rightIdx, mid + 1, high, startRange, endRange, value);
        stree[nodo] = stree[leftIdx] + stree[rightIdx];
    }
 
    int getSegmentTreeSize(int N) {
        int size = 1;
        for(; size < N; size <<= 1);
        return size << 1;
    }
};
 
int main() {
	optimizar_io
	int tc, n, a[200010];
 
	cin >> tc;
	while (tc--) {
		cin >> n;
		for (int i = 0; i < n; i++) cin >> a[i];
		SegmentTree st(n);
		for (int i = 0; i < n; i++) {
			if (a[i]) {
				// cout << i - a[i] + 1 << "," << i << "\n";
				st.updateRange(1, 0, n - 1, max(0, i - a[i] + 1), i, 1);
			}
		}
		for (int i = 0; i < n; i++) {
			if (st.query(1, 0, n - 1, i, i))
				cout << "1 ";
			else
				cout << "0 ";
		}
		cout << "\n";
	}
	return 0;
}

<|start_filename|>atcoder/abc137A_+-x.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc137/tasks/abc137_a
-- implementation

main = do
  li <- getLine
  let a:b:[] = map read $ words li
  print $
    max (a + b) $ max (a - b) (a * b)


<|start_filename|>atcoder/abc131A_security.cpp<|end_filename|>
/* TsukiZombina
 * https://atcoder.jp/contests/abc131/tasks/abc131_a
 * implementation
 * */

#include <iostream>
#include <string>

int main()
{
    std::string S;
    std::cin >> S;
    bool flag = 0;
    for (size_t i = 0; i < S.size() - 1; i++)
    {
        if (S[i] == S[i + 1]) {
            flag = 1;
            break;
        } else {
            continue;
        }  
    }

    if (flag) {
        std::cout << "Bad";
    } else {
        std::cout << "Good";
    }

    return 0;
}


<|start_filename|>classical/fibonacci_dp.cpp<|end_filename|>
#include <iostream>
#include <vector>

using namespace std;

int main() {
    const int max_n = 21;
    vector<long long> fibonacci(max_n);
    fibonacci[0] = 0;
    fibonacci[1] = 1;
    for(int i = 2; i < max_n; ++i) {
        fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];
    }

    for(int i = 0; i < max_n; ++i) {
        cout << "F_" << i << " = " << fibonacci[i] << endl;
    }
}


<|start_filename|>atcoder/abc155A_poor.cpp<|end_filename|>
// https://atcoder.jp/contests/abc155/tasks/abc155_a

#include<iostream>
#include<set>

using namespace std;

int main() {
    int a, b, c;
    cin >> a >> b >> c;

    set<int> values;
    values.insert(a);
    values.insert(b);
    values.insert(c);

    if (values.size() == 2) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}


<|start_filename|>atcoder/abc125B_resale.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc125/tasks/abc125_b
-- greedy

solve n v c ans
  | n == 0 = ans
  | x > y =
    solve (n-1) (tail v) (tail c) (ans+x-y)
  | otherwise =
    solve (n-1) (tail v) (tail c) ans
      where x = head v
            y = head c

main = do
  li <- getLine
  let n = read li
  li <- getLine
  let v = map read $ words li
  li <- getLine
  let c = map read $ words li
  
  print $ solve n v c 0


<|start_filename|>kattis/dancerecital.cpp<|end_filename|>
// Vicfred
// https://open.kattis.com/problems/dancerecital
// brute force, permutations
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>

using namespace std;

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

    vector<string> recital(R);

    for(int i = 0; i < R; ++i)
        cin >> recital[i];

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

    int minima = 1 << 30;
    do {
        int quickchange = 0;
        for(int i = 0; i < R - 1; ++i) {
            for(int idx = 0; idx < recital[i].size(); ++idx) {
                char c = recital[i][idx];
                bool found = false;
                for(int j = 0; j < recital[i+1].size(); ++j) {
                    char d = recital[i+1][j];
                    if(c == d)
                        found = true;
                }
                if(found)
                    quickchange += 1;
            }
        }
        minima = min(minima, quickchange);
    } while(next_permutation(recital.begin(), recital.end()));

    cout << minima << endl;

    return 0;
}



<|start_filename|>kattis/candydivision.cpp<|end_filename|>
// Vicfred
// https://open.kattis.com/problems/candydivision
// math
#include <iostream>
#include <set>

using namespace std;

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

    set<long> divisors;

    divisors.insert(0);
    for(long i = 1; i*i <= N; ++i) {
        if(N%i == 0) {
            divisors.insert(i-1);
            divisors.insert(N/i-1);
        }
    }

    for(long item: divisors) {
        cout << item << " ";
    } cout << endl;

    return 0;
}


<|start_filename|>atcoder/ablD_flat_subsequence.cpp<|end_filename|>
// Vicfred
// https://atcoder.jp/contests/abl/tasks/abl_d
// segment tree
#include <iostream>
#include <vector>
#include <algorithm>
#include "segtree.hpp"

using namespace std;
using namespace atcoder;

int main() {
    const int maxn = 3e5+1;
    int n, k;
    cin >> n >> k;

    vector<int> a(n);
    for(int &i: a)
        cin >> i;

    auto operation = [] (int a, int b) -> int { return max(a, b); };
    auto starting = [] () -> int { return 0; };

    segtree<int, operation, starting> segmentitos(maxn);

    int ans = -1;
    for(int i: a) {
        int l = max(i - k, 0);
        int r = min(i + k, 300'000);
        int maxima = segmentitos.prod(l, r + 1) + 1;
        ans = max(ans, maxima);
        segmentitos.set(i, maxima);
    }

    cout << ans << endl;

    return 0;
}


<|start_filename|>atcoder/abc171C_one_quadrillion_and_one_dalmatians_.hs<|end_filename|>
-- frederick99
-- https://atcoder.jp/contests/abc171/tasks/abc171_c
-- math

import Data.Char (chr)
 
solve :: Int -> Int -> (Int, String)
solve p n = (q, chr (97 + r) : s)
  where
    (m, s) = if n > p
               then solve (p * 26) (n - p)
               else (n - 1, "")
    (q, r) = m `divMod` 26
 
main :: IO ()
main = getLine >>= putStrLn . snd . solve 26 . read



<|start_filename|>codeforces/cf1405A_permutation_forgery.cpp<|end_filename|>
// TsukiZombina
// https://codeforces.com/contest/1405/problem/A
// math

#include <iostream>
#include <algorithm>
#include <vector>

int main()
{
    int t;
    std::cin >> t;
    for (int i = 0; i < t; i++)
    {
        int n;
        std::cin >> n;
        std::vector<int> p(n);
        for (auto& x : p)
        {
            std::cin >> x;
        }
        std::reverse(p.begin(), p.end());
        for (const auto& x : p)
        {
            std::cout << x << " ";
        }
        std::cout << std::endl;
        
    }
    return 0;
}

<|start_filename|>codeforces/cf677A_vanya_and_fence.cpp<|end_filename|>
// Martin
// https://codeforces.com/problemset/problem/677/A
// implementation

#include<iostream>

int main() {
    int n, h;
    std::cin >> n >> h;
    int height, answer {0};
    while (n--) {
        std::cin >> height;
        if (height > h) answer += 2;
        else answer++;
    }
    std::cout << answer;
    return 0;
}


<|start_filename|>codeforces/cf1332B_composite_coloring.cpp<|end_filename|>
// Vicfred
// https://codeforces.com/problemset/problem/1332/B
// math, greedy

#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <set>

using namespace std;

// requires Iterator satisfies RandomAccessIterator
template <typename Iterator>
size_t prime_sieve(Iterator start, Iterator end) {
    if (start == end) return 0;
    // clear the container with 0
    std::fill(start, end, 0);
    // mark composites with 1
    for (Iterator prime_it = start + 1; prime_it != end; ++prime_it) {
        if (*prime_it == 1) continue;
        // determine the prime number represented by this iterator location
        size_t stride = (prime_it - start) + 1;
        // mark all multiples of this prime number up to max
        Iterator mark_it = prime_it;
        while ((end - mark_it) > stride) {
            std::advance(mark_it, stride);
            *mark_it = 1;
        }
    }
    // copy marked primes into container
    Iterator out_it = start;
    for (Iterator it = start + 1; it != end; ++it) {
        if (*it == 0) {
            *out_it = (it - start) + 1;
            ++out_it;
        }
    }
    return out_it - start;
}

int main() {
    vector<int> primes(100);
    int count = prime_sieve(primes.begin(), primes.end());

    int t;
    cin >> t;

    for(int kase = 0; kase < t; kase++) {
        int n;
        cin >> n;
        vector<int> a(n);

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

        map<int,set<int>> elements;
        for(int item: a) {
            for(int prime: primes) {
                if(item%prime == 0) {
                    elements[prime].insert(item);
                    break;
                }
            }
        }

        int m = 1;
        vector<int> color(1001);
        for(int prime: primes) {
            if(elements[prime].size() > 0) {
                for(int item: elements[prime]) {
                    color[item] = m;
                }
                m += 1;
            }
        }

        cout << m-1 << endl;
        for(int item: a) {
            cout << color[item] << " ";
        } cout << endl;
    }
    return 0;
}



<|start_filename|>codeforces/cf50A_domino_piling_.c<|end_filename|>
// https://codeforces.com/problemset/problem/50/A
#include<stdio.h>

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

    int result = (n * m) / 2;
    printf("%d\n", result);
    return 0;
}


<|start_filename|>atcoder/abc176D_wizard_in_maze.cpp<|end_filename|>
// Vicfred
// https://atcoder.jp/contests/abc176/tasks/abc176_d
// dfs, bfs, flood fill
#include <iostream>
#include <deque>
#include <vector>
#include <string>
#include <utility>
#include <tuple>

using namespace std;

const int INF = 1<<30;

int main() {
    int H, W;
    cin >> H >> W;

    int ch, cw, dh, dw;

    cin >> ch >> cw;
    cin >> dh >> dw;

    ch -= 1;
    cw -= 1;
    dh -= 1;
    dw -= 1;

    vector<string> s(H);
    for(auto &row: s)
        cin >> row;

    vector<vector<int>> dist(H, vector<int>(W, INF));
    deque<pair<int,int>> q;
    q.push_back({ch, cw});
    dist[ch][cw] = 0;

    int dir[] = {1, 0, -1, 0, 1};

    while(!q.empty()) {
        int cx, cy;
        tie(cx, cy) = q.front();
        q.pop_front();
        for(int i = 0; i < 4; i++) {
            int nx = cx + dir[i];
            int ny = cy + dir[i + 1];
            if(nx < 0 or ny < 0 or nx >= H or ny >= W)
                continue;
            if(s[nx][ny] == '#')
                continue;
            if(dist[nx][ny] > dist[cx][cy]) {
                dist[nx][ny] = dist[cx][cy];
                q.push_front({nx, ny});
            }
        }

        for(int i = -2; i <= 2; i++) {
            for(int j = -2; j <= 2; j++) {
                int nx = cx + i;
                int ny = cy + j;
                if(nx < 0 or ny < 0 or nx >= H or ny >= W)
                    continue;
                if(s[nx][ny] == '#')
                    continue;
                if(dist[nx][ny] > dist[cx][cy] + 1) {
                    dist[nx][ny] = dist[cx][cy] + 1;
                    q.push_back({nx, ny});
                }
            }
        }
    }

    if(dist[dh][dw] == INF)
        dist[dh][dw] = -1;

    cout << dist[dh][dw] << endl;

    return 0;
}



<|start_filename|>atcoder/abc125A_biscuit_generator_.lisp<|end_filename|>
; uninhm
; https://atcoder.jp/contests/abc125/tasks/abc125_a
; math

(

let ((a (read))
     (b (read))
     (c (read)))

(write (
  * b (values (floor c a))
))

)


<|start_filename|>atcoder/abc130A_rounding.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc130/tasks/abc130_a
-- implementation

main = do
  li <- getLine
  let x:a:[] = (map read $ words li) :: [Int]
  print $ if x < a then 0 else 10


<|start_filename|>codeforces/cf1555A_pizzaforces.cpp<|end_filename|>
// uninhm
// https://codeforces.com/contest/1555/problem/A
// greedy

#include <iostream>

int
main ()
{
  int t;
  std::cin >> t;

  long long int n;
  while (t--)
    {
      std::cin >> n;
      if (n <= 6)
        std::cout << 15 << std::endl;
      else
        std::cout << (n + n%2) * 5 / 2 << std::endl;
    }
}

<|start_filename|>codeforces/cf1525A_potion-making.hs<|end_filename|>
-- uninhm
-- https://codeforces.com/contest/1525/problem/A
-- basic math

solve :: String -> String -- Read the whole input, return the whole output
solve = unlines . fmap (show . div 100 . gcd 100 . read) . tail . lines

main :: IO ()
main = interact $ solve


<|start_filename|>codeforces/cf1283C_friends_and_gifts.cpp<|end_filename|>
// Vicfred
// https://codeforces.com/contest/1283/problem/C
// implementation
#include <iostream>
#include <vector>

using namespace std;

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

    vector<int> f(n);
    vector<int> indegree(n), outdegree(n);

    for(int i = 0; i < n; i++) {
        cin >> f[i];
        f[i] -= 1;
        if(f[i] != -1) {
            outdegree[i] += 1;
            indegree[f[i]] += 1;
        }
    }

    //for(int item: f)
    //    cout << item+1 << " ";
    //cout << endl;
    //for(int item: indegree)
    //    cout << item << " ";
    //cout << endl;
    //for(int item: outdegree)
    //    cout << item << " ";
    //cout << endl;

    vector<int> alones;
    for(int i = 0; i < n; i++) {
        if(indegree[i] == 0 and outdegree[i] == 0) {
            alones.push_back(i);
        }
    }

    //cout << "solitos calculados " << alones.size() << endl;

    if(alones.size() == 1) {
        //cout << "caso 1" << endl;
        int forever = alones[0];
        for(int i = 0; i < n; i++) {
            if(indegree[i] == 0 and i != forever) {
                f[forever] = i;
                outdegree[forever] += 1;
                indegree[i] += 1;
                break;
            }
        }
    } else if(alones.size() >= 2) {
        //cout << "caso 2" << endl;
        for(int i = 0; i < alones.size(); i++) {
            int forever = alones[i];
            int alone = alones[(i + 1) % alones.size()];
            f[forever] = alone;
            outdegree[forever] += 1;
            indegree[alone] += 1;
        }
    }

    //cout << "solitos juntados" << endl;

    vector<int> heads, tails;
    for(int i = 0; i < n; i++) {
        if(indegree[i] == 0) heads.push_back(i);
        if(outdegree[i] == 0) tails.push_back(i);
    }

    for(int i = 0; i < tails.size(); i++) {
        f[tails[i]] = heads[i];
    }

    for(int item: f) {
        cout << item + 1 << " ";
    } cout << endl;

    return 0;
}



<|start_filename|>atcoder/abc138B_resistors_in_parallel.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc138/tasks/abc138_b
-- implementation

main = do
  li <- getLine
  li <- getLine
  let a = map (\x -> (1/) $ read x) $ words li
  print $ (1/) $ sum a



<|start_filename|>atcoder/abc178A_not_.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc178/tasks/abc178_a
-- implementation

import Data.Bits (xor)

main = interact $ show . xor 1 . (read :: String -> Int)


<|start_filename|>atcoder/abc145A_circle_.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc145/tasks/abc145_a
-- basic math

main = interact $ show . (^2) . read


<|start_filename|>atcoder/abc133A_t_or_t.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc133/tasks/abc133_a
-- basic math

main = do
  li <- getLine
  let n:a:b:[] = map read $ words li
  print $ min (n * a) b


<|start_filename|>atcoder/abc130A_rounding_.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc130/tasks/abc130_a
-- implementation

solve :: [Int] -> Int
solve [x, a] = if x < a then 0 else 10

main :: IO ()
main = interact $ show . solve . map read . words


<|start_filename|>codeforces/cf1311A_add_odd_or_subs_even.cpp<|end_filename|>
// Martin
// https://codeforces.com/contest/1311/problem/A
// greedy, math

#include<iostream>

using namespace std;

int main() {
    int t, a, b;
    cin >> t;

    while (t--) {
        cin >> a >> b;
        int diff = a - b;
        bool diff_odd = diff & 1;
        if (diff < 0) {
            if (diff_odd)  // diff is odd, just: `a + diff`
                cout << 1;
            else  // means we need two operations: `a + (diff - 1)`, then + 1
                cout << 2;
        } else if (diff > 0) { // we need to decrease `a`
            if (diff_odd)  // diff is odd, so: `a - (diff + 1), then + 1
                cout << 2;
            else
                cout << 1;  // diff is even, just: `a - diff`
        } else {
            cout << 0;
        }

        cout << endl;
    }

    return 0;
}


<|start_filename|>atcoder/abc178C_ubiquity_.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc178/tasks/abc178_c
-- math, combinatorics

mmod = 10^9+7

binpow a b
  | b == 0    = 1
  | otherwise =
    if b `mod` 2 == 1 then
      res `mod` mmod * res `mod` mmod * a `mod` mmod
    else
      res `mod` mmod * res `mod` mmod
        where res = binpow a (b `div` 2)

solve n = (binpow 10 n) - ((*2) $ binpow 9 n) + (binpow 8 n)
normalize x = (x + mmod) `mod` mmod

main = interact $ show . normalize . solve . read


<|start_filename|>codeforces/cf266A_stones_on_the_table.cpp<|end_filename|>
// Martin
// https://codeforces.com/problemset/problem/266/A
// implementation

#include<iostream>

int main() {
    int n, counter {0};
    std::string s;

    std::cin >> n >> s;

    for (unsigned int i = 1; i < s.length(); i++) {
        if (s[i] == s[i - 1]) counter++;
    }

    std::cout << counter;

    return 0;
}


<|start_filename|>codeforces/cf1501A_alexey_and_train.cpp<|end_filename|>
// Vicfred
// https://codeforces.com/contest/1501/problem/A
// implementation
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main() {
    long t;
    cin >> t;

while(t--) {
    long n;
    cin >> n;
    vector<long> a(n+1), b(n+1);

    for(int i = 1; i <= n; ++i) {
        cin >> a[i] >> b[i];
    }

    vector<long> tm(n+1);
    for(int i = 1; i <= n; ++i) {
        cin >> tm[i];
    }

    long current = 0;
    long wait;
    for(int i = 1; i <= n; ++i) {
        current += a[i] - b[i-1] + tm[i]; // arrival at station i
        // cout << "arrive=" << current << endl;
        wait = (b[i] - a[i] - 1)/2 + 1;
        // cout << "a[" << i << "]=" << a[i] << endl;
        // cout << "b[" << i << "]=" << b[i] << endl;
        // cout << "wait " << wait << " seconds" << endl;
        current += wait; // wait this long

        if(current < b[i] && i != n)
            current = b[i];
        
        //cout << "leave=" << current << endl;
    }
    cout << current - wait << endl;
}
}



<|start_filename|>codeforces/cf71A_way_too_long_words__.hs<|end_filename|>
-- Vicfred
-- https://codeforces.com/problemset/problem/71/A
-- implementation
import Control.Monad

transform :: String -> String
transform s
    | (length s <= 10) = s
    | otherwise = ([head s] ++ show (length s - 2) ++ [last s])

main :: IO ()
main =  do
    n <- getLine
    inputs <- replicateM (read n) getLine
    let answers = map transform inputs
    sequence_ (map putStrLn answers)



<|start_filename|>atcoder/abc137B_one_clue.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc137/tasks/abc137_b
-- math

import Data.List (intercalate)

main = do
  li <- getLine
  let k:x:[] = map read $ words li
  putStrLn $ intercalate " " $ map show $
    if x - k + 1 < -10^6 then
      [-10^6 .. x+k-1]
    else if x + k - 1 > 10^6 then
      [10^6 .. x-k+1]
    else
      [x-k+1 .. x+k-1]


<|start_filename|>atcoder/abc139A_power_socket.hs<|end_filename|>
-- Vicfred
-- https://atcoder.jp/contests/abc139/tasks/abc139_b
-- math
main :: IO ()
main = do [a, b] <- map read . words <$> getLine; print $ div (b+a-3) (a-1)



<|start_filename|>atcoder/abc186B_blocks_on_grid.cpp<|end_filename|>
// uninhm
// https://atcoder.jp/contests/abc186/tasks/abc186_b
// implementation

#include <iostream>
#include <vector>

using namespace std;

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

  int minimum = 1 << 30;

  vector<int> grid;
  grid.reserve(h*w+10);

  int x;
  for(int i = 0; i < h*w; ++i) {
    cin >> x;
    if(x < minimum)
      minimum = x;

    grid.push_back(x);
  }

  int ans = 0;
  for(const int& i: grid)
    ans += i - minimum;

  cout << ans << endl;
}


<|start_filename|>codeforces/cf277A_learning_languages.cpp<|end_filename|>
// Vicfred
// https://codeforces.com/problemset/problem/277/A
// dsu, dfs
#include <iostream>
#include <vector>
#include <map>
#include <unordered_set>

using namespace std;

class UnionFind {
    private:
        vector<int> p, rank, setSize;
        int numSets;
    public:
        UnionFind(int N) {
            setSize.assign(N, 1); numSets = N; rank.assign(N, 0);
            p.assign(N, 0); for (int i = 0; i < N; i++) p[i] = i; }
        int findSet(int i) { return (p[i] == i) ? i : (p[i] = findSet(p[i])); }
        bool isSameSet(int i, int j) { return findSet(i) == findSet(j); }
        void unionSet(int i, int j) {
            if (!isSameSet(i, j)) { numSets--;
                int x = findSet(i), y = findSet(j);
                if (rank[x] > rank[y]) { p[y] = x; setSize[x] += setSize[y]; }
                else                   { p[x] = y; setSize[y] += setSize[x];
                    if (rank[x] == rank[y]) rank[y]++; } } }
        int numDisjointSets() { return numSets; }
        int sizeOfSet(int i) { return setSize[findSet(i)]; }
};

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

    map<int, unordered_set<int>> languages;

    bool something = false;

    for(int i = 0; i < n; ++i) {
        int k;
        cin >> k;
        if(k > 0)
            something = true;

        for(int j = 0; j < k; ++j) {
            int language;
            cin >> language;
            languages[i].insert(language);
        }
    }

    int extra =  0;

    if(!something) {
        languages[0].insert(1);
        extra += 1;
    }

    UnionFind UF(n);

    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < i; ++j) {
            for(int language: languages[i]) {
                if(languages[j].count(language) > 0) {
                    UF.unionSet(i,j);
                }
            }
        }
    }

    cout << UF.numDisjointSets()-1+extra << endl;

    return 0;
}


<|start_filename|>atcoder/abc186A_brick.cpp<|end_filename|>
// uninhm
// https://atcoder.jp/contests/abc186/tasks/abc186_a
// basic math

#include <iostream>

using namespace std;

int main() {
  int n, w;
  cin >> n >> w;
  cout << n/w << endl;
}


<|start_filename|>atcoder/abc211A_blood_pressure.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc211/tasks/abc211_a
-- implementation

solve [a, b] =
  (a - b) / 3 + b

main = interact $ show . solve . map read . words



<|start_filename|>atcoder/abc143C_slimes.cpp<|end_filename|>
// uninhm
// https://atcoder.jp/contests/abc143/tasks/abc143_c
// implementation

#include<iostream>
#include<stdio.h>

using namespace std;

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

  char c, last;
  scanf("%c", &c);
  last = c;

  int ans = 1;
  for(int i = 1; i < n; ++i) {
    cin >> c;
  
    if(c != last)
      ans++;

    last = c;
  }

  cout << ans << endl;
}


<|start_filename|>atcoder/abc134A_dodecagon.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc134/tasks/abc134_a
-- implementation

main = do
  li <- getLine
  let r = read li
  print $ 3 * r^2


<|start_filename|>codeforces/cf1371A_magical_sticks.cpp<|end_filename|>
// Vicfred
// https://codeforces.com/contest/1371/problem/A
// implementation
#include <iostream>

using namespace std;

int main() {
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        cout << n/2 + n%2 << endl;
    }
    return 0;
}



<|start_filename|>atcoder/abc144D_water_bottle.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc144/tasks/abc144_d
-- math, trigonometry

-- hahahaha oneliner

main = do interact (\li -> (show $ (\x -> x / 6.283185307179586 * 360) $ ((\[a,b,x] -> atan(if x <= b/2 * (a^2) then ((a * b ^ 2) / ( 2 * x)) else ((2 * (b - (x / (a ^ 2)))) / a))) :: [Double] -> Double) $ ((map read $ words li) :: [Double])) ++ "\n")


<|start_filename|>atcoder/abc141A_weather_prediction__.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc141/tasks/abc141_a
-- implementation

import Data.List
import Data.Maybe

days = ["Sunny", "Cloudy", "Rainy"]
day i = days !! i
dayidx d = fromJust $ elemIndex d days

main = interact $ day . (`mod` 3) . (+1) . dayidx . init


<|start_filename|>atcoder/abc185B_smartphone_addiction.cpp<|end_filename|>
// uninhm
// https://atcoder.jp/contests/abc185/tasks/abc185_b
// simulation

#include <iostream>

using namespace std;

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

  int bat = n;
  int a, b;
  int last = 0;
  for(int i = 0; i < m; ++i) {
    cin >> a >> b;
    bat -= a - last;
    if(bat <= 0) {
      cout << "No" << endl;
      return 0;
    }
    bat += b - a;
    if(bat > n) bat = n;
    last = b;
  }

  if(bat - (t - last) <= 0)
    cout << "No" << endl;
  else
    cout << "Yes" << endl;

  return 0;
}


<|start_filename|>codeforces/cf1526B_i_hate_1111.hs<|end_filename|>
-- user: nel_tu_
-- path: https://codeforces.com/contest/1526/problem/B
-- tags: math

import Data.Bool ( bool )

solve :: Int -> Bool
solve n = or [(n - k) `mod` 11 == 0 | k <- [0, 111 .. 1110], k <= n]

main = interact $ unlines . map (bool "NO" "YES" . solve . read) . tail . lines



<|start_filename|>codeforces/cf1514A_perfectly_imperfect_array.cpp<|end_filename|>
// Vicfred
// https://codeforces.com/contest/1514/problem/A
// math
#include <iostream>
#include <vector>

using namespace std;

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

while(t--) {
    int n;
    cin >> n;

    vector<long long int> a(n);

    for(auto &item : a) {
        cin >> item;
    }

    const int maxn = 10001;
    vector<long long int> square(maxn);

    for(int i = 1; i*i < maxn; ++i) {
        square[i*i] = 1;
    }

    bool found = false;
    for(const auto& n : a) {
        if(square[n] == 0) {
            found = true;
            break;
        }
    }

    if(found) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
}
}



<|start_filename|>codeforces/cf339A_helpful_maths.cpp<|end_filename|>
// Martin
// https://codeforces.com/contest/339/problem/A
// greedy, implementation, sorting

#include<iostream>
#include<algorithm>
#include<vector>

int main() {
    char c;
    std::vector<int> numbers;

    while (std::cin.get(c) && c != '\n') {
        if (c != '+') numbers.push_back((int)c - '0');
    }

    std::sort(begin(numbers), end(numbers));

    for (unsigned int i = 0; i < numbers.size(); i++)
        std::cout << numbers[i] << ((i < numbers.size() - 1) ? "+" : "");

    return 0;
}


<|start_filename|>codeforces/cf158A_next_round__.cpp<|end_filename|>
// https://codeforces.com/problemset/problem/158/A

#include<iostream>
#include<vector>

using namespace std;

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

    vector<int> scores;

    int value;
    for (int i = 0; i < n; i++) {
        cin >> value;
        scores.push_back(value);
    }

    int min = scores[k - 1];
    int sum = 0;
    for (int i = 0; i < n; i++) {
        int score = scores.at(i);
        if (score >= min && score > 0) sum += 1;
    }

    cout << sum << std::endl;
    return 0;
}


<|start_filename|>atcoder/abc149C_next_prime.lua<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc149/tasks/abc149_c
-- eratosthenes sieve

x = io.read("*n")

not_prime = {true}

for i = 2, 10 ^ 6 do
  if not_prime[i] == nil then
    if i >= x then
      print(i)
      break
    end
    cur = i * 2
    while cur < 10 ^ 6 do
      not_prime[cur] = true
      cur = cur + i
    end
  end
end


<|start_filename|>codeforces/cf1360B_honest_coach.hs<|end_filename|>
--- frederick99, 6/2020
--- https://codeforces.com/contest/1360/problem/B
--- greedy, sorting

import Control.Monad ( replicateM_ )


honestCoach :: [Int] -> Int
honestCoach = minSeparation . quickSort


quickSort :: Ord a => [a] -> [a]
quickSort [] = []
quickSort [x] = [x]
quickSort (pivot : rest) = quickSort l ++ pivot : quickSort r
    where l = filter (<=pivot) rest
          r = filter ( >pivot) rest


minSeparation :: (Ord a, Num a) => [a] -> a
minSeparation a = minimum $ zipWith subtract a (tail a)


readInput :: IO [Int]
readInput = getLine >> map read . words <$> getLine

main :: IO ()
main = do
    t <- read <$> getLine
    replicateM_ t (honestCoach <$> readInput >>= print)


<|start_filename|>atcoder/abc177A_dont_be_late.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc177/tasks/abc177_a
-- basic math

main = do
  li <- getLine
  let d:t:s:[] = map read $ words li
  putStrLn $ if t*s >= d then "Yes" else "No"


<|start_filename|>atcoder/abc178C_ubiquity.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc178/tasks/abc178_c
-- math, combinatorics

binpow a b mmod
  | b == 0    = 1
  | otherwise =
    if b `mod` 2 == 1 then
      res `mod` mmod * res `mod` mmod * a `mod` mmod
    else
      res `mod` mmod * res `mod` mmod
        where res = binpow a (b `div` 2) mmod

main = do
  li <- getLine
  let n = read li :: Integer
  let mmod = 10^9+7
  print $ ((\x -> (x + mmod) `mod` mmod) :: Integer -> Integer)
    $ (binpow 10 n mmod) - ((*2) $ binpow 9 n mmod) + (binpow 8 n mmod)


<|start_filename|>atcoder/abc081A_placing_marbles.lua<|end_filename|>
-- Vicfred
-- https://atcoder.jp/contests/abc081/tasks/abc081_a
-- implementation

s = io.read()
ans = 0
for i = 1, 3 do
    if s:sub(i,i) == '1' then
        ans = ans + 1
    end
end
print(ans)


<|start_filename|>atcoder/abc122A_double_helix_.lisp<|end_filename|>
; uninhm
; https://atcoder.jp/contests/abc122/tasks/abc122_a
; implementation

(

let
  ((b (read)))

(write-line (
  cond
    ((string-equal b "A") "T")
    ((string-equal b "T") "A")
    ((string-equal b "C") "G")
    ((string-equal b "G") "C")
))

)


<|start_filename|>codeforces/cf71A_way_too_long_words.hs<|end_filename|>
-- Vicfred
-- https://codeforces.com/problemset/problem/71/A
-- implementation
transform :: String -> String
transform s
    | (length s <= 10) = s
    | otherwise = ([head s] ++ show (length s - 2) ++ [last s])

main :: IO ()
main =  do
    w <- getLine
    words <- getContents
    putStrLn . unlines . map transform . lines $ words



<|start_filename|>atcoder/abc179A_plural_form.lua<|end_filename|>
-- Vicfred
-- https://atcoder.jp/contests/abc179/tasks/abc179_a
-- string manipulation

s = io.read()
if s:sub(#s, #s) == "s" then
    print(s .. "es")
else
    print(s .. "s")
end



<|start_filename|>kattis/monk.cpp<|end_filename|>
// Vicfred
// https://open.kattis.com/problems/monk
// binary search
#include <iostream>
#include <vector>
#include <utility>
#include <cmath>
#include <iomanip>

using namespace std;

int a, d;
vector<pair<double,double>> ascent;
vector<pair<double,double>> descent;
double dist;

bool monk(double time);

int main() {
    cout << fixed << setprecision(6);
    cin >> a >> d;
    dist = 0.0;

    for(int i = 0; i < a; i++) {
        int h, t;
        cin >> h >> t;
        ascent.push_back(make_pair(h, t));
        dist += h;
    }

    //cout << "distancia total " << dist << endl;

    for(int i = 0; i < d; i++) {
        int h, t;
        cin >> h >> t;
        descent.push_back(make_pair(h, t));
    }

    //cout << "=======" << endl;
    //for(auto item: ascent) {
    //    cout << item.first << " " << item.second << endl;
    //}
    //cout << "=======" << endl;
    //for(auto item: descent) {
    //    cout << item.first << " " << item.second << endl;
    //}
    //cout << "=======" << endl;

    double L, R, mid;
    L = 0.0;
    R = 1000000000.0;
    mid = 0.0;
    for(int i = 0; i < 1000; i++) {
        mid = L + (R-L)/2.0;
        //cout << "~~~~~~~probando " << mid << endl;
        if(monk(mid)) {
            //cout << mid << " es valida" << endl;
            R = mid;
        }
        else {
            //cout << mid << " NO es valida" << endl;
            L = mid;
        }
    }

    cout << mid << endl;

    return 0;
}

bool monk(double time) {
    double monk_up = 0.0;
    double monk_down = 0.0;

    double uptime = time;

    for(int i = 0; i < a; i++) {
        if(uptime <= 0.0) break;
        double D = ascent[i].first;
        double T = ascent[i].second;
        double velocity = D/T;
        //cout << "distancia: " << d << endl;
        //cout << "tiempo: " << d << endl;
        //cout << "velocidad: " << d << endl;
        if(T > uptime) {
            monk_down += velocity*uptime;
            uptime = 0.0;
            break;
        }
        monk_down += D;
        uptime -= T;
    }

    //cout << "subi " << monk_up << endl;

    uptime = time;

    for(int i = 0; i < d; i++) {
        if(uptime <= 0.0) break;
        double D = descent[i].first;
        double T = descent[i].second;
        double velocity = D/T;
        //cout << "distancia: " << d << endl;
        //cout << "tiempo: " << d << endl;
        //cout << "velocidad: " << d << endl;
        if(T > uptime) {
            monk_down += velocity*uptime;
            uptime = 0.0;
            break;
        }
        monk_down += D;
        uptime -= T;
    }

    //cout << "baje " << monk_down << endl;

    double total = monk_up + monk_down;

    //cout << "total " << total << endl;

    if(total >= dist)
        return true;

    return false;
}



<|start_filename|>atcoder/abc204A_rock_paper_scissors.lisp<|end_filename|>
;; uninhm
;; https://atcoder.jp/contests/abc204/tasks/abc204_a
;; implementation

(let ((x (read))
      (y (read)))
  (if (= x y)
    (write x)
    (write (- 3 x y))))


<|start_filename|>atcoder/arc108A_sum_and_product.cpp<|end_filename|>
// uninhm
// https://atcoder.jp/contests/arc108/tasks/arc108_a
// math

#include<iostream>

using namespace std;

int main() {
  long s, p;
  cin >> s >> p;

  for(long n = 1; n*n <= p; ++n) {
    if(n* (s - n) == p) {
      cout << "Yes" << endl;
      return 0;
    }
  }

  cout << "No" << endl;
}


<|start_filename|>atcoder/abc135A_harmony_.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc135/tasks/abc135_a
-- basic math

solve [a, b] = 
	if (a + b) `mod` 2 == 0 then
		show $ (a + b) `div` 2
	else
		"IMPOSSIBLE"

main = interact $ solve . map read . words


<|start_filename|>kickstart/allocation.cpp<|end_filename|>
// Vicfred
// https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ffc7/00000000001d3f56
// greedy
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main() {
    long long int t;
    cin >> t;

    for(int kase = 1; kase <= t; kase++) {
        long long int n, b;
        cin >> n >> b;

        vector<long long int> a(n);
        for(long long int &item: a)
            cin >> item;

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

        long long int ans = 0;
        while(true) {
            if(ans >= n) break;
            if(b < a[ans]) break;
            b -= a[ans++];
        }

        cout << "Case #" << kase << ": " << ans << endl;
    }
    return 0;
}



<|start_filename|>atcoder/abc124A_buttons.lisp<|end_filename|>
; uninhm
; https://atcoder.jp/contests/abc124/tasks/abc124_a
; implementation

(let ((a (read))
      (b (read)))

(write (+ (max a b) (max (- (max a b) 1) (min a b)))))


<|start_filename|>codeforces/cf1312C_adding_powers.cpp<|end_filename|>
// <NAME>
// https://codeforces.com/problemset/problem/1312/C
// greedy, math
#include <algorithm>
#include <iterator>
#include <string>
#include <iostream>
#include <vector>

using namespace std;

int main() {
    long long t;
    cin >> t;

    while(t--) {
        long long n, k;
        cin >> n >> k;

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

        string ans = "YES";
        while(any_of(a.begin(), a.end(), [](long long x) { return x != 0; })) {
            auto b = a;
            transform(b.begin(), b.end(), b.begin(), [=](long long x) { return x%k; });
            vector<long long> c;
            copy_if(b.begin(), b.end(), back_inserter(c), [](long long x) { return x != 0; });
            vector<long long> d = {1LL};
            if(c > d) {
                ans = "NO";
                break;
            }
            transform(a.begin(), a.end(), a.begin(), [=](long long x) { return x/k; });
        }
        cout << ans << endl;
    }
}



<|start_filename|>atcoder/abc077B_around_square.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc077/tasks/abc077_b
-- basic math

main = interact $ show . (^2) . floor . sqrt . read


<|start_filename|>atcoder/abc138A_red_or_not.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc138/tasks/abc138_a
-- implementation

main = do
  li <- getLine
  let a = read li
  li <- getLine
  putStrLn $
    if a < 3200 then
      "red"
    else
      li


<|start_filename|>codeforces/cf1493A_anti_knapsack.cpp<|end_filename|>
// Vicfred
// https://codeforces.com/contest/1493/problem/A
// greedy
#include <iostream>

using namespace std;

int main() {
    long T;
    cin >> T;

    long k, n;
while(T--) {
    cin >> n >> k;
    cout << n - k + k/2L << endl;
    for(int i = k + 1; i <= n; i++) {
        cout << i << " ";
    }
    for(int i = (k+1)/2; i < k; i++) {
        cout << i << " ";
    }
    cout << endl;
}
    return 0;
}



<|start_filename|>codeforces/cf1283B_candies_division.cpp<|end_filename|>
// Vicfred
// https://codeforces.com/contest/1283/problem/B
// math
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int t;
    cin >> t;
    while(t--) {
        int n, k;
        cin >> n >> k;
        cout << (n/k)*k + min(n%k,k/2) << endl;
    }
}



<|start_filename|>kattis/grandpabernie.cpp<|end_filename|>
// Vicfred
// https://open.kattis.com/problems/grandpabernie
// data structures, implementation
#include <algorithm>
#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>

using namespace std;

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

    unordered_map<string, vector<int>> visits;

    string s;
    int y;
    for(int i = 0; i < n; i++) {
        cin >> s >> y;
        visits[s].push_back(y);
    }

    int q;
    cin >> q;

    for(auto &item: visits) {
        sort(item.second.begin(), item.second.end());
    }

    /*
    for(auto item: visits) {
        cout << item.first << " ";
        for(auto year: item.second) {
            cout << year << " ";
        } cout << endl;
    }
    */

    for(int i = 0; i < q; i++) {
        cin >> s >> y;
        y -= 1;
        cout << visits[s][y] << endl;
    }

    return 0;
}



<|start_filename|>codeforces/cf1526A_mean_inequality_2.hs<|end_filename|>
-- user: nel_tu_
-- path: https://codeforces.com/contest/1526/problem/A
-- tags: implementation, observation

{-# LANGUAGE ViewPatterns #-}
 
import Data.List ( sort )
import Control.Monad ( replicateM_ )
 
solve :: Int -> [Int] -> [Int]
solve n (sort -> nums)
    = take n nums `zip` drop n nums >>= \(a, b) -> [a, b]
 
getInt = read <$> getLine
getInts = map read . words <$> getLine 
putInts = putStrLn . unwords . map show
 
main = do n <- getInt
          replicateM_ n (solve <$> getInt <*> getInts >>= putInts)



<|start_filename|>codeforces/cf617A_elephant.cpp<|end_filename|>
// Martin
// https://codeforces.com/contest/617/problem/A
// math

#include<iostream>

using namespace std;

int solve(int x) {
    if (x < 5) return 1;
    int result = (int)x / 5;
    if (x % 5 > 0) result++;
    return result;
}

int main() {
    int x;
    cin >> x;
    cout << solve(x) << endl;
    return 0;
}


<|start_filename|>codeforces/cf1A_theatre_square.hs<|end_filename|>
-- Vicfred
-- https://codeforces.com/problemset/problem/1/A
-- math
main :: IO ()
main = do
    [n, m, a] <- map read <$> words <$> getLine
    putStrLn $ show $ ceiling(n/a) * ceiling(m/a)



<|start_filename|>codeforces/cf1472A_cards_for_friends.cpp<|end_filename|>
// uninhm
// https://codeforces.com/contest/1472/problem/A
// simulation

#include<iostream>

using namespace std;

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

  for(int i = 0; i < t; ++i) {
    int w, h, n;
    cin >> w >> h >> n;

    int r = 1;
    while(w % 2 == 0) {
      w /= 2;
      r *= 2;
    }
    while(h % 2 == 0) {
      h /= 2;
      r *= 2;
    }

    cout << (r >= n ? "YES" : "NO") << "\n";
  }
}


<|start_filename|>atcoder/abc139A_tenki.hs<|end_filename|>
-- Vicfred
-- https://atcoder.jp/contests/abc139/tasks/abc139_a
-- implementation

predict :: String -> String -> Int
predict s t = length $ filter id $ zipWith (==) s t

main :: IO ()
main = predict <$> getLine <*> getLine >>= print



<|start_filename|>codeforces/cf1529B_sifid_and_strange_subsequences.hs<|end_filename|>
-- uninhm
-- https://codeforces.com/contest/1529/problem/B
-- greedy

import Data.List (sort)

odds (x:xs) = x : evens xs
odds [] = []

evens (_:xs) = odds xs
evens [] = []

(.>) = flip (.)
infixl 8 .>

firstdiff [x] = x
firstdiff (x:y:_) = y - x

solve l = go (length l) (firstdiff $ map snd l) l where
  go n mindiff (x':y':xs)
    | y > 0 && y <= mindiff = fst y'
    | y > 0 = fst x'
    | otherwise = go n (min mindiff (y-x)) (y':xs)
      where
        y = snd y'
        x = snd x'

  go n mindiff [x] = n

main = interact $ lines
  .> tail
  .> evens
  .> map (show . solve . zip [1..] . sort . map read . words)
  .> unlines


<|start_filename|>codeforces/cf1529A_eashag_loves_big_arrays.hs<|end_filename|>
-- uninhm
-- https://codeforces.com/contest/1529/problem/A
-- greedy

evens (x:xs) = x:odds xs
evens _ = []

odds (_:xs) = evens xs
odds _ = []

solution :: [Int] -> String
solution a =
  show $ length a - (length . filter (== minimum a)) a

main = interact $ unlines . map (solution . map read . words) . odds . tail . lines


<|start_filename|>codeforces/cf1487A_arena.cpp<|end_filename|>
// Martin
// https://codeforces.com/contest/1487/problem/A
// implementation, sorting

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

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

    while (t--) {
        cin >> n;
        vector<int> values(n);
        for (auto& it : values) cin >> it;

        sort(values.begin(), values.end(), [] (const int& a, const int& b) { return a > b; });  // reverse sort

        int answer {0};
        int last = values.back();
        for (unsigned int i = 0; i < values.size() - 1; i++) {
            if (values[i] > last) answer++;
        }
        cout << answer << endl;
    }
    return 0;
}


<|start_filename|>atcoder/abc164B_battle.cpp<|end_filename|>
// https://atcoder.jp/contests/abc164/tasks/abc164_b
#include<iostream>

int main() {
    int a_health, a_strenght, b_health, b_strenght;
    std::cin >> a_health >> a_strenght >> b_health >> b_strenght;

    int i = 2;
    while (a_health > 0 && b_health > 0) {
        if (i % 2 == 0) b_health -= a_strenght;
        else a_health -= b_strenght;

        i++;
    }

    if (a_health < 1) std::cout << "No";
    else std::cout << "Yes";

    return 0;
}


<|start_filename|>atcoder/abc125B_resale.lua<|end_filename|>
-- Vicfred
-- https://atcoder.jp/contests/abc125/tasks/abc125_b
-- greedy
n = io.read("*n")
v, c = {}, {}
for i = 1, n do v[i] = io.read("*n") end
for i = 1, n do c[i] = io.read("*n") end
ans = 0
for i = 1, n do
    if(c[i] < v[i]) then
        ans = ans + v[i] - c[i]
    end
end
print(ans)



<|start_filename|>spoj/HELLO.asm<|end_filename|>
; uninhm
; https://www.spoj.com/problems/HELLO/
; implementation

section .text
  global _start

_start:
  mov eax,4
  mov ebx,1
  mov ecx,msg
  mov edx,len
  int 0x80

  mov eax,1
  xor ebx,ebx
  int 0x80

section .data
  msg db "Hello World!", 0xa
  len equ $-msg


<|start_filename|>codeforces/cf1550A_find_the_array.cpp<|end_filename|>
// Vicfred
// https://codeforces.com/contest/1550/problem/A
// greedy
#include <iostream>

using namespace std;

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

while(t--) {
    int s;

    cin >> s;

    int ans = 1;

    while(ans * ans < s) {
        ++ans;
    }

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


<|start_filename|>codeforces/cf1521A_nastia_and_nearly_good_numbers.hs<|end_filename|>
-- user: nel_tu_
-- path: https://codeforces.com/contest/1521/problem/A
-- tags: math

solve [_, 1] = Nothing
solve [a, b] = Just [a, a*b, a*b + a]


input = map (map read . words) . tail . lines
output = maybe "NO" $ ("YES\n" ++) . unwords . map show

main = interact $ unlines . map (output . solve) . input



<|start_filename|>codeforces/cf1501B_napoleon_cake.cpp<|end_filename|>
// Vicfred
// https://codeforces.com/contest/1501/problem/B
// implementation, greedy
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main() {
    long t;
    cin >> t;
while(t--) {
    long n;
    cin >> n;
    
    vector<long> a(n);
    for(auto& item: a) {
        cin >> item;
    }

    vector<long> cakes(n);

    long cream = a[n - 1];
    for(long i = n - 1; i >= 0; i--) {
        cream = max(cream, a[i]);
        //cout << "cake: " << i << endl;
        //cout << "cream: " << cream << endl;
        if(cream) {
            cakes[i] = 1;
            cream -= 1;
        }
    }

    for(int i = 0; i < n; ++i)
        cout << cakes[i] << " ";
    cout << endl;
}
}



<|start_filename|>codeforces/cf1407B_big_vova.cpp<|end_filename|>
// Vicfred
// https://codeforces.com/contest/1407/problem/B
// math, implementation
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

using namespace std;

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

    while(t--) {
        int n;
        cin >> n;

        vector<int> a(n);
        for(auto &item: a)
            cin >> item;

        sort(a.begin(), a.end(), greater<int>());

        int current = a.front();
        vector<int> ans = {current};
        a.erase(a.begin());

        int GCD = current;
        while(!a.empty()) {
            int maxima = 0;
            current = ans.back();
            //cout << "current: " << current << endl;
            //cout << "CURRENT GCD: " << GCD << endl;
            for(auto item: a) {
                if(gcd(GCD, item) > maxima) {
                    maxima = gcd(GCD, item);
                }
            }
            //cout << "maxima: " << maxima << endl;
            GCD = gcd(GCD,maxima);
            for(auto iter = a.begin(); iter != a.end();) {
                if(gcd(GCD, *iter) == maxima) {
                    //cout << "found " << *iter << endl;
                    ans.push_back(*iter);
                    a.erase(iter);
                    break;
                } else {
                    ++iter;
                }
            }
        }
        
        for(auto item: ans)
            cout << item << " ";
        cout << endl;
    }

    return 0;
}



<|start_filename|>atcoder/abc161D_lunlun_number.cpp<|end_filename|>
// Vicfred
// https://atcoder.jp/contests/abc161/tasks/abc161_d
// dfs
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>

using namespace std;

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

    queue<long long> q;
    
    for(long long i = 1LL; i <= 9LL; i++)
        q.push(i);

    set<long long> lunlun;
    map<long long, int> visited;

    while(!q.empty()) {
        long long item = q.front();
        q.pop();

        if(lunlun.size() > k-1)
            break;

        if(visited.count(item) > 0)
            continue;

        visited[item] = 1;
        lunlun.insert(item);

        if(item%10LL != 0LL)
            q.push(item*10LL+item%10LL-1LL);
        q.push(item*10LL+item%10LL);
        if(item%10LL != 9LL)
            q.push(item*10LL+item%10LL+1LL);
    }

    cout << *(--lunlun.end()) << endl;
}



<|start_filename|>atcoder/abc208C_fair_candy_distribution.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc208/tasks/abc208_c
-- implementation

import Data.List (sort)

getInts :: IO [Int]
getInts = map read . words <$> getLine

solve n k a =
  flip map a $ \i ->
    if i < x then
      y + 1
    else
      y
    where x = sort a !! mod k n
          y = k `div` n

main = do
  [n, k] <- getInts
  a <- getInts
  putStr . unlines . map show $ solve n k a


<|start_filename|>codeforces/cf1195C_basketball_exercise.cpp<|end_filename|>
// Vicfred
// https://codeforces.com/problemset/problem/1195/C
// dynamic programming

#include <iostream>
#include <vector>

using namespace std;

int main() {
    const int MAXN = 100005;
    int n;
    cin >> n;

    vector<long long int> a(n);
    vector<long long int> b(n);

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

    vector<vector<long long int>> dp(MAXN,vector<long long int>(5));

    dp[0][1] = a[0];
    dp[0][2] = b[0];

    for(int i = 1; i < n; i++) {
        dp[i][1] = max(dp[i-1][2]+a[i],max(dp[i-1][3]+a[i],a[i]));
        dp[i][3] = max(dp[i-1][1],dp[i-1][2]);
        dp[i][2] = max(dp[i-1][1]+b[i],max(dp[i-1][3]+b[i],b[i]));
    }

    cout << max(dp[n-1][1],max(dp[n-1][2],dp[n-1][3])) << endl;

    return 0;
}



<|start_filename|>atcoder/abc168C_colon.cpp<|end_filename|>
// uninhm & Vicfred & Glum
// https://atcoder.jp/contests/abc168/tasks/abc168_c
// math
#include <ios>
#include <iostream>
#include <cmath>
#include <math.h>
#include <iomanip>

using namespace std;

int main() {
    cout << fixed << showpoint;
    cout << setprecision(23);

    long double a, b, h, m;

    cin >> a >> b >> h >> m;

    long double x = M_PI/6;
    long double y = M_PI/30;
    long double z = x/60;
    long double C = abs(x*h + z*m - y*m);
    /* x = factor para las horas, pues 5*pi/30 es una hora
     * y = factor para los minutos, 2*pi/60 = pi/30
     * */

    cout << sqrt(a*a+b*b-2.0L*a*b*cos(C)) << endl;

    return 0;
}



<|start_filename|>atcoder/abc217C_inverse_of_permutation.c<|end_filename|>
// uninhm
// https://atcoder.jp/contests/abc217/tasks/abc217_a
// implementation

#include <stdio.h>

int main ()
{
  int n;
  scanf ("%d\n", &n);
  int q[n];
  for (int i = 1; i <= n; ++i)
    {
      int p_i;
      scanf ("%d", &p_i);
      q[p_i-1] = i;
    }

  for (int i = 0; i < n; ++i)
    printf ("%d ", q[i]);
  putchar ('\n');
}


<|start_filename|>codeforces/cf650A_watchmen.cpp<|end_filename|>
// Vicfred
// https://codeforces.com/problemset/problem/650/A
// math, set
#include <iostream>
#include <vector>
#include <unordered_map>
#include <map>
#include <utility>

using namespace std;

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

    vector<long long int> point(2);
    unordered_map<long long int, long long int> first;
    unordered_map<long long int, long long int> second;
    map<pair<int,int>, long long int> points;

    for(int i = 0; i < n; ++i) {
        cin >> point[0] >> point[1];
        first[point[0]] += 1;
        second[point[1]] += 1;
        points[make_pair(point[0], point[1])] += 1;
    }

    long long int ans = 0LL;

    for(auto item: first) {
        long long int i = item.second;
        ans += i*(i-1LL)/2LL;
    }

    for(auto item: second) {
        long long int i = item.second;
        ans += i*(i-1LL)/2LL;
    }

    for(auto item: points) {
        long long int i = item.second;
        ans -= i*(i-1LL)/2LL;
    }

    cout << ans << endl;

    return 0;
}


<|start_filename|>atcoder/abc191A_vanishing_pitch.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc191/tasks/abc191_a
-- basic math

import Data.Bool (bool)

(.>) = flip (.)
infixl 8 .>

main = interact $ words .> map read .> \[v, t, s, d] ->
  bool "No" "Yes" $ d < v*t || v*s < d


<|start_filename|>codeforces/cf1422B_nice_matrix.cpp<|end_filename|>
// Vicfred
// https://codeforces.com/contest/1422/problem/B
// greedy
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

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

    int n, m;
    while(t--) {
        cin >> n >> m;
        vector<vector<long long>> a(n, vector<long long>(m));

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

        vector<long long> x(3);
        long long ans = 0LL;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                x[0] = a[i][j];
                x[1] = a[i][m-j-1];
                x[2] = a[n-i-1][j];

                sort(begin(x), end(x));

                ans += abs(a[i][j] - x[1]);
                ans += abs(a[i][m-j-1] - x[1]);
                ans += abs(a[n-i-1][j] - x[1]);

                a[i][j] = x[1];
                a[i][m-j-1] = x[1];
                a[n-i-1][j] = x[1];
            }
        }

        cout << ans << endl;
    }

    return 0;
}



<|start_filename|>atcoder/abc133A_t_or_t_.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc133/tasks/abc133_a
-- basic math

solve [n, a, b] = min (n * a) b

main = interact $ show . solve . map read . words


<|start_filename|>atcoder/abc143A_curtain_.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc143/tasks/abc143_a
-- basic math

solve [a, b] = max 0 $ a - 2 * b

main = interact $ show . solve . map read . words


<|start_filename|>codeforces/abc151A_next_alphabet.hs<|end_filename|>
-- Vicfred
-- https://atcoder.jp/contests/abc151/tasks/abc151_a
-- implementation
main :: IO ()
main = do
    c <- getChar
    putChar $ toEnum $ (fromEnum c) + 1



<|start_filename|>atcoder/abc190B_magic_3.hs<|end_filename|>
-- user: nel_tu_
-- path: https://atcoder.jp/contests/abc190/tasks/abc190_b
-- tags: implementation

import Data.Bool ( bool )

solve ([_, s, d] : spells) = any effective spells
    where effective [x, y] = x < s && y > d

input :: String -> [[Int]]
input = map (map read . words) . lines

main = interact $ bool "No" "Yes" . solve . input



<|start_filename|>atcoder/abc208B_factorial_yen_coin.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc208/tasks/abc208_b
-- implementation, recursion

factorial 0 = 1
factorial n = n * factorial (n - 1)

solve 1 p = p
solve n p =
  p `div` f + solve (n-1) (p `mod` f)
    where f = factorial n

main = getLine >>= print . solve 10 . read


<|start_filename|>codeforces/cf1422A_fence.cpp<|end_filename|>
// Vicfred
// https://codeforces.com/contest/1422/problem/A
// math
#include <algorithm>
#include <iostream>

using namespace std;

int main() {
    long t;
    cin >> t;
    
    while(t--) {
        long a, b, c, d;
        cin >> a >> b >> c;

        d = max(a,max(b,c));

        cout << d << endl;
    }

    return 0;
}



<|start_filename|>codeforces/cf977A_wrong_substraction.cpp<|end_filename|>
// Martin
// https://codeforces.com/contest/977/problem/A
// implementation

#include<iostream>
#include<string>

int main() {
    std::string n;
    int k, last;
    std::cin >> n >> k;

    while (k--) {
        last = std::stoi(&n.back());  // str.back returns a reference.
        n.pop_back();  // Remove last digit (assuming last digit is 0).
        if (last != 0) {
            n = n + std::to_string(last - 1);  // recover last digit with Tanya rules.
        }
    }
    std::cout << n;
    return 0;
}


<|start_filename|>atcoder/abc212A_alloy.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc212/tasks/abc212_a
-- implementation

solve [a, b]
  | a == 0    = "Silver"
  | b == 0    = "Gold"
  | otherwise = "Alloy"

main = getLine >>= putStrLn . solve . map read . words


<|start_filename|>atcoder/abc143A_curtain.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc143/tasks/abc143_a
-- basic math

main = do
  li <- getLine
  let a:b:[] = map read $ words li
  putStrLn.show $
    max 0 $ a - 2 * b


<|start_filename|>atcoder/abc172C_tsundoku.lua<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc172/tasks/abc172_c
-- greedy

N, M, K = io.read("*n","*n","*n")
A = {}; for i = 1, N do A[i] = io.read("*n") end
B = {}; for i = 1, M do B[i] = io.read("*n") end

a = {}; a[0] = 0
for i = 1, N do a[i] = a[i-1] + A[i] end

b = {}; b[0] = 0
for i = 1, M do b[i] = b[i-1] + B[i] end

ans, j = 0, M
for i = 0, N do
  if a[i] > K then break end
  while b[j] > K - a[i] do j = j - 1 end
  ans = math.max(ans, i + j)
end

print(ans)


<|start_filename|>codeforces/cf734A_anton_and_danik.cpp<|end_filename|>
// Martin
// https://codeforces.com/contest/734/problem/A
// implementation, strings

#include<iostream>
#include<algorithm>
#include<string>

using namespace std;

int main() {
    int n;
    string wins;
    cin >> n >> wins;
    
    int a_wins = count(wins.begin(), wins.end(), 'A');
    int d_wins = count(wins.begin(), wins.end(), 'D');

    if (a_wins > d_wins) cout << "Anton";
    else if (d_wins > a_wins) cout << "Danik";
    else cout << "Friendship";

    return 0;
}


<|start_filename|>codeforces/cf467A_george_and_accommodation.cpp<|end_filename|>
// Martin
// https://codeforces.com/contest/467/problem/A
// implementation

#include<iostream>

int main() {
    int n, p, q, count {0};
    std::cin >> n;
    while(n--) {
        std::cin >> p >> q;
        if (q - p >= 2) count++;
    }
    std::cout << count;
    return 0;
}


<|start_filename|>codeforces/cf1348B_phoenix_and_beauty.cpp<|end_filename|>
// Vicfred
// https://codeforces.com/problemset/problem/1348/B
// two pointers, greedy

#include <iostream>
#include <set>

using namespace std;

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

    for(int kase = 1; kase <= t; ++kase) {
        int n, k;
        cin >> n >> k;

        set<int> a;

        for(int i = 0; i < n; ++i) {
            int ins;
            cin >> ins;
            a.insert(ins);
        }

        if(a.size() > k) {
            cout << "-1" << endl;
            continue;
        }

        cout << n*k << endl;

        for(int i = 0; i < n; ++i) {
            for(auto item: a) {
                cout << item << " ";
            }

            for(int j = 0; j < (k-a.size()); ++j) {
                cout << "1 ";
            }
        } cout << endl;
    }
}



<|start_filename|>cses/dice_combinations.cpp<|end_filename|>
// Vicfred
// https://cses.fi/problemset/task/1633
// dynamic programming
#include <iostream>
#include <vector>

using namespace std;

int main() {
    const int mod = 1e9 + 7;
    const int maxn = 1e6 + 1;

    vector<int> dp(maxn, 0);
    dp[0] = 1;

    for(int i = 1; i <= maxn - 1; ++i) {
        for(int dice = 1; dice <= 6; ++dice) {
            if(i - dice >= 0) {
                dp[i] += dp[i - dice];
                dp[i] %= mod;
            }
        }
    }

    int n;
    cin >> n;

    cout << dp[n] << endl;

    return 0;
}



<|start_filename|>codeforces/cf231A_team_.c<|end_filename|>
// https://codeforces.com/problemset/problem/231/A
#include<stdio.h>

int main() {
    int n;
    int petya = 0, vasya = 0, tonya = 0;
    int amount = 0;

    scanf("%d", &n);

    while (n > 0) {
        scanf("%d %d %d", &petya, &vasya, &tonya);
        if (petya + vasya + tonya > 1)
            amount += 1;
        n--;
    }
    printf("%d\n", amount);
    return 0;
}


<|start_filename|>codeforces/cf1536A_omkar_and_bad_story.hs<|end_filename|>
-- uninhm
-- https://codeforces.com/contest/1536/problem/A
-- greedy

import Control.Monad (replicateM_)

getInt = read <$> getLine
getInts = map read . words <$> getLine

solution = unlines [ "YES"
                   , "101"
                   , unwords (map show [0..100])
                   ]

main = do
  t <- getInt
  replicateM_ t $ do
    n <- getInt
    a <- getInts
    if any (< 0) a then
      putStrLn "NO"
    else
      putStr solution


<|start_filename|>kattis/orders.cpp<|end_filename|>
// Vicfred
// https://open.kattis.com/problems/orders
// dynamic programming
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> c(n);
    for(int i = 0; i < n; i++)
        cin >> c[i];

    vector<int> dp(30001, -1);
    dp[0] = 0;

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < dp.size() - c[i]; j++) {
            if(dp[j] != -1) {
                if(dp[j] == n or dp[j + c[i]] != -1)
                    dp[j + c[i]] = n;
                else
                    dp[j + c[i]] = i;
            }
        }
    }

    int m;
    cin >> m;
    int d;
    for(int i = 0; i < m; i++) {
        cin >> d;
        if(dp[d] == n)
            cout << "Ambiguous" << endl;
        else if(dp[d] == -1)
            cout << "Impossible" << endl;
        else {
            vector<int> ans;
            while(d > 0) {
                ans.push_back(dp[d] + 1);
                d -= c[dp[d]];
            }
            reverse(ans.begin(), ans.end());
            for(int item: ans)
                cout << item << " ";
            cout << endl;
        }
    }

    return 0;
}



<|start_filename|>codeforces/cf1537A_arithmetic_array.hs<|end_filename|>
-- uninhm
-- https://codeforces.com/contest/1537/problem/A
-- greedy

import Control.Monad (replicateM_)

getInt = read <$> getLine
getInts = map read . words <$> getLine

main = do
  n <- getInt
  replicateM_ n $ do
    k <- getInt
    s <- sum <$> getInts
    if s < k then
      print 1
    else
      print $ s - k


<|start_filename|>atcoder/abc207A_repression.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc207/tasks/abc207_a
-- implementation

solve l = sum l - minimum l
main = interact $ show . solve . map read . words


<|start_filename|>codeforces/cf71A_way_too_long_words___.cpp<|end_filename|>
// https://codeforces.com/problemset/problem/71/A
#include<iostream>
#include<string>

int solve(std::string word) {
    return (word.end() - 1) - (word.begin() + 1);
}

int main() {
    int n;
    std::cin >> n;
    std::string current;
    while (n > 0) {
        std::cin >> current;
        if (current.length() > 10) {
            std::cout << current.at(0) << solve(current) << current.back() << std::endl;
        } else {
            std::cout << current << std::endl;
        }
        n--;
    }
    return 0;
}


<|start_filename|>atcoder/abc132A_fifty_fifty.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc132/tasks/abc132_a
-- implementation

main = do
  s <- getLine
  let a:b:c:d:[] = s
  putStrLn $
    if (a /= b || a /= c || a /= d) && (
       a == b && c == d ||
       a == c && b == d ||
       a == d && b == c ) then
      "Yes"
    else
      "No"



<|start_filename|>kattis/iwannabe.cpp<|end_filename|>
// Vicfred
// https://open.kattis.com/problems/iwannabe
// sorting, data structures, implementation
#include <algorithm>
#include <iostream>
#include <vector>
#include <set>
#include <tuple>

using namespace std;

typedef tuple<long,long,long> pokemon;

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

    vector<pokemon> pokemons;
    set<pokemon> team;

    long a, d, h;
    for(int i = 0; i < n; i++) {
        cin >> a >> d >> h;
        pokemons.push_back({a, d, h});
    }

    sort(pokemons.begin(), pokemons.end(), [](pokemon a, pokemon b) {
            return get<0>(a) > get<0>(b);
    });

    /*
    for(auto a: pokemons) {
        cout << get<0>(a) << " " << get<1>(a) << " " << get<2>(a) << endl;
    }
    */

    for(int i = 0; i < k; i++)
        team.insert(pokemons[i]);

    sort(pokemons.begin(), pokemons.end(), [](pokemon a, pokemon b) {
            return get<1>(a) > get<1>(b);
    });

    /*
    for(auto a: pokemons) {
        cout << get<0>(a) << " " << get<1>(a) << " " << get<2>(a) << endl;
    }
    */

    for(int i = 0; i < k; i++)
        team.insert(pokemons[i]);

    sort(pokemons.begin(), pokemons.end(), [](pokemon a, pokemon b) {
            return get<2>(a) > get<2>(b);
    });

    /*
    for(auto a: pokemons) {
        cout << get<0>(a) << " " << get<1>(a) << " " << get<2>(a) << endl;
    }
    */

    for(int i = 0; i < k; i++)
        team.insert(pokemons[i]);
    
    cout << team.size() << endl;

    return 0;
}



<|start_filename|>codeforces/cf1512B_almost_rectangle.cpp<|end_filename|>
// Vicfred
// https://codeforces.com/contest/1512/problem/B
// implementation, greedy
#include <iostream>
#include <string>
#include <tuple>
#include <vector>
#include <utility>

using namespace std;

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

while(t--) {
    int n;
    cin >> n;

    vector<string> grid(n);
    for(auto &row : grid) {
        cin >> row;
    }

    vector<pair<int,int>> positions;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            if(grid[i][j] == '*') {
                positions.push_back({i, j});
            }
        }
    }

    // same row
    if (positions[0].first == positions[1].first) {
        if(positions[0].first == 0) {
            positions.push_back({1, positions[0].second});
            positions.push_back({1, positions[1].second});
        } else {
            positions.push_back({positions[0].first - 1, positions[0].second});
            positions.push_back({positions[1].first - 1, positions[1].second});
        }
    }

    // same column
    else if (positions[0].second == positions[1].second) {
        if(positions[0].second == 0) {
            positions.push_back({positions[0].first, 1});
            positions.push_back({positions[1].first, 1});
        } else {
            positions.push_back({positions[0].first, positions[0].second - 1});
            positions.push_back({positions[1].first, positions[1].second - 1});
        }
    }

    // different row and different column
    else {
        int x, y, i, j;
        tie(x, y) = positions[0];
        tie(i, j) = positions[1];
        positions.push_back({x,j});
        positions.push_back({i,y});
    }

    for(const auto& [x, y] : positions) {
        grid[x][y] = '*';
    }

    for(const auto& row : grid) {
        cout << row << endl;
    }
}
    return 0;
}



<|start_filename|>atcoder/abc082A_round_up_the_mean.lua<|end_filename|>
-- Vicfred
-- https://atcoder.jp/contests/abc082/tasks/abc082_a
-- simple math

a, b = io.read("*n", "*n")
print(math.floor((a + b) / 2 + 1 / 2))


<|start_filename|>atcoder/abc171C_one_quadrillion_and_one_dalmatians.hs<|end_filename|>
-- frederick99, algorithm by vicfred
-- https://atcoder.jp/contests/abc171/tasks/abc171_c
-- math

import Data.Char ( chr )
 
solve :: Int -> String
solve 0 = ""
solve n = chr (97 + r) : solve q
  where (q, r) = pred n `divMod` 26

main :: IO ()
main = putStrLn =<< reverse . solve . read <$> getLine



<|start_filename|>atcoder/ablC_connect_cities.cpp<|end_filename|>
// Vicfred
// https://atcoder.jp/contests/abl/tasks/abl_c
// graph, dsu, dfs, bfs
#include <iostream>
#include "dsu.hpp"

using namespace std;
using namespace atcoder;

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

    dsu uf(n);

    int a, b;
    for(int i = 0; i < m; i++) {
        cin >> a >> b;
        a -= 1;
        b -= 1;
        uf.merge(a, b);
    }

    auto cities = uf.groups();

    cout << cities.size() - 1 << endl;

    return 0;
}



<|start_filename|>codeforces/cf136A_presents.cpp<|end_filename|>
// Martin
// https://codeforces.com/contest/136/problem/A
// implementation

#include<iostream>

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

    int gifts[n];
    int friends[n];
    int tmp;

    for (int i = 0; i < n; i++) {
        std::cin >> tmp;
        gifts[i] = tmp - 1;
    }

    for (int i = 0; i < n; i++) friends[gifts[i]] = i;

    for (int i = 0; i < n; i++) {
        std::cout << (friends[i] + 1) << " ";
    }

    std::cout << std::endl;
    return 0;
}


<|start_filename|>atcoder/abc184C_super_ryuma.cpp<|end_filename|>
// Solution by Vicfred, implementation by uninhm
// https://atcoder.jp/contests/abc184/tasks/abc184_c
// greedy

#include<iostream>
#include<math.h>

using namespace std;

int main() {
  long r1, c1, r2, c2;
  cin >> r1 >> c1 >> r2 >> c2;

  if(r1 == r2 && c1 == c2) {
    cout << 0 << endl;
    return 0;
  }

  if(r1 + c1 == r2 + c2 ||
     r1 - c1 == r2 - c2 ||
     abs(r1 - r2) + abs(c1 - c2) <= 3) {
    cout << 1 << endl;
    return 0;
  }

  if((r1 + c1) %2 == (r2 + c2)%2) {
    cout << 2 << endl;
    return 0;
  }

  for(int i = -3; i <= 3; i++) {
    for(int j = -3; j <= 3; j++) {
      long x = r1 + i;
      long y = c1 + j;

      if(x + y == r2 + c2 ||
          x - y == r2 - c2 ||
          abs(x - r2) + abs(y - c2) <= 3) {
        cout << 2 << endl;
        return 0;
      }
    }
  }

  cout << 3 << endl;
}


<|start_filename|>codeforces/cf1360C_similar_pairs.hs<|end_filename|>
--- frederick99, 6/2020
--- https://codeforces.com/contest/1360/problem/C
--- implementation, sets

import           Control.Monad ( replicateM_ )
import qualified Data.Set as Set


similarPairs :: [Int] -> String
similarPairs s =
    let odds = length (filter odd s) in
    if even odds || any (seen . succ) s
        then "YES"
        else "NO"
    where seen = (`Set.member` Set.fromList s)


readInput :: IO [Int]
readInput = getLine >> map read . words <$> getLine

main :: IO ()
main = do
    t <- read <$> getLine
    replicateM_ t (similarPairs <$> readInput >>= putStrLn)


<|start_filename|>atcoder/abc165D_floor_function.cpp<|end_filename|>
// Vicfred
// https://atcoder.jp/contests/abc165/tasks/abc165_d
// math
#include <algorithm>
#include <iostream>

using namespace std;

int main() {
    long long a, b, n;
    cin >> a >> b >> n;

    cout << (a*min(b-1LL, n))/b << endl;

    return 0;
}



<|start_filename|>codeforces/cf59A_word_.cpp<|end_filename|>
// https://codeforces.com/problemset/problem/59/A
#include<iostream>
#include<string>

using namespace std;

void uppercase(string& str) {
    for (auto c : str)
        printf("%c", toupper(c));
}

void lowercase(string& str) {
    for (auto c : str)
        printf("%c", tolower(c));
}

int main() {
    string word;
    cin >> word;

    int lower_count = 0, upper_count = 0;
    for (auto c : word) {
        if (islower(c)) lower_count++;
        else upper_count++;
    }

    if (lower_count == upper_count || lower_count > upper_count)
        lowercase(word);
    else
        uppercase(word);

    printf("\n");

    return 0;
}


<|start_filename|>atcoder/abc191B_remote_it.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc191/tasks/abc191_b
-- implementation

getInts :: IO [Int]
getInts = map read . words <$> getLine

main = do
  [_, x] <- getInts
  putStrLn . unwords . map show . filter (/= x) =<< getInts


<|start_filename|>atcoder/abc138C_alchemist.cpp<|end_filename|>
// TsukiZombina
// https://atcoder.jp/contests/abc138/tasks/abc138_c
// sorting, greedy

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    int N;
    float number = 0, mix;
    std::cin >> N;
    std::vector<int> numbers(N);
    for(auto& x: numbers)
    {
        std::cin >> x;
    }

    std::sort(numbers.begin(), numbers.end());
     
    mix = numbers[0];
    for (const auto& number: numbers) {
        mix = (mix + number)/2;
    }
    std::cout << mix;
    return 0;
}


<|start_filename|>atcoder/abc210A_cabbages.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc210/tasks/abc210_a
-- basic math

solve [n, a, x, y]
  | n <= a = n*x
  | otherwise = a*x + (n-a)*y

main = interact $ show . solve . map read . words


<|start_filename|>atcoder/abc184A_determinant.cpp<|end_filename|>
// uninhm
// https://atcoder.jp/contests/abc184/tasks/abc184_a
// implementation

#include<iostream>

using namespace std;

int main() {
  int a, b, c, d;
  cin >> a >> b >> c >> d;

  cout << a*d - b*c << endl;
}


<|start_filename|>codeforces/cf791A_bear_and_bigger_brother.cpp<|end_filename|>
// Martin
// https://codeforces.com/contest/791/problem/A
// implementation

#include<iostream>

int main() {
    int a, b, years {0};
    std::cin >> a >> b;

    while (b >= a) {
        b *= 2, a *= 3;
        years++;
    }
    std::cout << years;
    return 0;
}


<|start_filename|>atcoder/abc178B_product_max_.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc178/tasks/abc178_b
-- math

import Data.Bits

bignum :: Int
bignum = shiftL 1 63

solve :: [Int] -> Int
solve [a, b, c, d] = foldl max (-bignum) [a * c, a * d, b * c, b * d]

main = interact $ show . solve . map read . words


<|start_filename|>codeforces/cf236A_boy_or_girl.cpp<|end_filename|>
// Martin
// https://codeforces.com/contest/236/problem/A
// implementation, brute force, set

#include<iostream>
#include<string>
#include<set>

using namespace std;

int main() {
    string username;
    cin >> username;

    set<char> s;
    for (auto c : username) s.insert(c);

    if (s.size() & 1) cout << "IGNORE HIM!" << endl;
    else cout << "CHAT WITH HER!" << endl;

    return 0;
}


<|start_filename|>atcoder/abc121A_white_cells.lisp<|end_filename|>
; uninhm
; https://atcoder.jp/contests/abc121/tasks/abc121_a
; math

(

let (
  (h (read))
  (w (read))
  (a (read))
  (b (read))
)

(write (
  * (- h a) (- w b)
))

)


<|start_filename|>atcoder/abc213A_bitwise_exclusive_or.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc213/tasks/abc213_a
-- implementation

import Data.Bits (xor)

listify f [a, b] = f a b

main = interact $ show . listify xor . map (read :: String -> Int) . words


<|start_filename|>codeforces/cf1499B_binary_removals.cpp<|end_filename|>
// Vicfred
// https://codeforces.com/blog/entry/88812
// greedy
#include <algorithm>
#include <iostream>

using namespace std;

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

while(t--) {
    string s;
    cin >> s;

    int i = s.find("11");
    int j = s.rfind("00");

    cout << (i != -1 && j != -1 && i < j ? "NO" : "YES") << endl;
}
    return 0;
}


<|start_filename|>atcoder/abc132A_fifty_fifty__.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc132/tasks/abc132_a
-- greedy

import Data.Set (fromList, size)
import Data.Bool (bool)

solve = bool "No" "Yes" . (==) 2 . size . fromList . init

main = interact solve



<|start_filename|>atcoder/abc214A_new_generation_abc.lisp<|end_filename|>
;; uninhm
;; https://atcoder.jp/contests/abc214/tasks/abc214_a
;; implementation

(setf n (read))
(write-line
  (cond ((<= n 125) "4")
        ((<= n 211) "6")
        (t          "8")))


<|start_filename|>atcoder/abc178C_ubiquity.lua<|end_filename|>
-- Vicfred
-- https://atcoder.jp/contests/abc178/tasks/abc178_c
-- math

function binpow(a, b, m)
    a = a % m
    res = 1
    while b > 0 do
        if (b % 2) == 1 then
            res = (res * a) % m
        end
        a = (a * a) % m
        b = b // 2
    end

    return res
end

mod = 1000000007

n = io.read("*n")

ans = binpow(10, n, mod) - binpow(9, n, mod) - binpow(9, n, mod) + binpow(8, n, mod)
ans = ans + mod
ans = ans % mod
print(ans)



<|start_filename|>atcoder/hhkb2020C_neq_min.cpp<|end_filename|>
// Vicfred
// https://atcoder.jp/contests/hhkb2020/tasks/hhkb2020_c
// set, ordered set, balanced tree, data structure
#include <iostream>
#include <set>

using namespace std;

int main() {
    const int maxn = 200000;

    set<int> numbers;
    for(int i = 0; i <= maxn; i++) {
        numbers.insert(i);
    }

    int n;
    cin >> n;

    int p;
    for(int i = 0; i < n; i++) {
        cin >> p;
        auto it = numbers.find(p);
        if(it != numbers.end())
            numbers.erase(it);
        cout << *numbers.begin() << endl;
    }
}



<|start_filename|>atcoder/abc139A_tenki_.hs<|end_filename|>
-- Vicfred
-- https://atcoder.jp/contests/abc139/tasks/abc139_a
-- implementation

main :: IO ()
main = do
    s <- getLine
    t <- getLine
    print $ foldl (\ count idx -> count + if s !! idx == t !! idx then 1 else 0) 0 [0..2]



<|start_filename|>atcoder/abc179C_axb+c.lua<|end_filename|>
-- Vicfred
-- https://atcoder.jp/contests/abc179/tasks/abc179_c
-- math, combinatorics
n = io.read("*n")

ans = 0

for a = 1, n-1 do
    ans = ans + (n - 1) // a
end

print(ans)



<|start_filename|>atcoder/abc147B_palindrome_philia.go<|end_filename|>
// <NAME>
// https://atcoder.jp/contests/abc147/tasks/abc147_b
// category: string manipulation

package main

import (
	"fmt"
)

func main() {
	var word string
	fmt.Scan(&word)
	palindromeHugger(word)
}

func palindromeHugger(word string) {
	var incidences int
	wordLenght := len(word) - 1

	for i, letter := range word {
		if letter != rune(word[wordLenght-i]) {
			incidences++
		}
	}

	fmt.Println(incidences / 2)
}


<|start_filename|>kattis/crackingrsa.cpp<|end_filename|>
// Vicfred
// https://open.kattis.com/problems/crackingrsa
// math
#include <iostream>

using namespace std;

int main() {
    const int MAXN = 1e6+10;
    long phi[MAXN];
    for(int i = 1; i <= MAXN; ++i)
        phi[i] = i;

    /*
    for(int i = 1; i < 20; i++)
        cout << phi[i] << " ";
    cout << endl;
    */

    for(int i = 2; i <= MAXN; ++i)
        if(phi[i] == i)
            for(int j = i; j <= MAXN; j += i)
                phi[j] = (phi[j]/i) * (i - 1);

    /*
    for(int i = 1; i < 20; i++)
        cout << phi[i] << " ";
    cout << endl;
    */

    int t;
    cin >> t;

    long n, e;
    while(t--) {
        cin >> n >> e;
        for(int d = 1; d < phi[n]; d++) {
            if((d*e)%phi[n] == 1) {
                cout << d << endl;
                break;
            }
        }
    }

    return 0;
}



<|start_filename|>atcoder/abc142A_odds_of_oddness_.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc142/tasks/abc142_a
-- basic probability

solve n = (/n).fromIntegral.floor $ (n + 1) / 2

main = interact $ show . solve . read


<|start_filename|>codeforces/cf1526A_mean_inequality.hs<|end_filename|>
-- uninhm
-- https://codeforces.com/contest/1526/problem/A
-- greedy

import Data.List (transpose, sort)

odds (x:xs) = x : evens xs
odds [] = []

evens (_:xs) = odds xs
evens [] = []

split a = [take l a, drop l a]
  where l = length a `div` 2

solve :: [Int] -> [Int]
solve = concat . transpose . split . sort

solveLine =
  unwords . map show . solve . map read . words

main = interact $ unlines . map solveLine . evens . tail . lines


<|start_filename|>codeforces/cf1303B_national_project.cpp<|end_filename|>
// Vicfred
// https://codeforces.com/problemset/problem/1303/B
// math
#include <iostream>
#include <cmath>

using namespace std;

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

    while(t--) {
        long long int n, g, b;
        cin >> n >> g >> b;

        long long int periods = (n+1LL)/2LL;
        long long int days = periods/g*(g+b);

        if(periods%g > 0LL) {
            days += periods%g;
        } else {
            days -= b;
        }

        cout << max(n, days) << endl;
    }

    return 0;
}



<|start_filename|>atcoder/abc184B_quizzes.cpp<|end_filename|>
// uninhm
// https://atcoder.jp/contests/abc184/tasks/abc184_b
// implementation, simulation

#include<iostream>
#include<string>

using namespace std;

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

  string s;
  cin >> s;

  for(char c: s)
    if(c == 'o')
      x++;
    else if(c == 'x' && x > 0)
      x--;

  cout << x << endl;
}


<|start_filename|>atcoder/abc135A_harmony.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc135/tasks/abc135_a
-- basic math

main = do
  li <- getLine
  let a:b:[] = map read $ words li
  putStrLn $
    if (a + b) `mod` 2 == 0 then
      show $ div (a + b) 2
    else
      "IMPOSSIBLE"


<|start_filename|>codeforces/cf1360F_spy_string.hs<|end_filename|>
--- frederick99, 6/2020
--- https://codeforces.com/contest/1360/problem/F
--- implementation, hamming distance

{-# LANGUAGE TupleSections #-}
import Control.Monad ( replicateM_ )


spyString :: Int -> [String] -> String
spyString m [] = replicate m '0'
spyString m (leader : members) =
    case filter isSpy candidates of
        (spy : _) -> spy
        _         -> "-1"
    where
        isSpy cand = all ((2 >) . hammingDistance cand) members
        candidates = gen `concatMap` map (`splitAt` leader) [0..m-1]
        gen (l, r) = ((l ++) . (: tail r)) `map` ['a'..'z']


hammingDistance :: String -> String -> Int
hammingDistance a b = sum $ zipWith ((fromEnum.) . (/=)) a b


readInput :: IO (Int, [String])
readInput = do
    [n, m] <- map read . words <$> getLine
    (m, ) <$> (sequence $ replicate n getLine)

main :: IO ()
main = do
    t <- read <$> getLine
    replicateM_ t (uncurry spyString <$> readInput >>= putStrLn)


<|start_filename|>atcoder/abc166F_three_variables_game.cpp<|end_filename|>
// Vicfred
// https://atcoder.jp/contests/abc166/tasks/abc166_f
// dfs
#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <stack>

using namespace std;

const unsigned long MAXN = 100005;

int n;
string S[MAXN];
bool visited[MAXN][10][10][10];
stack<char> st;
stack<char> answer;

bool dfs(int i, int a, int b, int c) {
    if(i == n) {
        while(!st.empty()) {
            answer.emplace(st.top());
            st.pop();
        }
        return true;
    }

    visited[i][a][b][c] = true;

    if(S[i] == "AB") {
        if(a+1 < 10 && b > 0 && !visited[i+1][a+1][b-1][c]) {
            st.emplace('A');
            if(dfs(i+1, a+1, b-1, c)) {
                return true;
            }
            st.pop();
        }
        if(b+1 < 10 && a > 0 && !visited[i+1][a-1][b+1][c]) {
            st.emplace('B');
            if(dfs(i+1, a-1, b+1, c)) {
                return true;
            }
            st.pop();
        }
    }
    else if(S[i] == "AC") {
        if(a+1 < 10 && c > 0 && !visited[i+1][a+1][b][c-1]) {
            st.emplace('A');
            if(dfs(i+1, a+1, b, c-1)) {
                return true;
            }
            st.pop();
        }
        if(c+1 < 10 && a > 0 && !visited[i+1][a-1][b][c+1]) {
            st.emplace('C');
            if(dfs(i+1, a-1, b, c+1)) {
                return true;
            }
            st.pop();
        }
    }
    else {
        // case BC
        if(b+1 < 10 && c > 0 && !visited[i+1][a][b+1][c-1]) {
            st.emplace('B');
            if(dfs(i+1, a, b+1, c-1)) {
                return true;
            }
            st.pop();
        }
        if(c+1 < 10 && b > 0 && !visited[i+1][a][b-1][c+1]) {
            st.emplace('C');
            if(dfs(i+1, a, b-1, c+1)) {
                return true;
            }
            st.pop();
        }
    }

    return false;
}

int main () {
    int a, b, c;
    cin >> n >> a >> b >> c;

    for(int i = 0; i < n; ++i)
        cin >> S[i];

    if(a > 0 and b > 0 and c > 0) {
        cout << "Yes" << endl;

        bool idx[3] = {true, true, true};
        for(int i = 0; i < n; i++) {
            if(S[i] == "AB") {
                cout <<  "AB"[idx[0]] << endl;
                idx[0] = !idx[0];
            }
            else if(S[i] == "BC") {
                cout <<  "BC"[idx[1]] << endl;
                idx[1] = !idx[1];
            }
            else {
                cout <<  "CA"[idx[2]] << endl;
                idx[2] = !idx[2];
            }
        }
    } else {
        if(dfs(0, min(a, 3), min(b, 3), min(c, 3))) {
            cout << "Yes" << endl;
            while(!answer.empty()) {
                cout << answer.top() << endl;
                answer.pop();
            }
        } else {
            cout << "No" << endl;
        }
    }

    return 0;
}



<|start_filename|>codeforces/cf1030A_in_search_of_an_easy_problem.cpp<|end_filename|>
// Martin
// https://codeforces.com/contest/1030/problem/A
// implementation

#include<iostream>

using namespace std;

int main() {
    int n, tmp;
    cin >> n;
    bool is_easy = true;
    while (n--) {
        cin >> tmp;
        if (tmp == 1) is_easy = false;
    }
    if (is_easy) cout << "EASY";
    else cout << "HARD";

    return 0;
}


<|start_filename|>atcoder/abc146A_cant_wait_for_holiday__.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc146/tasks/abc146_a
-- implementation

import Data.List (elemIndex)
import Data.Maybe (fromJust)

ans s = (+1).fromJust $ elemIndex s a
	where a = ["SAT", "FRI", "THU", "WED", "TUE", "MON", "SUN"]

main = interact $ show . ans . init


<|start_filename|>codeforces/cf977A_wrong_substraction_.cpp<|end_filename|>
// Martin
// https://codeforces.com/contest/1367/problem/A
// implementation

#include<iostream>

int substract(int value) {
    if (value % 10 != 0) {
        value -= 1;
    } else {
        value /= 10;
    }
    return value;
}

int main() {
    int n, k, last;
    std::cin >> n >> k;

    while (k--) {
        n = substract(n);
    }
    std::cout << n;
    return 0;
}


<|start_filename|>cses/minimizing_coins.cpp<|end_filename|>
// Vicfred
// https://cses.fi/problemset/task/1634
// dynamic programming
#include <iostream>
#include <vector>

using namespace std;

int main() {
    const int maxn = 1e6 + 1;
    const int INF = 1<<30;
    vector<int> dp(maxn, INF);

    int n, x;
    cin >> n >> x;

    dp[0] = 0;

    vector<int> coins(n);
    for(int &coin: coins) {
        cin >> coin;
        dp[coin] = 1;
    }

    for(int i = 1; i <= maxn - 1; ++i) {
        for(int &coin: coins) {
            if(i - coin >= 0) {
                dp[i] = min(dp[i], dp[i - coin] + 1);
            }
        }
    }

    if(dp[x] == INF)
        cout << -1 << endl;
    else
        cout << dp[x] << endl;

    return 0;
}



<|start_filename|>atcoder/abc146A_cant_wait_for_holiday.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc146/tasks/abc146_a
-- implementation

ans li | li == "SUN" = 7
       | li == "MON" = 6
       | li == "TUE" = 5
       | li == "WED" = 4
       | li == "THU" = 3
       | li == "FRI" = 2
       | otherwise   = 1


main = do
  li <- getLine
  putStrLn $ show $ ans li


<|start_filename|>cses/coin_combinations_ii.cpp<|end_filename|>
// Vicfred
// https://cses.fi/problemset/task/1635
// dynamic programming
#include <iostream>
#include <vector>

using namespace std;

int main() {
    const int mod = 1e9 + 7;
    const int maxn = 1e6 + 1;

    int n, x;
    cin >> n >> x;

    vector<vector<int>> dp(n + 1, vector<int>(maxn));
    dp[0][0] = 1;

    vector<int> coins(n);
    for(int &coin: coins) {
        cin >> coin;
    }

    for(int i = 1; i <= n; ++i) {
        for(int j = 0; j <= maxn - 1; ++j) {
            dp[i][j] = dp[i - 1][j];
            int value = j - coins[i - 1];
            if(value >= 0) {
                dp[i][j] += dp[i][value];
            }
            dp[i][j] %= mod;
        }
    }

    cout << dp[n][x] << endl;

    return 0;
}


<|start_filename|>kattis/islands.cpp<|end_filename|>
// Vicfred
// https://open.kattis.com/problems/islands
// brute force
#include <iostream>
#include <vector>

using namespace std;

int main() {
    long p;
    cin >> p;

    while(p--) {
        long k;
        cin >> k;

        vector<long> sequence(12);
        for(long i = 0; i < 12; i++) {
            cin >> sequence[i];
        }

        long islands = 0;
        for(int i = 1; i < 11; i++) {
            for(int j = i; j < 11; j++) {
                //cout << i << " " << j << endl;
                long minima = 1L << 60;
                for(int k = i; k <= j; k++) {
                    minima = min(minima, sequence[k]);
                }
                //cout << "minima: " << minima << endl;
                if(minima > sequence[i-1] and minima > sequence[j+1])
                    islands += 1;
            }
        }
        cout << k << " " << islands << endl;
    }

    return 0;
}



<|start_filename|>codeforces/cf507B_amr_and_pins.cpp<|end_filename|>
// Vicfred
// https://codeforces.com/problemset/problem/507/B
// math, greedy

#include <iostream>
#include <cmath>

using namespace std;

long double euclidean(long long int x, long long int y, long long int u, long long int v) {
    return sqrt((x-u)*(x-u) + (y-v)*(y-v));
}

int main() {
    long long int r, x, y, u, v;
    cin >> r >> x >> y >> u >> v;

    long double dist = euclidean(x, y, u, v);

    cout << static_cast<long long int>(ceil((dist)/(2.0*r))) << endl;

    return 0;
}



<|start_filename|>atcoder/abc174C_repsept.lua<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc174/tasks/abc174_c
-- simulation

k = io.read("*n")

if k % 2 == 0 then
  print(-1)
  return
end

sevens = 7
step = 1

while sevens % k ~= 0 do
  if step > 10 ^ 6 then
    step = -1
    break
  end

  sevens = sevens * 10 + 7
  sevens = sevens % k
  step = step + 1
end

print(step)


<|start_filename|>atcoder/abc119D_lazy_faith.cpp<|end_filename|>
// Vicfred
// https://atcoder.jp/contests/abc119/tasks/abc119_d
// binary search
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main() {
    int a, b, q;
    cin >> a >> b >> q;

    vector<long> s(a), t(b);

    for(int i = 0; i < a; ++i)
        cin >> s[i];

    for(int i = 0; i < b; ++i)
        cin >> t[i];

    for(int i = 0; i < q; ++i) {
        long x;
        cin >> x;

        long shrine = lower_bound(s.begin(), s.end(), x) - s.begin();
        long temple = lower_bound(t.begin(), t.end(), x) - t.begin();

        long ans = 1L << 60;
        for(int j = 0; j <= 1; ++j) {
            for(int k = 0; k <= 1; ++k) {
                int idx1 = shrine - j;
                int idx2 = temple - k;
                if(idx1 < 0 or idx2 < 0 or idx1 > a or idx2 > b) continue;
                ans = min(ans, abs(x - s[idx1]) + abs(s[idx1] - t[idx2]));
                ans = min(ans, abs(x - t[idx2]) + abs(s[idx1] - t[idx2]));
            }
        }
        cout << ans << endl;
    }

    return 0;
}



<|start_filename|>codeforces/cf1360D_buying_shovels.hs<|end_filename|>
--- frederick99, 6/2020
--- https://codeforces.com/contest/1360/problem/D
--- math, greedy

import Control.Monad ( replicateM_ )


buyingShovels :: [Int] -> Int
buyingShovels [n, k] = head (cands1 ++ cands2) where
    upper = ceiling . sqrt . fromIntegral $ n
    increasing = [1 .. upper]
    decreasing = [upper, upper-1 .. 1]
    cands1 = [x | x <- increasing, n `div` x <= k, n `mod` x == 0]
    cands2 = [n `div` x | x <- decreasing, x <= k, n `mod` x == 0]


readInput :: IO [Int]
readInput = map read . words <$> getLine

main :: IO ()
main = do
    t <- read <$> getLine
    replicateM_ t (buyingShovels <$> readInput >>= print)


<|start_filename|>atcoder/abc181A_heavy_rotation.lisp<|end_filename|>
;; uninhm
;; https://atcoder.jp/contests/abc181/tasks/abc181_a
;; implementation

(

let (
  (n (read))
)

(write-line
  (cond
    ((= (mod n 2) 0) "White")
    (t "Black")
  )
)

)


<|start_filename|>codeforces/cf71A_way_too_long_words_.hs<|end_filename|>
-- Vicfred
-- https://codeforces.com/problemset/problem/71/A
-- implementation
transform :: String -> String
transform s
    | (length s <= 10) = s
    | otherwise = ([head s] ++ show (length s - 2) ++ [last s])

main :: IO ()
main =  interact $ unlines . (map transform) . tail . words



<|start_filename|>codeforces/cf705A_hulk.cpp<|end_filename|>
// Martin
// https://codeforces.com/problemset/problem/705/A
// implementation

#include<iostream>

int main() {
    int n;
    std::cin >> n;
    if (n == 1) {
           std::cout << "I hate it";
    } else {
        for (int i = 1; i < n; i++) {
            if (i & 1) std::cout << "I hate that "; 
            else std::cout << "I love that "; 
        }
        if (n & 1) std::cout << "I hate it"; 
        else std::cout << "I love it"; 
    }
    return 0;
}


<|start_filename|>codeforces/cf1367A_short_substrings.cpp<|end_filename|>
// Martin
// https://codeforces.com/contest/1367/problem/A
// implementation, strings

#include<iostream>
#include<algorithm>

using namespace std;

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

    string test;
    
    while(tc--) {
        cin >> test;
        string answer;
        for (size_t i = 1; i < test.length(); i += 2) {
            answer += test[i - 1];  // keep char at even indices
            if (i == test.length() - 1) {
                answer += test[i];  // keep both if last iteration
            }
        }

        cout << answer << endl;
    }

    return 0; 
}


<|start_filename|>codeforces/cf41A_translation.cpp<|end_filename|>
// Martin
// https://codeforces.com/contest/41/problem/A
// implementation, reverse, strings

#include<iostream>
#include<algorithm>
#include<string>

using namespace std;

int main() {
    string s, t;
    cin >> s >> t;

    reverse(s.begin(), s.end());

    if (s == t) cout << "YES";
    else cout << "NO";

    return 0;
}


<|start_filename|>atcoder/abc179B_go_to_jail.cpp<|end_filename|>
// https://atcoder.jp/contests/abc179/tasks/abc179_b
#include<iostream>

using namespace std;

int main() {
    int n, a, b;
    cin >> n;
    int count = 0;
    while (n > 0) {
        cin >> a >> b;
        if (a == b) count += 1;
        else count = 0;

        if (count == 3) {
            cout << "Yes" << endl;
            break;
        }
        n--;
    }

    if (count < 3) cout << "No" << endl;

    return 0;
}


<|start_filename|>kattis/stockprices.cpp<|end_filename|>
// Vicfred
// https://open.kattis.com/problems/stockprices
// priority queue
#include <algorithm>
#include <iostream>
#include <queue>
#include <string>
#include <utility>
#include <vector>

using namespace std;

typedef pair<int, int> pi;

int main() {
    int t;
    cin >> t;
    
    while(t--) {
        int n;
        cin >> n;

        priority_queue<pi> bids;
        priority_queue<pi, vector<pi>, greater<pi>> asks;

        int last_price;
        last_price = -1;

        for(int idx = 0; idx < n; idx++) {
            string direction, tmp;
            int quantity, price;
            cin >> direction;
            cin >> quantity;
            cin >> tmp;
            cin >> tmp;
            cin >> price;

            if(direction == "buy")
                bids.push(make_pair(price, quantity));
            if(direction == "sell")
                asks.push(make_pair(price, quantity));

            //cout << "compras: " << bids.size() << endl;
            //cout << "ventas: " << asks.size() << endl;

            while(true) {
                if(bids.empty() or asks.empty())
                    break;
                if(bids.top().first < asks.top().first)
                    break;
                if(bids.top().second <= 0) {
                    bids.pop();
                    break;
                }

                auto ask = bids.top();
                bids.pop();

                //cout << "compra: " << ask.first << " "
                //    << ask.second << endl;

                auto sell = asks.top();
                asks.pop();

                //cout << "venta: " << sell.first << " "
                //    << sell.second << endl;

                int taken = min(ask.second, sell.second);
                ask.second -= taken;
                sell.second -= taken;

                //cout << "cantidad: " << taken << endl;

                last_price = sell.first;

                //cout << "precio: " << last_price << endl;

                if(ask.second > 0)
                    bids.push(ask);
                if(sell.second > 0)
                    asks.push(sell);
            }

            if(asks.empty())
                cout << "-";
            else
                cout << asks.top().first;
            cout << " ";

            if(bids.empty())
                cout << "-";
            else
                cout << bids.top().first;
            cout << " ";

            if(last_price == -1)
                cout << "-";
            else
                cout << last_price;
            cout << endl;
        }
        //cout << "========" << endl;
    }

    return 0;
}



<|start_filename|>atcoder/abc179B_go_to_jail.lua<|end_filename|>
-- Vicfred
-- https://atcoder.jp/contests/abc179/tasks/abc179_b
-- simulation
n = io.read("*n")

b = {}
d = {}
for i = 1, n do b[i], d[i] = io.read("*n", "*n") end

flag = false

for i = 1, n-2 do
   if b[i] == d[i] and
       b[i + 1] == d[i + 1] and
       b[i + 2] == d[i + 2] then
       flag = true
   end
end

if flag then
    print("Yes")
else
    print("No")
end



<|start_filename|>atcoder/abc178B_product_max.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc178/tasks/abc178_b
-- math

main = do
  li <- getLine
  let a:b:c:d:[] = map read $ words li :: [Integer]
  print $ foldl max (-10000000000000000001) [a * c, a * d, b * c, b * d]



<|start_filename|>codeforces/cf1538_stone_game.kt<|end_filename|>
// uninhm
// https://codeforces.com/contest/1538/problem/A
// implementation

fun main() {
	val t = readLine()!!.toInt()
	for (k in 1..t) {
		val n = readLine()!!.toInt()
		var a = readLine()!!.split(" ").map{ x -> x.toInt() }
		val b = a.indexOf(1)
		val c = a.indexOf(n)

		val x = minOf(b, c) + 1
		val y = maxOf(b, c) + 1
		println(minOf(y, x+n-y+1, n-x+1))
	}
}


<|start_filename|>atcoder/acl1A_reachable_towns.cpp<|end_filename|>
#include <algorithm>
#include <vector>
#include <utility>
#include <iostream>
#include <map>
#include "dsu.hpp"

using namespace std;

using atcoder::dsu;

struct city {
    int first, second, index;
};

const int inf = 1 << 30;

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

    vector<city> cities(n);

    for(int i = 0; i < n; i++) {
        cin >> cities[i].first;
        cin >> cities[i].second;
        cities[i].index = i;
    }
    
    sort(begin(cities), end(cities),
            [](city a, city b){ return a.first < b.first; });

    dsu uf(n);
    map<int, int> visited;
    visited[cities[0].second] = 0;

    for(int i = 1; i < n; i++) {
        vector<int> erased;
        pair<int,int> minima = make_pair(inf, inf);

        for(auto [x, y]: visited) {
            if(x < cities[i].second) {
                uf.merge(i, y);
                erased.push_back(x);
                if(minima.first > x)
                    minima = make_pair(x, y);
            } else {
                break;
            }
        }

        for(auto item: erased)
            visited.erase(item);

        int position = minima.second;
        if(minima.first > cities[i].second) {
            minima = make_pair(cities[i].second, i);
            position = i;
        }
        visited[minima.first] = position;
    }

    vector<int> ans(n);
    for(int i = 0; i < n; i++)
        ans[cities[i].index] = uf.size(i);

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

    return 0;
}



<|start_filename|>codeforces/cf867A_between_the_offices.cpp<|end_filename|>
// Martin
// https://codeforces.com/contest/867/problem/A
// implementation

#include<iostream>
#include<string>

using namespace std;

int cnt(string days, string sub) {
    size_t pos = 0;
    int count = 0;
    while ((pos = days.find(sub, pos)) != string::npos) {
        count++;
        pos += sub.size();
    }
    return count;
}

int main() {
    int n_days;
    string days;
    cin >> n_days >> days;

    string fs = "FS", sf = "SF";
    int s = cnt(days, sf);
    int f = cnt(days, fs);

    if (s > f) cout << "YES" << endl;
    else cout << "NO" << endl;

    return 0;
}


<|start_filename|>classical/travelling_salesman_problem.cpp<|end_filename|>
// Vicfred
// http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1437
// dynamic programming
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <cstring>

using namespace std;

const unsigned int MAXN = 15;
int xsize, ysize, n, x[MAXN], y[MAXN], dist[MAXN][MAXN];

int dp[MAXN][1 << MAXN];

int tsp(int pos, int mask) {
    if(mask == (1 << (n + 1)) - 1)
        return dist[pos][0];
    if(dp[pos][mask] != -1)
        return dp[pos][mask];

    int ans = INT32_MAX;
    for(int bit = 0; bit <= n; bit++)
        if(bit != pos and !(mask & (1 << bit)))
            ans = min(ans, dist[pos][bit] + tsp(bit, mask | (1 << bit)));
    return dp[pos][mask] = ans;
}

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

    while(t--) {
        memset(dp, -1, sizeof dp);
        cin >> xsize >> ysize;
        cin >> x[0] >> y[0];
        cin >> n;
        for(int i = 1; i <= n; i++)
            cin >> x[i] >> y[i];

        for(int i = 0; i <= n; i++)
            for(int j = 0; j <= n; j++)
                dist[i][j] = abs(x[i] - x[j]) + abs(y[i] - y[j]);
        cout << "The shortest path has length " << tsp(0, 1) << endl;
    }
    return 0;
}



<|start_filename|>kattis/geppetto.cpp<|end_filename|>
// Vicfred
// https://open.kattis.com/problems/geppetto
// brute force, bitmask
#include <iostream>
#include <vector>

using namespace std;

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

    vector<int> a(M), b(M);
    for(int i = 0; i < M; i++) {
        cin >> a[i] >> b[i];
        a[i] -= 1;
        b[i] -= 1;
    }

    long long ans = 0LL;
    for(int mask = 0; mask < 1 << N; mask++) {
        bool flag = true;

        for(int i = 0; i < M; i++) {
            if(
                mask & (1 << a[i]) and
                mask & (1 << b[i])
            ) {
                flag = false;
                break;
            }
        }
        
        if(flag)
            ans += 1;
    }

    cout << ans << endl;

    return 0;
}



<|start_filename|>atcoder/abc125A_biscuit_generator.lisp<|end_filename|>
; uninhm
; https://atcoder.jp/contests/abc125/tasks/abc125_a
; math

(

let ((a (read))
     (b (read))
     (c (read)))

(write (
  * b (/ (- c (mod c a)) a)
))

)


<|start_filename|>atcoder/abc212B_weak_password.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc212/tasks/abc212_b
-- implementation

import Data.Bool (bool)

following n = (n+1) `mod` 10

isWeak li =
  and (zipWith (==) (init li) (tail li)) || and (zipWith f (init li) (tail li))
    where f a b = b == following a

main = getLine >>= putStrLn . bool "Strong" "Weak" . isWeak . map (read . pure)


<|start_filename|>atcoder/abc081B_shift_only.lua<|end_filename|>
-- Vicfred
-- https://atcoder.jp/contests/abc081/tasks/abc081_b
-- basic math

n = io.read("*n")
A = {}
for i = 1,n do
    A[i] = io.read("*n")
end
minima = 2^64
for i = 1,n do
    times = 0
    while math.fmod(A[i],2) == 0 do
        A[i] = A[i]/2
        times = times + 1
    end
    minima = math.min(minima, times)
end
print(minima)


<|start_filename|>atcoder/abc206B_savings.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc206/tasks/abc206_b
-- math, gauss

solution n =
  ceiling $ (-1 + sqrt (1 + 8*n))/2

main = interact $ show . solution . read


<|start_filename|>cses/coin_combinations_i.cpp<|end_filename|>
// Vicfred
// https://cses.fi/problemset/task/1635
// dynamic programming
#include <iostream>
#include <vector>

using namespace std;

int main() {
    const int mod = 1e9 + 7;
    const int maxn = 1e6 + 1;

    vector<int> dp(maxn, 0);
    dp[0] = 1;

    int n, x;
    cin >> n >> x;

    vector<int> coins(n);
    for(int &coin: coins) {
        cin >> coin;
    }

    for(int i = 1; i <= maxn; ++i) {
        for(int &coin: coins) {
            int value = i - coin;
            if(value >= 0) {
                dp[i] += dp[value];
                dp[i] %= mod;
            }
        }
    }

    cout << dp[x] << endl;

    return 0;
}


<|start_filename|>codeforces/cf1542B_plus_and_multiply.c<|end_filename|>
// uninhm
// https://codeforces.com/contest/1542/problem/B
// modulo, greedy

#include <stdio.h>

int main ()
{
  long long t;
  scanf ("%lld\n", &t);
  while (t--)
    {
      long long n, a, b;
      scanf ("%lld %lld %lld\n", &n, &a, &b);
      long long m = n % b;

      if (a == 1)
        {
          if ((n-1)%b == 0)
            puts ("Yes");
          else
            puts ("No");
          continue;
        }

      long long x = 1;
      long long found = 0;
      while (x <= n)
        {
          if (x%b == m)
            {
              found = 1;
              break;
            }
          x *= a;
        }
      if (found)
        puts ("Yes");
      else
        puts ("No");
    }
}


<|start_filename|>codeforces/cf492A_vanya_and_cubes.cpp<|end_filename|>
// Martin
// https://codeforces.com/contest/492/problem/A
// implementation

#include<iostream>

using namespace std;

int main() {
    int n, height {0}, acc {0};
    cin >> n;

    int i {2}, t {1};
    while (n >= acc + t) {
        acc += t;
        t += i;
        i++;

        height++;
    }

    cout << height << endl;

    return 0; 
}


<|start_filename|>codeforces/cf155A_i_love_username.cpp<|end_filename|>
// Martin
// https://codeforces.com/contest/155/problem/A
// brute force

#include<iostream>

using namespace std;

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

    int value;
    cin >> value;
    int min = value, max = value;
    int amazing {0};
    while (n > 1) {
        cin >> value;
        if (value > max) {
            max = value;
            amazing++;
        } else if (value < min) {
            min = value;
            amazing++;
        }
        n--;
    }
    cout << amazing << endl;

    return 0;
}


<|start_filename|>atcoder/abc189C_mandarin_orange.cpp<|end_filename|>
#include <iostream>
#include <vector>
#include <stack>

using namespace std;

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

    vector<int> A(N);
    for(int &item: A)
        cin >> item;

    vector<int> posLeft(N);
    stack<int> S;

    for(int i = 0; i < N; i++) {
        while(!S.empty() && A[S.top()] >= A[i])
            S.pop();
        posLeft[i] = S.empty() ? 0 : S.top() + 1;
        S.push(i);
    }

    vector<int> posRight(N);
    S = {};

    for(int i = N - 1; i >= 0; i--) {
        while(!S.empty() && A[S.top()] >= A[i])
            S.pop();
        posRight[i] = S.empty() ? N - 1 : S.top() - 1;
        S.push(i);
    }

    int maxArea = 0;
    for(int i = 0; i < N; i++) {
        maxArea = max(maxArea, (posRight[i] - posLeft[i] + 1) * A[i]);
    }

    cout << maxArea << endl;

    return 0;
}


<|start_filename|>atcoder/abc180B_various_distances.c<|end_filename|>
// Vicfred
// https://atcoder.jp/contests/abc180/tasks/abc180_b
// math
#include <stdio.h>
#include <math.h>

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

    long long int manhattan = 0L;
    double euclidean = 0.0L;
    long long int chebyshev = 0L;

    long long int x;
    for(int i = 0; i < n; i++) {
        scanf("%lld", &x);
        x = fabs(x);
        manhattan += x;
        euclidean += x*x;
        chebyshev = fmax(chebyshev, x);
    }

    euclidean = sqrt(euclidean);

    printf("%lld\n%.12lf\n%lld\n", manhattan, euclidean, chebyshev);
    
    return 0;
}


<|start_filename|>atcoder/abc175A_rainy_season.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc175/tasks/abc175_b
-- brute force, recursion

import Data.List

solution n l x y z ans
  | x >= n = ans
  | y >= n = solution n l (x+1) (x+2) (x+2) ans
  | z >= n = solution n l x (y+1) (y+1) ans
  | (l!!y) + (l!!z) > (l!!x) && (l!!y /= l!!z) && (l!!y /= l!!x) && (l!!z /= l!!x) =
    solution n l x y (z+1) (ans+1)
  | otherwise =
    solution n l x y (z+1) ans

main = do
  li <- getLine
  let n = read li
  li <- getLine
  let l = reverse $ sort $ map read $ words li
  print $ solution n l 0 1 1 0



<|start_filename|>atcoder/abc204B_nuts.lisp<|end_filename|>
;; uninhm
;; https://atcoder.jp/contests/abc204/tasks/abc204_b
;; implementation

(setf n (read))
(setq x 0)
(dotimes (_ n)
  (let ((a (read)))
    (if (> a 10)
      (setq x (+ x (- a 10))))))
(write x)


<|start_filename|>atcoder/abc164C_gacha.cpp<|end_filename|>
// https://atcoder.jp/contests/abc164/tasks/abc164_c
#include<iostream>
#include<set>
#include<string>

using namespace std;

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

    set<string> values;
    string value;
    for (int i = 0; i < n; i++) {
        cin >> value;
        values.insert(value);
    }

    cout << values.size() << endl;
    return 0;
}


<|start_filename|>atcoder/abc082B_two_anagrams.lua<|end_filename|>
-- Vicfred
-- https://atcoder.jp/contests/abc082/tasks/abc082_b
-- greedy, sorting

s = io.read()
t = io.read()
a_anagram = {}
for i = 1, #s do
    a_anagram[i] = s:sub(i, i)
end
b_anagram = {}
for i = 1, #t do
    b_anagram[i] = t:sub(i, i)
end
table.sort(a_anagram)
table.sort(b_anagram, function(x, y) return x > y end)
s = table.concat(a_anagram)
t = table.concat(b_anagram)
print(s < t and "Yes" or "No")


<|start_filename|>atcoder/abc169A_multiplication_1.hs<|end_filename|>
-- Vicfred
-- https://atcoder.jp/contests/abc169/tasks/abc169_a
-- implementation
main :: IO ()
main = getLine >>= print . product . map read . words



<|start_filename|>atcoder/abc140A_password_.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc140/tasks/abc140_a
-- basic combinatorics

main = interact $ show . (^3) . read


<|start_filename|>atcoder/abc146A_cant_wait_for_holiday_.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc146/tasks/abc146_a
-- implementation

import Data.List (elemIndex)
import Data.Maybe (fromJust)

main = do
  li <- getLine
  let a = ["SAT", "FRI", "THU", "WED", "TUE", "MON", "SUN"] in
    print $ (+1) $ fromJust $ elemIndex li a


<|start_filename|>codeforces/cf1360A_minimal_square.hs<|end_filename|>
--- frederick99, 6/2020
--- https://codeforces.com/contest/1360/problem/A
--- math, geometry

import Control.Monad ( replicateM_ )


minSquare :: [Int] -> Int
minSquare [w, h] = max a (2*b) ^ 2
    where a = max w h
          b = min w h


readInput :: IO [Int]
readInput = map read . words <$> getLine

main :: IO ()
main = do
    x <- read <$> getLine
    replicateM_ x (minSquare <$> readInput >>= print)


<|start_filename|>atcoder/abc148C_snack.cpp<|end_filename|>
// uninhm
// https://atcoder.jp/contests/abc148/tasks/abc148_c
// implementation

#include<iostream>
#include<numeric>

using namespace std;

int main() {
  long a, b;
  cin >> a >> b;
  cout << lcm(a, b) << endl;
}


<|start_filename|>codeforces/cf546A_soldier_and_bananas.cpp<|end_filename|>
// Martin
// https://codeforces.com/contest/546/problem/A
// brute force, implementation, math

#include<iostream>

int solve(int cost, int money, int amount) {
    int i {1};
    int acc = 0;

    for (int i = 1; i <= amount; i++) acc += i * cost;

    int answer = acc - money;

    return (answer < 0) ? 0 : answer;
}

int main() {
    int k, n, w;
    std::cin >> k >> n >> w;

    std::cout << solve(k, n, w);
    return 0;
}


<|start_filename|>atcoder/abc178B_product_max.lua<|end_filename|>
-- Vicfred
-- https://atcoder.jp/contests/abc178/tasks/abc178_b
-- math

a, b, c, d = io.read("*n", "*n", "*n", "*n")

maxima = c*b
maxima = math.max(maxima, d*b)
maxima = math.max(maxima, c*a)
maxima = math.max(maxima, a*d)

print(maxima)



<|start_filename|>atcoder/abc120A_favorite_sound.lisp<|end_filename|>
;; uninhm
;; https://atcoder.jp/contests/abc120/tasks/abc120_a
;; implementation

(
  let (
    (a (read))
    (b (read))
    (c (read))
  )

  (write (
    min (/ (- b (mod b a)) a) c
  ))
)


<|start_filename|>codeforces/cf1283A_minutes_before_new_year.cpp<|end_filename|>
// Vicfred
// https://codeforces.com/contest/1283/problem/A
// implementation
#include <iostream>

using namespace std;

int main() {
    int t;
    cin >> t;
    while(t--) {
        int h, m;
        cin >> h >> m;
        cout << (23-h)*60+(60-m) << endl;
    }
    return 0;
}



<|start_filename|>codeforces/cf1360E_polygon.hs<|end_filename|>
--- frederick99, 6/2020
--- https://codeforces.com/contest/1360/problem/E
--- simulation, puzzle

import Control.Monad ( replicateM_ )


polygon :: [[Bool]] -> String
polygon grid =
    let right = map tail grid
        bottom = tail grid
        invalid = zipWith3_2d isValid grid right bottom
    in
        if any or invalid
            then "NO"
            else "YES"
    where
        zipWith3_2d = zipWith3 . zipWith3
        isValid t u v = t && not u && not v


readInput :: IO [[Bool]]
readInput = do
    n <- read <$> getLine
    sequence $ replicate n (map (=='1') <$> getLine)

main :: IO ()
main = do
    t <- read <$> getLine
    replicateM_ t (polygon <$> readInput >>= putStrLn)


<|start_filename|>codeforces/cf1514C_product_1_modulo_n.cpp<|end_filename|>
// Vicfred
// https://codeforces.com/contest/1514/problem/C
// math
#include <iostream>
#include <vector>

using namespace std;

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a%b); }

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

    const int maxn = 1e5+1;
    vector<int> a(maxn);

    long long int p = 1LL;
    int ans = 0;

    for(int i = 0; i < n; ++i) {
        if(gcd(n, i) == 1) {
            ans += 1;
            a[i] = 1;
            p *= i;
            p %= n;
        }
    }

    if(p != 1) {
        a[p] = 0;
        ans -= 1;
    }
    cout << ans << endl;
    for(int i = 0; i < maxn; ++i) {
        if(a[i] == 1) {
            cout << i << " ";
        }
    } cout << endl;


}



<|start_filename|>codeforces/cf1330B_dreamoon_likes_permutations.cpp<|end_filename|>
// Vicfred
// https://codeforces.com/problemset/problem/1330/B
// greedy, implementation

#include <algorithm>
#include <iostream>
#include <vector>
#include <set>

using namespace std;

bool ispermutation(set<int> items) {
    int size = items.size();
    for(int i = 1; i <= size; ++i)
        if(items.count(i) == 0)
            return false;
    return true;
}

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

    while(t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        vector<int> sizes;
        
        for(int i = 0; i < n; ++i)
            cin >> a[i];

        int ways = 0;

        set<int> p1;
        set<int> p2;

        for(int i = 0; i < n; ++i) {
            if(p1.count(a[i]) > 0)
                break;
            p1.insert(a[i]);
        }

        for(int i = p1.size(); i < n; ++i) {
            if(p2.count(a[i]) > 0)
                break;
            p2.insert(a[i]);
        }

        int total = p1.size() + p2.size();

        if(ispermutation(p1) and ispermutation(p2) and total == n) {
            ways += 1;
            sizes.push_back(p1.size());
        }

        p1.clear(); p2.clear();

        for(int i = n-1; i > 0; --i) {
            if(p1.count(a[i]) > 0)
                break;
            p1.insert(a[i]);
        }

        for(int i = n-1-p1.size(); i >= 0; --i) {
            if(p2.count(a[i]) > 0)
                break;
            p2.insert(a[i]);
        }

        total = p1.size() + p2.size();

        if(ispermutation(p1) and ispermutation(p2) and total == n) {
            ways += 1;
            sizes.push_back(p2.size());
        }

        if(sizes.size() == 2 and sizes[0] == sizes[1]) {
            ways -= 1;
            sizes.clear();
            sizes.push_back(p2.size());
        }

        cout << ways << endl;
        for(int size: sizes)
            cout << size << " " << n-size << endl;
    }
    return 0;
}



<|start_filename|>atcoder/abc134A_dodecagon_.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc134/tasks/abc134_a
-- implementation

solve r = 3 * r^2

main = interact $ show . solve . read


<|start_filename|>codeforces/cf1422D_returning_home.cpp<|end_filename|>
// Vicfred
// https://codeforces.com/contest/1422/problem/D
// dijkstra, priority queue
#include <algorithm>
#include <iostream>
#include <numeric>
#include <queue>
#include <vector>
#include <utility>

using namespace std;

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

    long long sx, sy, fx, fy;
    cin >> sx >> sy >> fx >> fy;

    vector<vector<pair<long long, long long>>> graph(m + 2);
    graph[m].push_back({m + 1, abs(fx - sx) + abs(fy - sy)});

    vector<long long> x(m), y(m);
    for(long long i = 0; i < m; i++) {
        cin >> x[i] >> y[i];
        graph[m].push_back({i, min(abs(sx - x[i]), abs(sy - y[i]))});
        graph[i].push_back({m + 1, abs(fx - x[i]) + abs(fy - y[i])});
    }

    vector<long long> ordered(m);
    iota(begin(ordered), end(ordered), 0);

    for(long long i = 0; i < 2; i++) {
        sort(begin(ordered), end(ordered),
                [&](long long u, long long v) {return x[u] < x[v]; });
        for(long long j = 0; j <  m - 1; j++) {
            long long a = ordered[j];
            long long b = ordered[j + 1];
            graph[a].push_back({b, x[b] - x[a]});
            graph[b].push_back({a, x[b] - x[a]});
        }
        swap(x, y);
    }

    priority_queue<pair<long long, long long>> q;
    vector<long long> dist(m + 2, 1LL<<60);
    dist[m] = 0;
    q.emplace(0, m);

    while(!q.empty()) {
        auto item = q.top();
        q.pop();

        long long u = -item.first;
        long long v = item.second;

        if(dist[v] != u)
            continue;

        for(auto cell: graph[v]) {
            long long to = cell.first;
            long long cost = cell.second;

            if(dist[v] + cost < dist[to]) {
                dist[to] = dist[v] + cost;
                q.emplace(-dist[to], to);
            }
        }
    }

    cout << dist[m + 1] << endl;

    return 0;
}



<|start_filename|>atcoder/abc185A_abc_preparation.c<|end_filename|>
// uninhm
// https://atcoder.jp/contests/abc185/tasks/abc185_a
// implementation

#include <stdio.h>

int main() {
  int a[4];
  scanf("%d %d %d %d", &a[0], &a[1], &a[2], &a[3]);

  int ans = 1 << 30;
  for(int i = 0; i < 4; ++i)
    ans = a[i] < ans ? a[i] : ans;

  printf("%d\n", ans);
}



<|start_filename|>atcoder/abc205C_pow.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc205/tasks/abc205_c
-- implementation

compare' a b
  | a > b     = ">"
  | a < b     = "<"
  | otherwise = "="

solve [a, b, c]
  | even c = compare' (abs a) (abs b)
  | otherwise = compare' a b

main = interact $ solve . map read . words


<|start_filename|>atcoder/abc141B_tap_dance.lua<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc141/tasks/abc141_b
-- implementation

s = io.read()
ans = "Yes"

for i = 1, s:len(), 1 do
  if i % 2 == 1 and
       s:sub(i,i) ~= 'R' and s:sub(i,i) ~= 'U' and
       s:sub(i,i) ~= 'D' or 
     i % 2 == 0 and
       s:sub(i,i) ~= 'L' and s:sub(i,i) ~= 'U' and
       s:sub(i,i) ~= 'D' then
    ans = "No"
    break
  end
end

print(ans)


<|start_filename|>atcoder/abc197B_visibility.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc197/tasks/abc197_b
-- implementation, recursion

solution p s = go p 0 0 s where
  go p c i s
    | i == length s = c
    | s !! i == '.' = go p (c+1) (i+1) s
    | i > p         = c
    | otherwise     = go p 0 (i+1) s

main' [_, _, y', x'] ls =
  solution x (ls !! y) + solution y (map (!!x) ls) - 1
    where x = x' - 1
          y = y' - 1

main = interact $ show . (\(l:ls) -> main' (map read $ words l) ls) . lines


<|start_filename|>codeforces/cf1407A_ahahahahahahahaha.cpp<|end_filename|>
// Vicfred
// https://codeforces.com/contest/1407/problem/A
// math, greedy, implementation
#include <iostream>
#include <vector>

using namespace std;

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

    while(t--) {
        int n;
        cin >> n;

        vector<int> a(n);
        for(auto &item: a)
            cin >> item;

        int zero, one;
        zero = one = 0;

        for(auto item: a) {
            if(item == 0)
                zero += 1;
            else
                one += 1;
        }

        if(one <= n/2) {
            cout << zero << endl;
            for(int i = 0; i < zero; i++)
                cout << 0 << " ";
            cout << endl;
            continue;
        }

        if(one%2 != 0)
            one -= 1;
        cout << one << endl;
        for(int i = 0; i < one; i++)
            cout << 1 << " ";
        cout << endl;
    }

    return 0;
}



<|start_filename|>atcoder/abc138A_red_or_not_.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc138/tasks/abc138_a
-- implementation

solve [a, s] =
	if (read a) < 3200 then
		"red"
	else
		s

main = interact $ solve . lines


<|start_filename|>atcoder/abc140A_password.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc140/tasks/abc140_a
-- basic combinatorics

main = do
  li <- getLine
  let n = read li in print $ n^3


<|start_filename|>atcoder/abc125A_biscuit_generator.cpp<|end_filename|>
// uninhm
// https://atcoder.jp/contests/abc125/tasks/abc125_a
// math

#include<iostream>

using namespace std;

int main() {
  int a, b, t;
  cin >> a >> b >> t;
  cout << t / a * b << endl;
  return 0;
}


<|start_filename|>atcoder/abc129A_airplane.lua<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc129/tasks/abc129_a
-- implementation

p, q, r = io.read("*n", "*n", "*n")

print(math.min(p+q, p+r, q+r))


<|start_filename|>atcoder/abc177A_dont_be_late_.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc177/tasks/abc177_a
-- basic math

import Data.Bool (bool)

solve [d, t, s] = bool "No" "Yes" $ t*s >= d

main = interact $ solve . map read . words


<|start_filename|>atcoder/abc137A_+-x_.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc137/tasks/abc137_a
-- implementation

solve [a, b] = max (a + b) $ max (a - b) (a * b)

main = interact $ show . solve . map read . words


<|start_filename|>atcoder/abc177D_friends.cpp<|end_filename|>
// Vicfred
// https://atcoder.jp/contests/abc177/tasks/abc177_d
// union find, data structures
#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;

class UnionFind {                                // OOP style
private:
  vi p, rank, setSize;                           // vi p is the key part
  int numSets;
public:
  UnionFind(int N) {
    p.assign(N, 0); for (int i = 0; i < N; ++i) p[i] = i;
    rank.assign(N, 0);                           // optional speedup
    setSize.assign(N, 1);                        // optional feature
    numSets = N;                                 // optional feature
  }

  int findSet(int i) { return (p[i] == i) ? i : (p[i] = findSet(p[i])); }
  bool isSameSet(int i, int j) { return findSet(i) == findSet(j); }

  int numDisjointSets() { return numSets; }      // optional
  int sizeOfSet(int i) { return setSize[findSet(i)]; } // optional

  void unionSet(int i, int j) {
    if (isSameSet(i, j)) return;                 // i and j are in same set
    int x = findSet(i), y = findSet(j);          // find both rep items
    if (rank[x] > rank[y]) swap(x, y);           // keep x 'shorter' than y
    p[x] = y;                                    // set x under y
    if (rank[x] == rank[y]) ++rank[y];           // optional speedup
    setSize[y] += setSize[x];                    // combine set sizes at y
    --numSets;                                   // a union reduces numSets
  }
};

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

    UnionFind friends(n);

    int a, b;
    for(int i = 0; i < m; ++i) {
        cin >> a >> b;
        a -= 1;
        b -= 1;

        friends.unionSet(a, b);
    }

    int ans = 0;
    for(int i = 0; i < n; i++)
        ans = max(ans, friends.sizeOfSet(i));

    cout << ans << endl;

    return 0;
}



<|start_filename|>atcoder/abc125A_biscuit_generator.lua<|end_filename|>
-- Vicfred
-- https://atcoder.jp/contests/abc125/tasks/abc125_a
-- math, implementation
a, b, t = io.read("*n", "*n", "*n")
print((t // a) * b)



<|start_filename|>atcoder/abc142A_odds_of_oddness.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc142/tasks/abc142_a
-- basic probability

main = do
  li <- getLine
  let n  = (read li)
  putStrLn.show $
    (fromIntegral $ floor $ (n + 1) / 2) / n


<|start_filename|>codeforces/cf4A_watermelon.hs<|end_filename|>
-- Vicfred
-- https://codeforces.com/problemset/problem/4/A

f :: Int -> String
f x
    | x == 2 = "NO"
    | even x = "YES"
    | otherwise = "NO"

main :: IO ()
main = interact $ f . read



<|start_filename|>atcoder/abc190A_very_very_primitive_game.hs<|end_filename|>
-- user: nel_tu_
-- path: https://atcoder.jp/contests/abc190/tasks/abc190_a
-- tags: implementation

import Data.Bool ( bool )

solve [a, b, c] = bool "Aoki" "Takahashi" $ a - b + c > 0

main = interact $ solve . map read . words



<|start_filename|>atcoder/abc211B_cycle_hit.hs<|end_filename|>
-- uninhm
-- https://atcoder.jp/contests/abc211/tasks/abc211_b
-- implementation

import Data.List (sort)
import Data.Bool (bool)

isSet :: Ord a => [a] -> Bool
isSet = check . sort
  where
    check [] = True
    check [_] = True
    check (x:y:xs) = x /= y && check (y:xs)

main = interact $ bool "No" "Yes" . isSet . lines



<|start_filename|>atcoder/abc167C_skill_up.cpp<|end_filename|>
// Vicfred
// https://atcoder.jp/contests/abc167/tasks/abc167_c
// bitmasks
#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>

using namespace std;

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

    vector<int> C(N);
    vector<vector<int>> A(N, vector<int>(M));

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

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

    int minima = 1<<30;

    for(int mask = 0; mask <= (1<<N)-1; ++mask) {
        int total = 0;
        vector<int> level(M);

        for(int bit = 0; bit < N; ++bit) {
            if(mask&(1<<bit)) {
                total += C[bit];

                for(int i = 0; i < M; ++i) {
                    level[i] += A[bit][i];
                }
            }
        }

        if(none_of(level.begin(),
                    level.end(),
                    [=](int x) { return x < X; })
          ) {
            minima = min(minima, total);
        }
    }

    if(minima == 1<<30)
        minima = -1;

    cout << minima << endl;

    return 0;
}



<|start_filename|>codeforces/cf1526B_i_hate_1111.cpp<|end_filename|>
// uninhm
// https://codeforces.com/contest/1526/problem/B
// greedy

#include<iostream>

using namespace std;

int main() {
  int t, n;
  cin >> t;
  for (int k = 0; k < t; ++k) {
    cin >> n;
    if (n >= 1110 || 111*(n%11) <= n) cout << "YES\n";
    else cout << "NO\n";
  }
}


<|start_filename|>codeforces/cf1186A_vus_cossack_and_contest.cpp<|end_filename|>
// Martin
// https://codeforces.com/contest/1186/problem/A
// implementation, min

#include<iostream>
#include<algorithm>

using namespace std;

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

    auto min_value = min(m, k);

    if (min_value >= n) cout << "Yes";
    else cout << "No";

    return 0; 
}
