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

int main()
{
int t,z;
cin>>t;
while(t–)
{
int a,b,c,d,x,y;
cin>>a>>b>>c>>d;
x=c/a;
y=d/b;
z=x+y;
cout<<z<<endl;
}

}

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

int main()
{
int t;
long long sum1=0,sum2=0,x,n;
cin>>t;
while(t–)
{
int D,d,p,q;
cin>>D>>d>>p>>q;

n=D/d;
x=((n-1)*n)/2;
sum1=((p*n)+((q*x)))*d;
//cout<<sum1<<endl;

if(D%d!=0)
{
sum2 = sum1 +(D%d)*(p+(q*n));
cout<<sum2<<endl;
}
else
{
cout<<sum1<<endl;
}

}
}

#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define MOD 1000000007
#define all(z) z.begin(),z.end()
using ll = long long int;

using namespace std;

ll Pow(ll a, ll b) {
static ll mod = 1000000007;
if (b == 0) return 1;
if (b == 1) return a;

if (b % 2 == 0) {
ll ans = Pow(a, b / 2);
return (ans * ans) % mod;
}
else {
ll ans = Pow(a, ((b – 1) / 2));
return ((a * ans) % mod * ans) % mod;
}
}

int main() {
fast;
int d;
cin >> d;
while (d–) {

ll a, b, temp;
cin >> a >> b;

temp = Pow(2 , a) – 1;

cout << Pow(temp, b) << endl;

}

return 0;
}

#include <iostream>
using namespace std;

long long int minn(long long int a,long long int b){
if(a>b)
return b;
return a;
}

