We must first determine the scenario in which the answer is $$$0$$$. If $$$a > c$$$, then. Following that, if $$$b <= d$$$, the answer will be $$$-1$$$. Answer for the alternative case is $$$\frac{c - a}{b - d} + 1$$$. Because every second, the distance will be reduced by $$$(d - b)$$$.

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int tests;
	cin >> tests;
	while (tests--) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		if (a > c) {
			cout << 0 << '\n';
			continue;
		}
		if (b <= d) {
			cout << -1 << '\n';
			continue;
		}
		int num = c - a;
		int den = b - d;
		cout << num / den + 1 << '\n';
	}
	return 0;
}

We can solve this problem by doing pre bruteforce with using vector and map data structures. $$$(10^6)^3$$$ = $$$10^{18}$$$

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define int ll
#define double ld
#define _FastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pii pair<int , int>
#define pb emplace_back
#define endl '\n'
#define sz(x) (int)((x).size())
#define all(x) (x).begin() , (x).end()
#define rall(x) (x).rbegin() , (x).rend()
#define F first
#define S second
const int mod = 1e9 + 7;
const int MAXX = 1e6 + 5;
const int N = 1e6;
const int INF = 1e18 + 123;

int t , l , r , k , x , y , ans;
map<int , int> p;

signed main()
{
    _FastIO;
    vector<int> v;
    vector<int>::iterator it;
    v.pb(0);
    p[0] = 0;
    for(int i = 1; i <= N; i++){
        k = i * i * i;
        x = (i - 1) * (i - 1) * (i - 1);
        p[k] = p[x] + k;
        p[k] %= mod;
        v.pb(k);
    }
    cin >> t;
    while(t--){
        cin >> l >> r;
        it = lower_bound(all(v) , l);
        it--;
        k = *it;
        x = p[k];
        it = upper_bound(all(v) , r);
        it--;
        k = *it;
        y = p[k];
        ans = y - x;
        ans += mod;
        ans %= mod;
        cout << ans << endl;
    }
    return 0;
}

So you just need to find first $$$n+1$$$ $$$f$$$ values. Then find first $$$n+1$$$ $$$s$$$ values. After first $$$n+1$$$ values, the answer is infinitely repeating.

#include <bits/stdc++.h>

using namespace std;

typedef long double LD;
typedef long long int LL;
typedef pair <int,int> pii;

#define L first
#define R second

const int maxn = 1e5 + 100;
int f[maxn], s[maxn];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n, q;
	cin >> n >> q;
	for (int i = 1; i <= n; i++)
		cin >> f[i], f[n + 1] ^= f[i];

	for (int i = 1; i <= n + 1; i++)
		s[i] = s[i - 1] ^ f[i];

	while (q--) {
		int idx;
		cin >> idx;
		idx = ((idx - 1) % (n + 1)) + 1;
		cout << s[idx] << '\n';
	}

	return 0;
}

All switched on bits of $$$x$$$ should be switched on in every $$$a_i$$$. You can do anything you want with other bits (except you can't make some bit in every $$$a_i$$$ switched on, but anyway it's impossible in the best case, because you can just turn bits off). If we will ignore fixed bits, we can see that the best way to choose numbers, is to add bits of $$$i-1$$$ between switched on bits of $$$x$$$.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define int ll
#define _FastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pii pair<int , int>
#define pb emplace_back
#define endl '\n'
#define all(x) (x).begin() , (x).end()
#define rall(x) (x).rbegin() , (x).rend()
#define F first
#define S second
const int mod = 1e9 + 7;
const int MAXX = 1e6 + 5;
const int N = 1e6;
const int INF = 1e18 + 123;

int t , x , n;

signed main()
{
    _FastIO;
    cin >> t;
    while(t--){
        cin >> x >> n;
        n--;
        vector<int> v;
        for(int i = 0; i <= 60; i++){
            if(x & (1LL << i))
                continue;
            v.pb(1LL << i);
        }
        int ans = x;
        for(int i = 0; i <= 30; i++){
            if(n & (1LL << i))
                ans += v[i];
        }
        cout << ans << endl;
    }
    return 0;
}

