Its quite clear from the problem itself that if the amount of money Pechkas has is greater than the amount Gajodhar has, then print “Gaddari karbe” . Otherwise, print “Gaddari nahi karbe”.

#include <bits/stdc++.h>
using namespace std;
signed main()
{
    int a, b;
    cin >> a >> b;
    if(a < b)
        cout << "Gaddari karbe\n";
    else
        cout << "Gaddari nahi karbe\n";
    
 
    return 0;
}

import java.util.*;
public class c{
      public static void main(String args[]){
            Scanner sc=new Scanner(System.in);
            int x=sc.nextInt();
            int y=sc.nextInt();
            if(y>x) System.out.println("Gaddari karbe");
            else System.out.println("Gaddari nahi karbe");
      }
}

Totla Seth replaces ‘t’ with ‘c’ , ‘l’ with ‘r’ and ‘f’ with ‘k’. Hence all occurrences of ‘t’, ‘l’, ‘f’ will be replaced by ‘c’, ‘r’, ‘k’.

#include <bits/stdc++.h>
using namespace std;
signed main()
{
    int T;
    cin>>T;
    while (T--)
    {
        string s;
        cin >> s;
        for(auto x : s)
        {
            if(x == 't')
                cout << 'c';
            else if(x == 'l')
                cout << 'r';
            else if(x == 'f')
                cout << 'k';
            else
                cout << x;
        }
        cout << "\n";
    }
    return 0;
}

import java.util.*;
public class c{
      public static void main(String args[]){
            Scanner sc=new Scanner(System.in);
            int t=sc.nextInt();
            while(t-->0){
                  String s=sc.next();
                  StringBuilder sb=new StringBuilder();
                  for(int i=0;i<s.length();i++){
                        if(s.charAt(i)=='t') sb.append('c');
                        else if(s.charAt(i)=='l') sb.append('r');
                        else if(s.charAt(i)=='f') sb.append('k');
                        else sb.append(s.charAt(i));
                  }
                  System.out.println(sb);
            }
      }
}

We have our equation $$${Px^2\ +\ Qx\ -\ P\ =\ 0}$$$, with roots equal to $$${A}$$$ and $$${B}$$$.

Since $$${A}$$$ and $$${B}$$$ are the roots then,

$$${P.A^2\ +\ Q.A\ -\ P\ =\ 0}$$$ — $$${(1)}$$$

$$${P.B^2\ +\ Q.B\ -\ P\ =\ 0}$$$ — $$${(2)}$$$

Now, $$${S_i=A^i+B^i}$$$

$$${M = \frac{S_{k+2} - S_k}{S_{k+1}}}$$$

On further solving,

$$${M = \frac{A^{k+2} + B^{k+2} - A^k - B^k}{A^{k+1} + B^{k+1}}}$$$

$$${M = \frac{A^k(A^2-1) + B^k(B^2-1)}{A^{k+1} + B^{k+1}}}$$$

Now, from eq(1) and eq(2),

$$${A^2-1=\frac{-QA}{P}}$$$

$$${B^2-1=\frac{-QB}{P}}$$$

Now, $$${M=\frac{A^k\frac{-QA}{P} + B^k\frac{-QB}{P}}{A^{k+1} + B^{k+1}}}$$$

Or, $$${M=\frac{-Q}{P}\frac{A^k.A + B^k.B}{A^{k+1} + B^{k+1}}}$$$

Or, $$${M=\frac{-Q}{P}\frac{A^{k+1} + B^{k+1}}{A^{k+1} + B^{k+1}}}$$$

Or, $$${M=\frac{-Q}{P}.}$$$

You just needed to print the value of $$${\frac{-Q}{P}}$$$.

#include <bits/stdc++.h>
#include <algorithm>
#include <vector>
#define pb push_back
using namespace std;
 
int main()
{
 
    int t;
    cin >> t;
    while (t--)
    {
        int a , b , k;
        cin>>a>>b>>k;
        int ans = -b/a;
        cout<<ans<<endl;
    }
 
    return 0;
}