int main() {
long long int test;
cin>>test;
while(test–)
{
long long int n,m,a[1000005],b[1000005],ans[1000005],count=0,count2=0,j=0,k=0,kk=0;
cin>>n>>m;
for(long long int i=1;i<=n;i++)
{
cin>>a[i];
}
k=n+1;
for(long long int i=1;i<=n;i++)
{
ans[i]=12345678;
}
for(long long int i=1;i<=n;i++)
{
if(a[i]==1){
k=i;
break;
}
}
for(long long int i=n;i>0;i–)
{

if(a[i]==2){
kk=i;
break;
}

}
ans[1]=0;
ans[k]=0;

for(long long int i=k+1;i<=n;i++)
{
count++;
if(a[i] == 1)
count=0;
ans[i]=count;
}
count=0;
ans[kk]=0;

for(long long int i=kk-1;i>0;i–)
{
count++;
if(a[i] == 2)
count=0;
ans[i]=minn(count,ans[i]);

}

// for(long long int i=1;i<=n;i++)
// cout<<ans[i]<<” “;
for(long long int i=1;i<=m;i++)
{
cin>>b[i];
}
for(long long int i=1;i<=m;i++)
{
if(ans[b[i]]==12345678)
{
cout<<-1<<” “;
}
else
cout<<ans[b[i]]<<” “;
}
cout<<“\n”;

}
return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long int
int32_t main() {
// your code goes here
ios_base::sync_with_stdio(false);
int test;
cin >> test;
while (test–)
{
int n;
cin >> n;

vector<pair<int, int>> x;
vector<pair<int, int>> y;
multiset X;
multiset Y;
for (int i = 0; i < n; ++i)
{
int a, b;
cin >> a >> b;
x.push_back({a, b});
y.push_back({b, a});
X.insert(a);
Y.insert(b);
}
sort(x.begin(), x.end());
sort(y.begin(), y.end());
int height1 = 0;
int height2 = 0;
int h1Max = 0;
int h1Min = LONG_MAX;
int area = LONG_MAX;
for (int i = 0; i < n – 1; ++i)
{

h1Max = max(h1Max, x[i].second);
h1Min = min(h1Min, x[i].second);
height1 = h1Max – h1Min;
auto it = Y.find(x[i].second);
Y.erase(it);
height2 = *Y.rbegin() – *Y.begin();
int newArea = (x[i].first – x[0].first) * height1 +
(x[n – 1].first – x[i + 1].first) * height2;
area = min(area, newArea);
}
int width1 = 0;
int width2 = 0;
int w1Max = 0;
int w1Min = LONG_MAX;
for (int i = 0; i < n – 1; ++i)
{
w1Max = max(w1Max, y[i].second);
w1Min = min(w1Min, y[i].second);
width1 = w1Max – w1Min;
auto it = X.find(y[i].second);
X.erase(it);
width2 = *X.rbegin() – *X.begin();
int newArea = (y[i].first – y[0].first) * width1 +
(y[n – 1].first – y[i + 1].first) * width2;
area = min(area, newArea);
}
if (area == LONG_MAX)
area = 0;
cout << area << endl;
}
return 0;
}

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

int Farthest(int node, vector<vector<int>> & GF, int n)
{
vector<bool> reached(n+1, false);
int fd=-1, far; reached[node] = true;
queue<pair<int, int>> qp; qp.push({node, 0});
while(qp.size()){
auto pi = qp.front(); qp.pop();
int N = pi.first, dis = pi.second;
if(fd < dis) fd = dis, far = N;
for(auto cN: GF[N]){
if(reached[cN]) continue;
reached[cN] = true;
qp.push({cN, dis+1});
}
}
return far;
}

void DFS1(int N, int par, vector<vector<int>> & GF, vector<int> & H, vector<int> & list, int cur)
{
bool childnode = true;
int mx = 0;
for(auto cN: GF[N]) if(cN != par)
{
childnode = false; mx = max(mx, H[cN]);
}
if(childnode)
{
list.push_back(cur); return;
}

int c = 0;
for(auto cN: GF[N])
{
if(cN == par) continue;
if(H[cN] == mx && c==0)
{
DFS1(cN, N, GF, H, list, cur+1); c++;
}
else DFS1(cN, N, GF, H, list, 1);
}
}

void HeightFind(int N, int par, vector<vector<int>> & GF, vector<int> & H)
{
bool childnode = true;
for(auto cN: GF[N])
{
if(cN == par) continue;
childnode = false;
HeightFind(cN, N, GF, H);
H[N] = max(H[N], 1 + H[cN]);
}
if(childnode) H[N] = 1;
}

void Between(int N, int par, vector<vector<int>> & GF, vector<int>&list, int n)
{
vector<int> H(n+1, 0);
HeightFind(N, par, GF, H);
DFS1(N, par, GF, H, list, 1);
}

int getSol(vector<vector<int>> & GE, int n, int k)
{
if(k==1)
return 1;
int u = Farthest(1, GE, n);
vector<int> list;
Between(u, 0, GE, list, n);
sort(list.rbegin(), list.rend());
int size = 1, count = 0, i = 0;
while(count<k){
size++;
count+=list[i++];
}
return size;
}

void Solution(){
int n, k;
int u, v;

cin>>n>>k;
vector<vector<int>> GE(n+1);
for(int i=1; i<n; i++){
cin>>u>>v;
GE[u].push_back(v); GE[v].push_back(u);
}
cout << getSol(GE, n, k) << “\n”;
}

int32_t main(){
int T;
cin>>T;
while(T–)
Solution();
return 0;
}

#include<bits/stdc++.h>

using namespace std;
#define ll long long int
#define vect1 vector<ll>
#define vect2 vector<vect1>
#define pair1 pair<ll, ll>

struct structure123 {
template <class T1, class T2>
size_t operator()(const pair<T1, T2>& p) const{
auto hash1 = hash<T1>{}(p.first);
auto hash2 = hash<T2>{}(p.second);
return hash1 ^ hash2;
}
};
#define umap_pll_l unordered_map<pair1, ll, structure123>

void depthSearch(ll nod, ll par, vect2&G, vect1 &S, vect1 &P, vect1 &C, vect1 &L, ll curlev){
C[nod] = 1; P[nod] = par;
L[nod] = curlev;
for(auto cnod: G[nod]){
if(cnod != par){
depthSearch(cnod, nod, G, S, P, C, L, curlev+1);
C[nod] += C[cnod];
S[nod] += S[cnod] + C[cnod];
}
}
}

void depthSearch2(ll nod, ll par, vect2&G, vect1 &T, vect1 &S, vect1 &C, umap_pll_l & Contdp, umap_pll_l & Cdp, ll n){
T[nod] = T[par] + n – 2*C[nod];
for(auto cnod: G[nod])
if(cnod != par){
depthSearch2(cnod, nod, G, T, S, C, Contdp, Cdp, n);
Cdp[make_pair(nod,cnod)] = C[cnod];
Contdp[make_pair(nod, cnod)] = S[cnod];
Contdp[make_pair(cnod, nod)] = T[nod] – S[cnod] – C[cnod];
}
Cdp[make_pair(nod, par)] = n – C[nod];

}

void func123(ll& u, ll dist, vect2 & P123){
for(ll i=20; i>=0; i–)
if((1<<i) <= dist){
dist -= (1<<i);
u = P123[u][i];
}
}

ll LCA1(ll a, ll b, vect2 &P123, vect1 & L){
ll u = a, v = b;
if(L[u] > L[v]) func123(u, L[u]-L[v], P123);
if(L[u] < L[v]) func123(v, L[v]-L[u], P123);
if (u==v) return u;

for(int i=19; i>=0; i–)
if(P123[u][i] != 0 && P123[u][i] != P123[v][i])
u = P123[u][i], v = P123[v][i];

u = P123[u][0];
return u;
}

void function123(ll &a, ll &b, vect2& P123, vect1 &L, vect1 & v){
ll lca = LCA1(a, b, P123, L);

ll dist = abs(L[lca] – L[a]) + abs(L[lca] – L[b]);

ll mva = (dist-1)/2, mvb;
ll m1 = a, m2;

func123(m1, mva, P123);

mvb = dist – 1 – mva; m2 = b;
if(m1 != lca) m2 = P123[m1][0];
else{
func123(m2, mvb, P123);
}

v[0] = m1; v[1] = m2; v[2] = mva; v[3] = mvb;
}

void funct10(ll a, ll b, vect2 & P123){
cout << “[A] ” << a << ” “;
while(P123[a][0] != 0){
a = P123[a][0];
cout << a << ” “;
} cout << “\n”;

cout << “[B] ” << b << ” “;
while(P123[b][0] != 0){
b = P123[b][0];
cout << b << ” “;
} cout << “\n”;
}
void function88(vect2 &G, int n, int q){

vect1 S(n+1, 0), P(n+1, 0), C(n+1, 0), T(n+1, 0), L(n+1, 0);

umap_pll_l Contdp, Cdp;
depthSearch(1, 0, G, S, P, C, L, 1);

T[0] = S[1] + C[1];
depthSearch2(1, 0, G, T, S, C, Contdp, Cdp, n);

vect2 P123(n+1, vect1(20, 0));
for(int nod=1; nod<=n; nod++) P123[nod][0] = P[nod];
for(int j=1; j<20; j++)
for(int nod=1; nod<=n; nod++)
P123[nod][j] = P123[P123[nod][j-1]][j-1];

vector<ll> v(4, 0);
ll a, b, ans=0;
while(q–){

cin>>a>>b;

if (L[a] < L[b]) swap(a, b);
function123(a, b, P123, L, v);
ll m1 = v[0], m2 = v[1], da=v[2], db=v[3];

ll conta = T[a] – (da+1)*Cdp[{m1, m2}] – Contdp[{m1, m2}];
ll contb = T[b] – (db+1)*Cdp[{m2, m1}] – Contdp[{m2, m1}];

ans = conta + contb;
cout <<ans << “\n”;
}
}

int main(){
ios::sync_with_stdio(false); cin.tie(NULL);
int testcases; cin>>testcases;
ll n, q;
while(testcases–){
cin>>n>>q;
vect2 G(n+1);
ll u, v;
for(int i=1; i<n; i++){
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
function88(G, n, q);
}
return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int NN = 1000100;

int ans[NN];

void calc(int mx, int n, int k, int val){
if(k == 1){
ans[val] = 1;
return;
}
if(n==k+1){
for(int i=1;i<=n;i++) if(i!=val) ans[i] = 1;
return;
}

if(n == 3){
ans[val] = 1;
return;
}
int N;

if((val & mx)){
N = n – mx + 1;
N = N + (N & 1) – 1;
int M = k – 1;
N = min(N, M + (M & 1) – 1);
}
else {
N = n – mx + 1;
N = N – (N & 1);
int M = k – 1;
N = min(N, M – (M & 1));
}
for(int i = 1; i <= N; i ++) val ^= mx + i – 1, ans[mx + i – 1] = 1;
if(val == 0 and k – N == mx – 1){
for(int i = 1; i < mx; i ++) ans[i] = 1;
return;
}
if(!val){
if(mx + N – 1 < n) {
val ^= mx;
val ^= mx + N;
ans[mx + N] = 1;
ans[mx] = 0;
}
else {
ans[mx] = 0;
ans[mx+1] = 0;
val ^= mx; N -= 2;
val ^= mx + 1;
}
}

calc(mx / 2, mx – 1, k – N, val);
}

int n, k;

void print(){
for(int i=1;i<=n;i++) {
if(ans[i]) printf(“%d “, i);
ans[i] = 0;
}

puts(“”);
return;
}

void solve(){
scanf(“%d%d”, &n, &k);

if(n == k) {
for(int i = 1; i <= n; i ++) ans[i] = 1;
return;
}

if(k == 1){
ans[n] = 1;
return;
}

if(k == n – 1){
int mx = 0;
int val = 0;
for(int i = 1; i <=n; i ++) val ^= i;
int id;

for(int i = 1; i <= n; i ++){
if((val ^ i) > mx) mx = val ^ i, id = i;
}
for(int i = 1; i <= n; i ++) if(id != i) ans[i] = 1;
return;
}

int mx = 1;
while(mx <= n) mx <<= 1;
mx >>= 1;

if(n + 2 == mx * 2 and k == n – 2){
for(int i = 1; i <= n; i ++) if(i != 2 and i != 3) ans[i] = 1;
return;
}

int val = mx * 2 – 1;

calc(mx, n, k, val);
}
int main(){
#ifndef ONLINE_JUDGE
freopen(“in.in”, “r”, stdin);
freopen(“out.out”, “w”, stdout);
#endif
int T;
cin >> T;
while(T –) solve(), print();
return 0;
}

#include<bits/stdc++.h>
//unsolve
using namespace std;
typedef long long int ll;
struct data1
{
ll go,first,second;
};
struct data
{
ll l,r,val;
};
data tree[500006];
ll n,k;
ll rant[100006];
ll sa[100006];
ll arr[100006];
ll tmp[100006];
ll lcp[100006];
stack<data1> s;
ll maxi[100006];
ll sum[100006];
void revise(ll i,ll pos,ll c)
{
if(tree[i].l==tree[i].r&&tree[i].l==pos)
{
tree[i].val=c;
return ;
}
ll mid=(tree[i].l+tree[i].r)>>1;
if(pos<=mid)
{
revise(i<<1,pos,c);
}
else if(pos>mid)
{
revise((i<<1)+1,pos,c);
}
tree[i].val=max(tree[i<<1].val,tree[(i<<1)+1].val);
return ;
}
ll query(ll i,ll l,ll r)
{
if(l<=tree[i].l&&r>=tree[i].r)
{
return tree[i].val;
}
ll mid=(tree[i].l+tree[i].r)>>1;
ll ans=-2e18;
if(l<=mid)
{
ans=max(ans,query(i<<1,l,r));
}
if(mid<r)
{
ans=max(ans,query((i<<1)+1,l,r));
}
return ans;

}
void init(ll i,ll l,ll r)
{
tree[i].l=l;
tree[i].r=r;
tree[i].val=-2e18;
if(l==r)
{
return ;
}
ll mid=(l+r)>>1;
init(i<<1,l,mid);
init((i<<1)+1,mid+1,r);
return ;
}
bool compare_sa(ll i,ll j)
{
if(rant[i]!=rant[j])
{
return rant[i]<rant[j];
}
else
{
int ri=(i+k<=n+1?rant[i+k]:-2e18);
int rj=(j+k<=n+1?rant[j+k]:-2e18);
return ri<rj;
}
}
void solve()
{
cin>>n;

for(int i=1 ; i<=n ; i++)
{
cin>>arr[i];
}
for(int i=1 ; i<=n+1 ; i++)
{
sa[i]=i;
if(i<=n)
{
rant[i]=arr[i];
}
else
{
rant[i]=-2e18;
}
}
for(k=1 ; k<=n; k=k*2)
{
sort(sa+1,sa+(n+2),compare_sa);
tmp[sa[1]]=0;
for(int i=2 ; i<=n+1; i++)
{
tmp[sa[i]]=tmp[sa[i-1]]+(compare_sa(sa[i-1],sa[i])?1:0);
}
for(int i=1 ; i<=n+1 ; i++)
{
rant[i]=tmp[i];
}
}
/*for(int i=1 ; i<=n+1 ; i++)
{
cout<<rant[i]<<” “<<sa[i]<<“\n”;
}*/
lcp[0]=0;
ll h=0;
for(int i=1 ; i<=n ; i++)
{
int j=sa[rant[i]];
if(h>0)
{
h–;
}
for(; j+h<=n&&i+h<=n ; h++)
{
if(arr[j+h]!=arr[i+h])
{
break;
}
}
lcp[rant[i]-1]=h;
}
/*for(int i=1 ; i<=n+1 ; i++)
{
cout<<lcp[i]<<” “;
}
cout<<“\n”;*/
sum[0]=0;
//cout<<lcp[n]<<“\n”;
for(int i=1 ; i<=n ; i++)
{
sum[i]=sum[i-1]+arr[i];

}
init(1,1,n);
for(int i=1 ; i<=n; i++)
{
revise(1,i,sum[i]);
}
ll tmp2=-2e18;
for(int i=n; i>=1 ; i–)
{
tmp2=max(sum[i],tmp2);
maxi[i]=tmp2;
}
ll ans=-2e18;
ll tmp1;
lcp[n]=0;
for(ll i=1 ; i<=n; i++)
{

s.push((data1){i,lcp[i-1]+1,n-sa[i+1]+1});
//cout<<i<<” “<<sa[i+1]<<” “<<query(1,sa[i+1],n)-sum[sa[i+1]-1]<<“\n”;
while(s.size()&&s.top().second>lcp[i])
{

ans=max(ans,(query(1,sa[s.top().go+1]+max(lcp[i],s.top().first-1),s.top().second+sa[s.top().go+1]-1)-sum[sa[s.top().go+1]-1])*(i+1-s.top().go));
//cout<<query(1,sa[s.top().go+1]+max(lcp[i],s.top().first-1),s.top().second+sa[s.top().go+1]-1)<<” “<<(sum[sa[s.top().go+1]-1])*(i+1-s.top().go)<<“\n”;
if(s.top().first<=lcp[i])
{
ll a=s.top().go;
ll b=s.top().first;
s.pop();
s.push((data1){a,b,lcp[i]});
}
else
{
s.pop();
}
}
}
cout<<ans<<“\n”;
}
int main()
{
int t;
cin>>t;
while(t–)
{
solve();
}
}

#include<bits/stdc++.h>
#define NN (1<<20)

using namespace std;
using INT=long long;
const int mod = 998244353;

int a[NN], p[NN];

int power(int a, long long n, int p) {
int ans=1;
for(; n; n>>=1, a=(long long)a*a%p) if(n&1ll) ans=(long long)ans*a%p;
return ans;
}

namespace FFT{
const int M=1<<19;
const int P=998244353;

int IM;
int a1[M], b1[M], p[M+1], rev[M];

void NTT(int *B, int *A, int N, int D) {
for(int j=0, d=__builtin_ctz(M/N); j<N; j++) A[rev[j]>>d]=B[j];
for(int n=1, m=M/2*D; n<N; m/=2, n<<=1) {
for(int i=0; i<N; i+=n<<1) {
int *w=(D==1?p:p+M) , *a=A+i, *b=A+i+n;
for(int j=0; j<n; j++, a++, b++, w+=m) {
int x=(long long)*w**b%P;
*b=(*a+P-x)%P; *a=(*a+x)%P;
}
}
}
}

void init() {
int fac[100]={0}, n=0;
for(int Q=P-1, q=2; Q>1; q++) if(Q%q==0) {
while(Q%q==0) Q/=q; fac[n++]=q;
}
int G=2;
while(1) {
int flg=1;
for(int i=0; i<n; i++) if(power(G, P/fac[i], P)==1) flg=0;
if(flg) break;
G++;
}
G=power(G, P/M, P);
for(int i=0; i<=M; i++) p[i]=(i==0?1:(long long)p[i-1]*G%P);
for(int i=0, j=1; j<M; j++) {
for(int k=M>>1; (i^=k)<k; k>>=1);
rev[j]=i;
}
IM=power(M, P-2, P);
}

void conv(int *a, int *b, int *c, int N, int P) {
if(N<=64) {
static int temp[64];
memset(temp, 0, sizeof(int)*N);
for(int i=0; i<N; i++) {
for(int j=0; j<N-i; j++) temp[i+j]=(temp[i+j]+(long long)a[i]*b[j])%P;
for(int j=N-i; j<N; j++) temp[i+j-N]=(temp[i+j-N]+(long long)a[i]*b[j])%P;
}
memcpy(c, temp, sizeof(int)*N);
return;
}
NTT(a, a1, N, 1);
NTT(b, b1, N, 1);
int R=IM*(long long)M/N%P;
for(int i=0; i<N; i++) a1[i]=(long long)a1[i]*b1[i]%P*R%P;
NTT(a1, c, N, -1);
}

void conv(int *a, int *b, int N, int P) {
if(N<=64) {
static int temp[64];
memset(temp, 0, sizeof(int)*N);
for(int i=0; i<N; i++) {
for(int j=0; j<N-i; j++) temp[i+j]=(temp[i+j]+(long long)a[i]*a[j])%P;
for(int j=N-i; j<N; j++) temp[i+j-N]=(temp[i+j-N]+(long long)a[i]*a[j])%P;
}
memcpy(b, temp, sizeof(int)*N);
return;
}
NTT(a, a1, N, 1);
int R=power(N, P-2, P);
for(int i=0; i<N; i++) a1[i]=(long long)a1[i]*a1[i]%P*R%P;
NTT(a1, b, N, -1);
}
};

using FFT::M;
using FFT::P;
using FFT::conv;

namespace Inverse{
//AB=1modx^N, i.e.B=A^{-1}, A[0]!=0
int A0[M];
void inverse(int *A, int *B, int N, int P) {
memset(B+1, 0, sizeof(int)*(N-1));
B[0]=power(A[0], P-2, P);
for(int n=2, h=1; n<=N; h<<=1, n<<=1) {
conv(A, B, A0, n, P);
for(int i=0; i<h; i++) A0[i]=0;
conv(A0, B, A0, n, P);
for(int i=h; i<n; i++) ((B[i]=P-A0[i]) ==P) && (B[i]=0);
}
}
};

using Inverse::inverse;

namespace Polynomial{
int A7[M], A8[M];

//C=A*B, deg(A) =n, deg(B) =m
//A=A_n*x^n+…+A_0, B=B_m*x^m+…+B_0
void multiply(int *A, int n, int *B, int m, int P, int *C) {
int N=1<<(32-__builtin_clz(n+m));
memcpy(A7, A, sizeof(int)*(n+1));
memset(A7+n+1, 0, sizeof(int)*(N-n-1));
memcpy(A8, B, sizeof(int)*(m+1));
memset(A8+m+1, 0, sizeof(int)*(N-m-1));
conv(A7, A8, C, N, P);
}

//A=B*Q+R, deg(A)=n, deg(B)=m
//A=A_n*x^n+…+A_0, B=B_m*x^m+…+B_0, B_m!=0
void divide(int *A, int n, int *B, int m, int P, int *Q, int *R) {
if(n<m) {
Q[0]=0;
memcpy(R, A, sizeof(int)*(n+1));
memset(R+n+1, 0, sizeof(int)*(m-n-1));
return;
}
if(n<512) {
memcpy(A7, A, sizeof(int)*(n+1));
int inv=power(B[m], P-2, P);
for(int i=n-m; i>=0; i–) {
int ret=(long long)(P-A7[i+m])*inv%P;
for(int j=m; j>=0; j–) A7[i+j]=(A7[i+j]+(long long)ret*B[j])%P;
((Q[i]=P-ret) ==P) && (Q[i]=0);
}
memcpy(R, A7, sizeof(int)*m);
return;
}
for(int i=0; i<n-m+1; i++) A7[i]=i<=m?B[m-i]:0;
int N=1<<(32-__builtin_clz(n-m));
memset(A7+n-m+1, 0, sizeof(int)*(N-n+m-1));
inverse(A7, A8, N, P);
for(int i=0; i<n-m+1; i++) A7[i]=A[n-i];
N*=2;
memset(A7+n-m+1, 0, sizeof(int)*(N-n+m-1));
memset(A8+N/2, 0, sizeof(int)*(N/2));
conv(A7, A8, Q, N, P);
reverse(Q, Q+n-m+1);
memset(Q+n-m+1, 0, sizeof(int)*(N-n+m-1));
N=1<<(32-__builtin_clz(n));
memset(Q+n-m+1, 0, sizeof(int)*(N-n+m-1));
memset(B+m+1, 0, sizeof(int)*(N-m-1));
conv(B, Q, A7, N, P);
for(int i=0; i<m; i++) ((R[i]=A[i]-A7[i])<0) && (R[i]+=P);
}

//multipoint evaluation
//A=A_n*x^n+…+A_0
//input:x_0, x_1, …, x_{m-1}
//output:y_0=A(x_0) , y_1=A(x_1) , …, y_{m-1}=A(x_{m-1})

int A9[M], A10[M], A11[M], A12[M];
vector<int>B[M], C[M];

//B_{l…r}=prod{x-x_i}{i=l}^{r}
//C_{l…r}=A mod B_{l…r}
// y_l=C_{l…r}
void evaluate(int *A, int n, int *x, int m, int P, int *y) {
if(!m) return;
if(max(n, m)<128) {
for(int i=0; i<m; i++) {
int ret=0;
for(int j=n; j>=0; j–) ret=(ret*(long long)x[i]+A[j])%P;
y[i]=ret;
}
return;
}
function<void (int , int , int )>build=[&](int u, int l, int r) {
if(l==r) {B[u]={!x[l]?0:P-x[l], 1}; return; }
int mid=l+r>>1;
build(u+u, l, mid);
build(u+u+1, mid+1, r);
for(int i=0; i<=mid-l+1; i++) A9[i]=B[u+u][i];
for(int i=0; i<=r-mid; i++) A10[i]=B[u+u+1][i];
multiply(A9, mid-l+1, A10, r-mid, P, A11);
B[u].resize(r-l+2);
for(int i=0; i<=r-l+1; i++) B[u][i]=A11[i];
};
build(1, 0, m-1);
function<void (int , int , int )>solve=[&](int u, int l, int r) {
int n=C[u].size() -1;
if(l==r) {
int ret=0;
for(int i=n; i>=0; i–) ret=((long long)ret*x[l]+C[u][i])%P;
y[l]=ret;
return;
}
int mid=l+r>>1;
for(int i=0; i<=n; i++) A9[i]=C[u][i];
int ldeg=mid-l+1;
for(int i=0; i<=ldeg; i++) A10[i]=B[u+u][i];
divide(A9, n, A10, ldeg, P, A11, A12);
C[u+u].resize(ldeg);
for(int i=0; i<ldeg; i++) C[u+u][i]=A12[i];
for(int i=0; i<=n; i++) A9[i]=C[u][i];
int rdeg=r-mid;
for(int i=0; i<=rdeg; i++) A10[i]=B[u+u+1][i];
divide(A9, n, A10, rdeg, P, A11, A12);
C[u+u+1].resize(rdeg);
for(int i=0; i<rdeg; i++) C[u+u+1][i]=A12[i];
solve(u+u, l, mid);
solve(u+u+1, mid+1, r);
};
C[1].resize(n+1);
for(int i=0; i<=n; i++) C[1][i]=A[i];
solve(1, 0, m-1);
}
};
using Polynomial::evaluate;
using Polynomial::multiply;

namespace fft {
const int mod=998244353;
const int root=31;

int power(int a, int b, int m, int ans=1) {
for (; b; b>>=1, a=1LL*a*a%m) if (b&1) ans=1LL*ans*a%m;
return ans;
}

const int root_1=power(root, mod-2, mod);
using VI = vector<int> ;
using INT = long long;

void fft(VI& a, bool invert) {
int n=a.size();
int PW=power(invert?root_1:root, (mod-1)/n, mod);
for (int m=n, h; h=m/2, m>=2; PW=1LL*PW*PW%mod, m=h) {
for (int i=0, w=1; i<h; ++i, w=1LL*w*PW%mod)
for (int j=i; j<n; j+=m) {
int k=j+h, x=(a[j]-a[k]+mod)%mod;
a[j]+=a[k]; a[j] %= mod;
a[k]=1LL*w*x%mod;
}
}
for (int i=0, j=1; j<n-1; ++j) {
for (int k=n/2; k>(i^=k); k /= 2);
if (j<i) swap(a[i], a[j]);
}
if (invert) {
int rev=power(n, mod-2, mod);
for (int i=0; i<n; ++i)
a[i]=1LL*a[i]*rev%mod;
}
}
VI multiply(const VI& a, const VI& b, int ok=0) {
int n=1, mx=a.size()+b.size()-1;
while (n<mx) n<<=1;
if (mx<256) {
VI c(mx);
for (int i=0; i<a.size(); i++) for (int j=0; j<b.size(); j++) {
c[i+j]=(c[i+j]+1ll*a[i]*b[j])%mod;
}
return c;
}
VI na=a, nb=b;
na.resize(n); nb.resize(n);
fft(na, false);
if (ok) nb=na;
else fft(nb, false);
for (int i=0; i<n; ++i) na[i]=1LL*na[i]*nb[i]%mod;
fft(na, true);
na.resize(mx);
return na;
}
};

int n, r;
vector <int> vec;

vector <int> pre(int st, int ed) {
vector <int> ans;
if(st == ed) {
ans.resize(ed – st + 2);
ans[0] = (mod – st) % mod;
ans[1] = 1;
return ans;
}
int md = (st + ed) >> 1;
vector <int> A, B;
A = pre(st, md);
B = pre(md + 1, ed);
ans = fft :: multiply(A, B);
return ans;
}

int C[NN], A[NN];

int main() {
#ifndef ONLINE_JUDGE
freopen(“in.in”, “r”, stdin);
freopen(“out.out”, “w”, stdout);
#endif
cin >> r >> n;
vec = pre(0, r – 1);
for(int i = 0; i <= r; i ++) A[i] = vec[i];
int tmp = 1;
for(int i = 1; i <= r; i ++) tmp = (INT) tmp * i % mod;
for(int i = 0; i < n; i ++) scanf(“%d”, &a[i]), a[i] %= mod;
for(int i = 1; i <= n; i ++) scanf(“%d”, &p[i]);
FFT::init();
evaluate(A, r, a, n, mod, C);
int ans = 1;
tmp = power(tmp, mod – 2, mod);
for(int i = 1; i <= n; i ++) {
int tot = (INT) C[i-1] * p[i] % mod * tmp % mod;
tot = (tot + 1 – p[i] + mod) % mod;
ans = (INT) ans * tot % mod;
}
cout << ans << endl;
}