We declare $$$dp[i][0]$$$ $$$(1 \le i \le n)$$$, as the maximum chosen days between day $$$1$$$ and $$$i$$$ such that the last day we chose was Green ("G"), Also $$$dp[i][1]$$$ for Yellow ("Y") and $$$dp[i][2]$$$ for Red ("R") will be defined same as Green. So the final answer will be maximum of $$$(dp[n][0], dp[n][1], dp[n][2])$$$. For base we put $$$dp[0][0] = dp[0][1] = dp[0][2] = 0$$$, and for example for update of $$$dp[i][0]$$$, We will have :

If the $$$i_{th}$$$ day is Green ("G"), we will have :

$$$dp[i][0] = max(dp[i — 1][0], dp[i — 1][2]) + 1$$$.

and if the $i_{th} day is not Green ("G"), we will have :

$$$dp[i][0] = dp[i - 1][0]$$$.

And for the other colors, the update is with the same idea.

#include<bits/stdc++.h>

using namespace std;

int main()
{
	int T;
	cin >> T;
	for(int test = 0; test < T; test++)
	{
		int n;
		cin >> n;
		string s;
		cin >> s;
		int dp[n+1][3];
		dp[0][0] = dp[0][1] = dp[0][2] = 0;
		for(int i = 0; i < n; i++)
		{	
			dp[i+1][0] = dp[i][0];
			dp[i+1][1] = dp[i][1];
			dp[i+1][2] = dp[i][2];
			if(s[i] == 'G')dp[i+1][0] = max(dp[i][0],dp[i][2])+1;
			else if(s[i] == 'Y')dp[i+1][1] = max(dp[i][0],dp[i][1])+1;
			else dp[i+1][2] = max(dp[i][1],dp[i][2])+1;
		}
		cout << max(dp[n][0], max(dp[n][1], dp[n][2])) << '\n';
	}
}

With this constraints, we can write brute force. For being fast we need sieve.

If $$$N=p^a*q^b*r^c$$$ .

Number of divisors = $$$(a+1)*(b+1)*(c+1)$$$,

#include <bits/stdc++.h>
using namespace std;

#define _FastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pb emplace_back
const int MAXX = 1e4 + 5;
const int N = 1e4;
const int NUM = 4000000;

int t , n , i , j , k , s , m , cnt;
bool p[MAXX];
int ans[MAXX];
vector<int> v;

void sieve(){
    p[2] = true;
    for(i = 3; i < N; i += 2){
        p[i] = true;
    }
    for(i = 3; (i * i) < N; i += 2){
        if(p[i]){
            for(j = (i + i + i); j < N; j += (i + i))
                p[j] = false;
        }
    }
    v.pb(2);
    for(i = 3; i < N; i += 2){
        if(p[i])
            v.pb(i);
    }
}

signed main()
{
    _FastIO;
    sieve();
    for(i = 1; i <= NUM; i++){
        k = i;
        s = 1;
        for(j = 0; (v[j] * v[j]) <= k; j++){
            if(k % v[j])
                continue;
            cnt = 0;
            while(k % v[j] == 0){
                k /= v[j];
                cnt++;
            }
            s *= (cnt + 1);
        }
        if(k > 1)
            s *= 2;
        while(m < s){
            m++;
            ans[m] = i;
        }
    }
    scanf("%d" , &t);
    while(t--){
        scanf("%d" , &n);
        printf("%d" , ans[n]);
        putchar('\n');
    }
    return 0;
}

At first, we assume that the answer is not $$$-1$$$, the state that the answer is $$$-1$$$ will be easily found.

From the constraints we can realize that any number from $$$1$$$ to $$$10^{13}$$$ has at most $$$M = \frac{log(10^{13})}{log(3)}$$$ which is less than $$$30$$$ digits.

So sum of the digits will be at most $$$2 * 30 = 60$$$, then we calculate the answer with recursion, for this way, we declare function $$$f(k, cntdigits, before)$$$ which calculates the $$$k_{th}$$$ smallest semi-prime-lover that has at most $$$cntdigits$$$ digits in $$$base_{3}$$$. We call a number semi-prime-lover if it's sum of digits + $$$before$$$ becomes a prime number.