import java.util.*;
public class c{
      public static void main(String args[]){
            Scanner sc=new Scanner(System.in);
            int t=sc.nextInt();
            while(t-->0){
                  int p=sc.nextInt(), q=sc.nextInt(), k=sc.nextInt();
                  System.out.println(-q/p);
            }
      }
}

For better understanding lets break the solution of this problem down into three parts.

For $$${x_1}$$$:

$$${x_1}$$$ should be the smallest number such that the sum of the bitwise $$${AND}$$$ operations between $$${x_1}$$$ and each element in the subarray $$${A[L:R]}$$$ gets maximized.

Now, as we know about the $$${AND}$$$ operation, we cannot change $$${0}$$$ to $$${1}$$$ using $$${AND}$$$ but we can change $$${1}$$$ to $$${0}$$$, which we don't want as we want to maximize the sum. Means the best we can do to maximize sum is to preserve each and every set bit.

For eg:

Suppose our $$${N}$$$ numbers are $$${1\ 2\ 3\ 4\ 5}$$$ and $$${l=2, r=4}$$$.

From $$${L}$$$ to $$${R}$$$ we have $$${2,\ 3,\ 4}$$$.

$$${2 --- 0010}$$$

$$${3 --- 0011}$$$

$$${4 --- 0100}$$$

Here the set bits(bits having $$${1}$$$) are $$${1^{st}}$$$ bit(from $$${3}$$$), $$${2^{nd}}$$$ bit (from $$${2}$$$ and $$${3}$$$) and $$${3^{rd}}$$$ bit (from $$${4}$$$).

So to maximize the sum of the bitwise $$${AND}$$$ operations between $$${x_1}$$$ and each element in the subarray $$${A[2:4]}$$$, we will have to take a number which has the $$${1^{nd}}$$$, $$${2^{rd}}$$$ and $$${3^{th}}$$$ bits set and all other bits unset as we also want to minimize $$${x_1}$$$. So our answer would be $$${0111}$$$ or $$${7}$$$.

For $$${x_2}$$$:

$$${x_2}$$$ should be the largest number such that the sum of the bitwise $$${OR}$$$ operations between $$${x_2}$$$ and each element in the subarray $$${A[L:R]}$$$ gets maximized.

Now, using the $$${OR}$$$ operation, we can change $$${0}$$$ to $$${1}$$$ but cannot change $$${1}$$$ to $$${0}$$$. As we need to minimize the sum, so it would be optimal to have a number whose set bits are the bits that are present in all of the elements from $$${A_L}$$$ to $$${A_R}$$$, because if on any element bit is $$${0}$$$ then we have to use $$${0}$$$ on this bit in $$${x_2}$$$ also, because we want to minimize the sum and it will produce a $$${0}$$$ bit. But if all elements are having set bits then, either we choose bit as $$${1}$$$ or $$${0}$$$, answer will not change. So we will choose $$${1}$$$ as our bit because our target is also to maximize $$${x_2}$$$.

For example:

Suppose our $$${N}$$$ numbers are $$${1\ 2\ 3\ 7\ 5}$$$ and $$${l=2,\ r=4}$$$.

From $$${l}$$$ to $$${r}$$$ we have $$${2,\ 3,\ 7}$$$.

$$${2 --- 0010}$$$

$$${3 --- 0011}$$$

$$${7 --- 0111}$$$

In this case the only bit that is present in each of the numbers is the $$${2^{nd}}$$$ bit so the answer would be $$${0010}$$$ i.e 2, taking any other bit as set bit would increase the value of sum. If we choose the $$${x_2}$$$ as $$${4}$$$ then $$${2 | 4 = 6}$$$, $$${3 | 4 = 7}$$$, $$${7 | 4 = 7}$$$, so the sum would be $$${20}$$$. But on choosing $$${x_2}$$$ as $$${2}$$$, we would have $$${2 | 2 = 2}$$$, $$${3 | 2 = 3}$$$, $$${7 | 2= 7}$$$, hence the value of each $$${A_i | x_2}$$$ remained $$${A_i}$$$. And the answer in this case is $$${12}$$$ which is less than that of $$${x=4}$$$.

For $$${x_3}$$$:

$$${x_3}$$$ should be the largest number such that the sum of the bitwise $$${XOR}$$$ operations between $$${x_3}$$$ and each element in the subarray $$${A[L:R]}$$$ gets maximized.

Suppose for $$${N=5}$$$ numbers are $$${1\ 2\ 3\ 7\ 5}$$$ and $$${l=2, r=4}$$$.

From $$${l}$$$ to $$${r}$$$ we have $$${2,\ 3,\ 7}$$$.

$$${2 --- 0010}$$$

$$${3 --- 0011}$$$

$$${7 --- 0111}$$$

So, for each bit $$${i}$$$ we should check if the number of elements from $$${l}$$$ to $$${r}$$$ having the $$${i^{th}}$$$ bit set is more than or equal to that of those which don't have the $$${i^{th}}$$$ bit set, then only we can set the $$${i^{th}}$$$ bit in $$${x_3}$$$.

If $$${x_3}$$$ has the $$${1^{st}}$$$ bit set, then $$${XOR}$$$ of that with $$${2}$$$'s $$${1^{st}}$$$ will be 1 while $$${XOR}$$$ of $$${3}$$$'s and $$${7}$$$'s $$${1^{st}}$$$ will be 0. Means $$${1+0+0 = 1}$$$ on the $$${1^{st}}$$$ bit of answer. But if $$${x_3}$$$ has the $$${1^{st}}$$$ bit unset, then $$${1^{st}}$$$ bit of answer will be calculated as $$${0+1+1=10}$$$ which is more. But as we want to minimize the sum. So we will go for set bit.

It simply means that we will go for that bit which is more because that will make $$${0}$$$ as $$${XOR}$$$. But what is the set and unset bits are same in count, then we will make bit set, because our secondary target is maximize $$${x_3}$$$.

We can use $$${2D}$$$ prefix array for calculating the number of bits in a certain range.