Note that if $$$before = 0$$$ we will have the prime-lover number so the answer is $$$f(k, M, 0)$$$. Also for solving the problem we need :

$$$cnt[i][j] (0 \leq i \leq M, 0 \leq j \leq S)$$$, that calculates the number of numbers with at most $$$i$$$ digits (obviously in $$$base_3$$$) with sum of digits equal to $$$j$$$, which can be calculated in this way : $$$cnt[0][0] = 1, cnt[i][j] = cnt[i-1][j] + cnt[i-1][j-1] + cnt[i-1][j-2]$$$.

for calculating $$$f(k, cntdigit, before)$$$ we always try to determine the value of the most valuable digit of the answer.

More specifically, suppose the number of semi-prime-lover numbers while the most valuable digit is $$$0$$$ be $$$x$$$, when it's $$$1$$$ be $$$y$$$ and when it's $$$2$$$ be $$$z$$$, now if $$$(0 \le k \le x)$$$ then the most valuable digit is $$$0$$$, and if $$$(x < k \le x + y)$$$ then the most valuable digit is $$$1$$$, and when $$$(x + y < k \le x + y + z)$$$ the most valuable digit is $$$2$$$ (otherwise the answer is $$$-1$$$).

In order to know how many semi-prime-lover numbers with most valuable digit $$$w$$$ we have, it's enough to calculate the following formula :

$$$\sum_{p_i \in P} cnt[cntdigits-1][p_i-w-before]$$$.

That $$$P$$$ means the set of prime numbers from $$$0$$$ to $$$S$$$.

Now the answer can be calculated in this way :

$$$f(k, cntdigits, before) = f(k, cntdigits-1,before)$$$.

$$$f(k, cntdigits, before) = 3^{cntdigits-1} + f(k-x, cntdigits-1,before+1)$$$.

$$$f(k, cntdigits, before) = 2*3^{cntdigits-1} + f(k-x-y, cntdigits-1,before+2)$$$.

Time Complexity : $$$\mathcal{O}(\log {MAX_N}^2 + T \times \log MAX_N \times \frac{\log {MAX_N}}{\log \log MAX_N})$$$.

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll N = 30; // N = MAX_DIGIT_IN_BASE_3
vector<ll> primes = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59};
ll dp[N][N*2], n, k, ans;

ll Find(ll k, ll digit, ll before)
{
	if(digit == -1)
		return 0;
	ll last_sum = 0, sum = 0;
	for(ll d = 0; d < 3; d++)
	{
		for(auto p: primes)if(p >= d+before)
			sum += dp[digit][p-d-before];
		if(sum >= k)
			return d*pow(3, digit)+Find(k-last_sum, digit-1, before+d);
		last_sum = sum;
	}
	return -1LL;
}

int main()
{
	memset(dp, 0, sizeof(dp));
	dp[1][0] = dp[1][1] = dp[1][2] = 1;
	for(int i = 0; i < N; i++)dp[i][0] = 1;
	for(int i = 0; i < N; i++)dp[i][1] = i;
	for(int i = 2; i < N; i++)
		for(int j = 2; j < 2*N; j++)
			dp[i][j] = dp[i-1][j]+dp[i-1][j-1]+dp[i-1][j-2];
	
	int T;
	cin >> T;
	for(int test = 0; test < T; test++)
	{
		cin >> n >> k;
		ans = Find(k, N-1, 0);
		if(ans > n)
			ans = -1;
		cout << ans << '\n';
	}
}

If you check all the cases from $$$1$$$ to $$$12$$$, You'll understand that if $$$n$$$ is a divisor of $$$12$$$, Answer is Yes, Otherwise the answer is No.

/*
*   ────────────── •✵•✵• ──────────────
* |         In The Name of *Allah*       |
*   ────────────── •✵•✵• ──────────────
*/

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10; 

void solve (){
  int n;
  cin >> n;
  cout << (12 % n == 0 ? "Yes" : "No");
}

int main () {
  ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int tc = 1;
  // cin >> tc;
  while (tc --) {
    solve();
  }
  return 0;
}
/* Thanks *Allah* */

The first condition is that $$$c$$$ and $$$d$$$ both must be greater than $$$a$$$ and $$$b$$$. So select two integers in such a way that both have only one common divisor and that must be $$$gcd(a, b)$$$. Now you can select both elements in the following way.

Now if $$$gcd(a,b) = g$$$ then $$$gcd(a+(x×g),b+(y×g))$$$ is also $$$g$$$. where $$$x$$$ and $$$y$$$ are non-zero positive integers.

so best suitable solution is $$$c = (max(a,b)+g)$$$ and $$$d = (max(a,b)+2×g)$$$ because $$$c$$$ and $$$d$$$ need to be distinct.

#include<bits/stdc++.h>
using namespace std;
 
int main(){
    int a,b;
    cin>>a>>b;
    int g = __gcd(a,b);
    int maxi = max(a,b);
    cout<<maxi+g<<' '<<maxi+2*g<<'\n';
    return 0;
}

For this particular problem you can solve it in too many ways but let's discuss $$$O(n^2)$$$ first and then we discuss the $$$O(n)$$$ solution.

$$$O(n^2)$$$ solution:

Traverse through $$$1$$$ to $$$n$$$ and now if you want to count divisors of $$$i$$$ you can find all of them in $$$O(n)$$$ and for this problem constraint is low you can do $$$O(n^2)$$$.

$$$O(n)$$$ solution:

If you want to find total numbers which have number $$$x$$$ in their divisors in the range $$$1$$$ to $$$n$$$ you can see such numbers form an Arithmetic progression like $$$x, 2x , 3x , ... $$$ so it's an arithmetic progression of a difference $$$x$$$ so the total number of terms in this AP is $$$\lfloor \frac{n}{x} \rfloor$$$ and sum of them is $$$\lfloor \frac{n}{x} \rfloor × x$$$

so we just have to traverse through $$$1$$$ to $$$n$$$ and count of all factors of all numbers will be $$$\sum \lfloor \frac{n}{i} \rfloor$$$ and sum all factors will be $$$\sum \lfloor \frac{n}{i} \rfloor × i$$$

// In the name of GOD
#include<iostream>
using namespace std;

int main(){
	int n;
	cin >> n;
	int ans1 = 0, ans2 = 0, counter;
	for (int i = 1; i <= n; i++) {
		counter = 0;
		for (int j = 1; j <= i; j++) {
			if (i % j == 0) {
				ans1 += j;
				counter++;
			}
		}
		ans2 += counter;	
	}
	cout << ans2 << ' ' << ans1;
	return 0;

}

Maximum sum we can form with a number of length $$$m$$$ is $$$9×m$$$(by placing all nines).so if $$$s$$$ is greater than $$$9×m$$$ there is no answer.

Now to find minimum number:

Traverse from $$$i=m-1$$$ to $$$i=0$$$ and fill every digit.

if $$$i=m-1$$$ then we fill $$$1^{st}$$$ digit and $$$(m-1)$$$ digits are remaining (excluding present digit).

if $$$i=m-2$$$ then we will $$$2^{nd}$$$ digit and $$$(m-2)$$$ digits are remaining(excluding present digit).

so if you are at $$$i$$$ then $$$i$$$ digits are remaining.The maximum possible sum we can form with those remaining $$$i$$$ digits is $$$9×i$$$ and $$$k$$$ is the remaining sum.

hence $$$j=max(0,k - 9×i)$$$ so assign $$$1$$$ to $$$j$$$ if $$$i = m-1$$$ and $$$j = 0$$$ because we should not have leading zeroes and we take $$$j$$$ at that place and subtracting $$$j$$$ from remaining sum $$$k$$$.

Now to find the maximum number:

first, we take as many nines as possible and decrease the sum by $$$9$$$ respectively, and when the sum becomes less than $$$9$$$ we print that digit, and the remaining digits should be zero.