#include <bits/stdc++.h>
using namespace std;
#define int long long int
signed main()
{
    int T;
    cin>>T;
    while (T--)
    {
        int n, q;
        cin >> n >> q;
        vector<int> v(n);
        for(int i = 0; i < n; i++)
            cin >> v[i];
        int N = 31;
        vector<vector<int>> pref(n + 1, vector<int> (N));
        for(int i = 0; i < n; i++)
        {
            for(int bit = 0; bit < N; bit++)
            {
                pref[i + 1][bit] = pref[i][bit] + (v[i] >> bit & 1);
            }
        }
        while(q--)
        {
            int l, r;
            cin >> l >> r;
            int len = r - l + 1;
            int x1 = 0, x2 = 0, x3 = 0;
            for(int bit = 0; bit < N; bit++)
            {
                int bits = pref[r][bit] - pref[l - 1][bit];
                if(bits > 0)
                    x1 |= (1 << bit);
                if(bits == len)
                    x2 |= (1 << bit);
                if(bits >= len / 2.0)
                    x3 |= (1 << bit);    
            }
            cout << x1 << " " << x2 << " " << x3 << "\n";
        }
    }
    return 0;
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;
public class A_Likes{
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;
        PrintWriter pw;
        public FastReader()
        {
            br = new BufferedReader(
                new InputStreamReader(System.in));
        }

    
        String next()
        {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
  
        int nextInt() { return Integer.parseInt(next()); }
  
        long nextLong() { return Long.parseLong(next()); }
  
        double nextDouble()
        {
            return Double.parseDouble(next());
        }
  
        String nextLine()
        {
            String str = "";
            try {
                if(st.hasMoreTokens()){
                    str = st.nextToken("\n");
                }
                else{
                    str = br.readLine();
                }
            }
            catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }

    public static void main(String[] args) {
        FastReader sc=new FastReader();
        int t=sc.nextInt();
        while(t-->0){
            int n=sc.nextInt();
            int q=sc.nextInt();
            int f[][]=new int[n][33];
            int a=sc.nextInt();
            for(int j=0;j<32;j++){
                if(((1<<j)&a)!=0) f[0][j]=1;
            }
            for(int i=1;i<n;i++){
                a=sc.nextInt();

                for(int j=0;j<32;j++){
                    if(((1<<j)&a)!=0) f[i][j]=f[i-1][j]+1;
                    else f[i][j]=f[i-1][j];
                }
            }

            while(q-->0){
                int l=sc.nextInt()-1, r=sc.nextInt()-1;
                int res[];
                if(l==0) res=f[r];
                else {
                    res=new int[33];
                    for(int i=0;i<32;i++){
                        res[i]=f[r][i]-f[l-1][i];
                    }
                }
                int x1=0;
                for(int i=0;i<32;i++){
                    if(res[i]>0) {x1+=(1<<i);
                }
                }
                int x2=0;
                for(int i=0;i<32;i++){
                    if(res[i]==r-l+1) x2+=(1<<i);
                }
                int x3=0;
                for(int i=0;i<32;i++){
                    if(res[i]>=r-l+1-res[i]) x3+=(1<<i);
                }

                System.out.println(x1+" "+x2+" "+x3);

            }
        }
    }
}

Suppose that $$${R_i⋅R_j}$$$ is a $$${P^{th}}$$$ power. The sufficient and necessary condition for that is: for any prime λ, the total number of times it divides $$${R_i}$$$ + the total number of times it divides $$${R_j}$$$ must be divisible by $$${P}$$$.

Let us factorize each number $$${R_i = λ_1^{β_1}.λ_2^{β_2}.λ_3^{β_3}...λ_m^{β_m}}$$$, where $$${λ_1,λ_2,λ_3,...λ_m}$$$ are distinct prime numbers and $$${β_1,β_2,β_3,...β_m}$$$ are their respective powers.

For e.g. if $$${R_i = 5040}$$$ and $$${P = 3}$$$

Then, $$${5040 = 2^4.3^2.5^1.7^1}$$$.

Now if we want to pair any number with $$${5040}$$$, then that number must divisible by $$${2^2, 3^1, 5^2, 7^2}$$$. By ensuring that the number has the necessary prime factors and their exponents sum up to a multiple of P, we can guarantee that the product of the number with $$${5040}$$$ will be a $$${P^{th}}$$$ power.

For each number $$${R_i}$$$, we calculate two values: $$${current}$$$ and $$${demand}$$$. $$${current}$$$ represents the multiplication of prime factors with their respective powers modulo $$${P}$$$ and $$${demand}$$$ represents the multiplication of prime factors with the demanding power for making sum $$${P}$$$.

Like for $$${5040}$$$, $$${current = 2^{4\%3=1}.3^{2\%3=2}.5^{1\%3=1}.7^{1\%3=1} = 630}$$$ and $$${demand = 2^{3-1}.3^{3-2}.5^{3-1}.7^{3-1} = 14700}$$$.

We will check how many numbers before $$${R_i}$$$ can fulfill the $$${demand}$$$ of $$${R_i}$$$ and will add that count to the answer. We will update the $$${current}$$$ value of $$${R_i}$$$ in map as it can be used as the $$${demand}$$$ for further numbers.

One edge case that if $$${P=1}$$$ then all pairs will be answer. So the answer will be $$${\frac{n*(n-1)}{2}}$$$. It will overflow int, so you have to use long long int.

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

typedef long long ll;

bool check_ps(int n)
{
    if((int) sqrt(n) == sqrt(n))
        return true;
    return false;

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

    int n, k;
    cin >> n >> k;

    map<ll, int> M;

    ll ans = 0;
    if(k == 1)
    {
        cout <<  1LL * n * (n - 1) / 2 ;
        return 0;
    }
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        ll current = 1;
        ll demand = 1;
        for (int j = 2; j * j <= x; j++)
        {
            int cnt = 0;
            while (x % j == 0)
            {
                x /= j;
                cnt++;
            }
            cnt %= k;
            for (int i2 = 0; i2 < cnt; i2++)
            {
                current *= j;
            }
            if (cnt)
            {
                for (int i2 = 0; i2 < k - cnt; i2++)
                {
                    demand *= j;
                }
            }
        }
        if (x > 1)
        {
            current *= x;
            for (int i2 = 0; i2 < (k - 1); i2++)
            {
                demand *= x;
            }
        }
        ans += M[demand];
        M[current]++;
    }

    cout << ans << "\n";
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;

public class jfal2 {
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;
        PrintWriter pw;

        public FastReader() {
            br = new BufferedReader(
                    new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                if (st.hasMoreTokens()) {
                    str = st.nextToken("\n");
                } else {
                    str = br.readLine();
                }
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }

    public static void main(String[] args) {
        FastReader sc = new FastReader();
        long n = sc.nextInt();
        int p = sc.nextInt();
        TreeMap<Integer, Long> map = new TreeMap<>();
        long res = 0;
        if(p == 1)
        {
            System.out.println(n * (n - 1) / 2);
            return;
        }
        for (int i = 0; i < n; i++) {
            int a = sc.nextInt();
            int target = 1;
            int curr = 1;
            int count = 0;
            while (a % 2 == 0) {
                count++;
                a = a / 2;
            }
            count = count % p;
            if (count > 0) {
                curr *= Math.pow(2, count);
                target *= Math.pow(2, p - count);
            }

            int temp = a;
            for (int j = 3; j * j <= a; j += 2) {
                count = 0;
                while (temp % j == 0) {
                    count++;
                    temp = temp / j;
                }
                count = count % p;
                if (count == 0)
                    continue;
                else {
                    curr *= Math.pow(j, count);
                    target *= Math.pow(j, p - count);
                }
                if(temp < 2)    
                    break;
            }
            if(temp > 1)
            {
                curr *= temp;
                target *= Math.pow(temp, p - 1);
            }
            if (map.containsKey(target)) {
                res += map.get(target);
            }
            map.put(curr, map.getOrDefault(curr, 0L) + 1);
        }
        System.out.println(res);
    }
}

A player will only win if after any kind of move in his turn causes his opponent to lose, irrespective of his opponent's move.

The solution is based on a dynamic programming approach.

Create dp with different states of a and b, where dp[a][b] denotes whether the state for a and b is winning or losing for player 1.

dp[0][0] = false, is losing since the player can’t make any kind of move.

Formally, dp[a][b] = true (means winning for player 1), only if :

anyone of dp[a - i][b] = false for 1 <= i <= a or,

anyone of dp[a - i][b] = false for 1 <= i <= b or,

anyone of dp[a - i][b - i] = false for 1 <= i <= min(a, b).

Time complexity — $$${O(n ^ 3)}$$$.

#include <bits/stdc++.h>
using namespace std;
#define fast_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long int
int INF = 1e18 + 1e9;
int dp[201][201];
bool canSalmanWin(int a, int b)
{
    if(a == 0 && b == 0)
        return false;
    if(dp[a][b] != -1)
        return dp[a][b];
    bool win = false;
    for(int i = 1; i <= a; i++)
        win |= !canSalmanWin(a - i, b);
    for(int i = 1; i <= b; i++)
        win |= !canSalmanWin(a, b - i);
    for(int i = 1; i <= min(a, b); i++)
        win |= !canSalmanWin(a - i, b - i);
    return dp[a][b] = win;
}
signed main()
{
    fast_io;
    int T;
    cin>>T;
    memset(dp, -1, sizeof(dp));
    while (T--)
    {
        int a, b;
        cin >> a >> b;
        if(canSalmanWin(a, b))
            cout << "Salman Khan\n";
        else 
            cout << "Abhishek Bachchan\n";
    }
    return 0;
}

Here the conventional dp solution of $$${O(n ^ 3)}$$$ time complexity fails under the constraints.

Here we can try some optimizations.

One observation could be made that there will be some limited number of losing states.

Initially put all states as losing states.

so for all dp[i][j] = false i.e losing, we can mark the below as winning states:

dp[i + k][j] = true for 1 <= k <= a - i.

dp[i][j + k] = true for 1 <= k <= b - j.

dp[i + k][j + k] = true for 1 <= k <= min(a - i, b - j).

Time complexity of this solution is amortized $$${O(n^2)}$$$.

#include <bits/stdc++.h>
using namespace std;
#define fast_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long int
int INF = 1e18 + 1e9;
signed main()
{
    fast_io;
    int T;
    cin>>T;
    int a = 1000, b = 1000;
    vector<vector<bool>> dp(a + 1, vector<bool> (b + 1));
    for(int i = 0; i <= a; i++)
    {
        for(int j = 0; j <= b; j++)
        {
            if(dp[i][j] == false)
            {
                for(int k = i + 1; k <= a; k++)
                    dp[k][j] = true;
                for(int k = j + 1; k <= b; k++)
                    dp[i][k] = true;
                for(int k = i + 1, m = j + 1; k <= a && m <= b; k++, m++)
                    dp[k][m] = true;
            }
        }
    }
    while (T--)
    {
        cin >> a >> b;
        if(dp[a][b])
            cout << "Salman Khan\n";
        else 
            cout << "Abhishek Bachchan\n";
    }
    return 0;
}

The solution is based on the matrix exponentiation algorithm.

The concept of matrix exponentiation in its most general form is very useful in solving questions that involve calculating the $$${n^{th}}$$$ term of a linear recurrence relation in time of the order of log(n).

Given recurrence,

$$${f_n= a_1.f_{n−1} + b_1.f_{n-2} + c_1.g_{n−2} + d_1.g_{n−3}}$$$

$$${g_n= a_2.g_{n−1} + b_2.g_{n-2} + c_2.f_{n−2} + d_2.f_{n−3}}$$$

can be written in form of matrix as, $$${X_{6 × 1}}$$$ = $$${A_{6 × 6} × B_{6 × 1}}$$$

where X is :

A is :

B is :

or, $$${X = A^N × C}$$$

C is :

Now, $$${A^N}$$$ can be calculated in O(6×6×6×logN) time complexity using matrix exponentiation. Results could be estimated as $$${(f_n + g_n)\% (10^9 + 7)}$$$. Hence the overall time complexity is O(logN).

#include <bits/stdc++.h>
using namespace std;
#define fast_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long int
int mod = 1e9 + 7;
int INF = 1e18 + 1e9;
vector<vector<int>> multiply(vector<vector<int> > A, vector<vector<int> > B){
    vector<vector<int> >result(A.size(),vector<int>(B[0].size(),0));
    if(A[0].size()==B.size()){
        const int N=A[0].size();
        for(int i=0;i<A.size();i++){
            for(int j=0;j<B[0].size();j++){
                for(int k=0;k<A[0].size();k++)
                {
                    result[i][j]+=A[i][k]*B[k][j];
                    result[i][j] %= mod;
                }
            }
        }
    }
    return result;
}
vector<vector<int>> pwr(vector<vector<int>> A, int N)
{
    int n = A.size();
    vector<vector<int>> res (n , vector<int> (n));
    for(int i = 0;i < n;i++)
    {
        for(int j = 0;j < n; j++)
        {
            if(i == j)
                res[i][j] = 1;
        }
    }
    while(N)
    {
        if(N % 2)
            res = multiply(res, A);
        A = multiply(A, A);
        N /= 2;
    }
    return res;
}
signed main()
{
    fast_io;
    int T;
    cin>>T;
    while (T--)
    {
        int a1, b1, c1, d1, a2, b2, c2, d2, f0, f1, f2, g0, g1, g2;
        cin >> a1 >> b1 >> c1 >> d1 >> a2 >> b2 >> c2 >> d2 >> f0 >> f1 >> f2 >> g0 >> g1 >> g2;
        vector<vector<int>> A = {
            {a1, 0, b1, c1, 0, d1},
            {0, a2, c2, b2, d2, 0},
            {1, 0, 0, 0, 0, 0},
            {0, 1, 0, 0, 0, 0},
            {0, 0, 1, 0, 0, 0},
            {0, 0, 0, 1, 0, 0}
        };
        vector<vector<int>> B = {
            {f2},
            {g2},
            {f1},
            {g1},
            {f0},
            {g0}
        };
        int q;
        cin >> q;
        while(q--)
        {
            int n;
            cin >> n;
            vector<vector<int>> res = pwr(A, n);
            res = multiply(res, B);
            cout << (res[4][0] + res[5][0]) % mod << "\n";
        }
    }
    return 0;
}