// In the name of Allah
#include <bits/stdc++.h>
using namespace std;
int main (){
  int m, s, i, k;
  cin >> m >> s;
  if (s < 1 && m > 1 || s > m * 9) cout << -1 << " " << -1 << endl;
  else {
    for (i = m - 1, k = s; i >= 0; i--) {
      int j = max(0, k - 9 * i);
      if (j == 0 && i == m - 1 && k) j = 1;
      cout << j;
      k -= j;
    }
    cout << ' ';
    for (i = m - 1, k = s; i >= 0; i--) {
      int j = min(9, k);
      cout << j;
      k -= j;
    }
  }
}
// Thanks Allah

source : 103150I — EZ Programming Contest #1 — X-OR XOR Let's figure out what $$$x$$$ should be by going bit by bit in its binary representation. In particular, let $$$a_i, b_i,$$$ and $$$x_i$$$ denote the ith bit from the right in $$$a, b,$$$ and $$$x$$$, respectively. Then for all positive integers $$$i$$$:

• If $$$a_i=0$$$ and $$$b_i=0$$$, $$$x_i$$$ can be $$$0$$$ or $$$1$$$. However, since $$$x≤10^{18}$$$, it is better to set $$$x_i=0$$$ to avoid going over that limit.
• If $$$a_i=0$$$ and $$$b_i=1$$$, no such $$$x_i$$$ exists, and the answer is $$$−1$$$.
• If $$$a_i=1$$$ and $$$b_i=0$$$, $$$x_i=1$$$.
• If $$$a_i=1$$$ and $$$b_i=1$$$, $$$x_i=0$$$. Therefore, by going bit by bit, we can construct such an $$$x$$$ or report whether no such $$$x$$$ exists. This runs in $$$O(log N)$$$ per test case.

There is also a simpler solution not involving going bit by bit, which uses the same proof as above: just set $$$x=$$$ $$$a$$$ $$$XOR$$$ $$$b$$$, and test whether this $$$x$$$ is valid or not.

// In the name of Allah
#include <bits/stdc++.h>
using namespace std;

void solve() {
    long long a, b;
    cin >> a >> b;
    long long res = 0, count = 1;
    while (a || b) {
        int b1 = a & 1, b2 = b & 1;
        if (b1 == 1) {
            if (b2 == 0) {
                res += (1LL << count);
            }
        }
        else if (b2 == 1) {
            cout << -1 << endl; return;
        }
        a >>= 1; b >>= 1;
        count++;
    }
    res >>= 1;
    cout << res << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int tt; cin >> tt; for (int i = 1; i <= tt; i++) {
    solve();
   }
}
// Thanks Allah

source : 103150F — EZ Programming Contest #1 — Palindromicity The string $$$aaa...aaa$$$ with length $$$l$$$ has exactly $$${l+1}\choose{2}$$$ palindromic substrings. Therefore it suffices to find some triangular numbers that add up to exactly $$$n$$$.

To do this, we can greedily choose the largest triangular number less than $$$n$$$. It can be checked that the length of the string will be at most $$$300$$$ for the given constraints.

Alternatively, by Gauss's Eureka Theorem, we only need to express $$$n$$$ as the sum of three triangular numbers. We can just brute force the three triangular numbers and find the answer for each $$$n$$$. This runs in $$$O(n\sqrt{n})$$$ per test case if you lazily brute force, or $$$O(n)$$$ or $$$O(n\sqrt{n})$$$ per test case if you use some math to find the next smallest triangular number or use precomputation.

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

int main(){
    vector<ll>tri{0};
    for(int i=1;i<=400;i++)tri.push_back(tri.back()+i);
    int q;cin>>q;
    while(q--){
        ll s;cin>>s;
        ll cs=0;string ss;
        int cur=0;
        while(cs<s){
            int i=0;
            while(tri[i+1]+cs<=s)i++;
            cs+=tri[i];
            for(int j=0;j<i;j++)ss+=char('a'+cur);
            cur=(cur+1)%26;
        }
        cout<<ss<<"\n";
    }
}

source : 102953-8 — CodeRams Algorithm Contest #2 — Number Placement For a given room of size $$$m$$$, it’s optimal to place the $$$m - 1$$$ smallest primes, and $$$1$$$, in the open cells. We can calculate the primes less than $$$10^7$$$ using the Sieve of Eratosthenes, and make a prefix sum array $$$P$$$, where we the $$$i_{th}$$$ element will pre calculate the sum of the first $$$i - 1$$$ primes and $$$1$$$. This way, $$$P[i]$$$ will be the minimum possible sum of numbers in a room of size $$$i$$$. Finally, we can run a DFS on the floor plan of the house to find the size of each room, and add $$$P[i]$$$ to the answer for each room size we find.

Proof of the first $$$m - 1$$$ prime numbers have minimum co-prime sum :

Suppose coprime numbers are not the first $$$m - 1$$$ primes and $$$1$$$, then there should at least be two numbers that have at least one common prime factor, which violates the condition that the numbers should be coprime.

#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
#include <map>
#include <fstream>
#include <bitset>
#include <unordered_map>
#include <stack>
#include <list>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef map<int, int> mii;
typedef map<int, string> mis;
typedef map<string, int> msi;
typedef set<int> si;
typedef set<ll> sl;
typedef map<ll, ll> mll;
typedef queue<int> qi;
typedef queue<ii> qii;
typedef vector<string> vs;
typedef pair<ll, ll> iil;
typedef priority_queue<int> pqi;
typedef priority_queue<ii> pqii;
typedef priority_queue<ll> pqil;
typedef priority_queue<iil> pqiil;
typedef vector<iil> viil;
typedef vector<vi> vvi;
typedef long double ld;
typedef pair<int, ii> iii;
typedef pair<iil, ll> iiil;
typedef vector<pair<pair<int,int>,int> > viii;
typedef vector<pair<pair<ll,ll>,ll> > viiil;
typedef vector<vl> vvl;

#define pb push_back
#define mp make_pair
#define rep(i, n) for (int i = 0 ; i < n ; i++)
#define rrep(i, m, n) for (int i = m ; i < n ; i++)
#define per(i, n) for (int i = n - 1 ; i >= 0 ; i--)
#define perr(i, m, n) for (int i = n - 1 ; i >= m ; i--)
#define INF 2000000000

ll MOD = 1000000007;

int mat[1005][1005];
bool vis[1005][1005];
int sm = 0;
int n;
bool comp[10000005];
vi p;
int MX = 10000005;

void dfs(int i, int j) {
	if (i < 0 || i >= n || j < 0 || j >= n) return;
	if (!mat[i][j]) return;
	if (vis[i][j]) return;
	vis[i][j] = true;
	sm++;
	dfs(i-1, j);
	dfs(i+1, j);
	dfs(i, j-1);
	dfs(i, j+1);
}

void solve() {
	
	for (int i = 2 ; i * i <= MX ; i++) {
		if (comp[i]) continue;
		for (int j = i * i ; j < MX ; j += i) {
			comp[j] = true;
		}
	}
	
	rep(i, MX) {
		if (!comp[i] && i > 1) {
			p.pb(i);
		}
	}
	
	vl pf;
	pf.pb(0);
	pf.pb(1);
	rep(i, p.size()) {
		pf.pb(pf[pf.size()-1] + p[i]);
	}
    cin >> n;
    
    
    rep(i, n) {
    	string s;
    	cin >> s;
    	rep(j, n) {
    		mat[i][j] = (s[j] == '.');
    	}
    }
    
    ll tot = 0;
    
    rep(i, n) {
    	rep(j, n) {
    		if (!vis[i][j] && mat[i][j]) {
	    		sm = 0;
	    		dfs(i, j);
	    		tot = (tot + pf[sm]);
	    	}
    	}
    }
    
    //cout << p.size() << '\n';
    cout << tot << '\n';
}

void querySolve() {
    int t;
    cin >> t;
    for (int i = 0 ; i < t ; i++) {
        solve();
    }
}

int32_t main() {
	ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    solve();
    //querySolve();
}