[Solution] PermutationForces II Codeforces Solution

[Solution] PermutationForces II Codeforces Solution

E. PermutationForces II

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given a permutation a$a$ of length n$n$. Recall that permutation is an array consisting of n$n$ distinct integers from 1$1$ to n$n$ in arbitrary order.

You have a strength of s$s$ and perform n$n$ moves on the permutation a$a$. The i$i$-th move consists of the following:

• Pick two integers x$x$ and y$y$ such that i≤x≤y≤min(i+s,n)$i\le x\le y\le min(i+s,n)$, and swap the positions of the integers x$x$ and y$y$ in the permutation a$a$. Note that you can select x=y$x=y$ in the operation, in which case no swap will occur.

You want to turn a$a$ into another permutation b$b$ after n$n$ moves. However, some elements of b$b$ are missing and are replaced with −1$-1$ instead. Count the number of ways to replace each −1$-1$ in b$b$ with some integer from 1$1$ to n$n$ so that b$b$ is a permutation and it is possible to turn a$a$ into b$b$ with a strength of s$s$.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

Since the answer can be large, output it modulo 998244353$998244353$.

Input

The input consists of multiple test cases. The first line contains an integer t$t$ (1≤t≤1000$1\le t\le 1000$) — the number of test cases. The description of the test cases follows.

XOR Mixup Codeforces Solution

PermutationForces II Codeforces Solution

Rising Sand Codeforces Solution

3SUM Closure Codeforces Solution

Fixed Point Guessing Codeforces Solution

Equal Reversal Codeforces Solution

Long Binary String Codeforces Solution

The first line of each test case contains two integers n$n$ and s$s$ (1≤n≤2⋅105$1\le n\le 2\cdot {10}^5$; 1≤s≤n$1\le s\le n$) — the size of the permutation and your strength, respectively.

The second line of each test case contains n$n$ integers a1,a2,…,an$a_1,a_2,\dots ,a_n$ (1≤ai≤n$1\le a_i\le n$) — the elements of a$a$. All elements of a$a$ are distinct.

The third line of each test case contains n$n$ integers b1,b2,…,bn$b_1,b_2,\dots ,b_n$ (1≤bi≤n$1\le b_i\le n$ or bi=−1$b_i=-1$) — the elements of b$b$. All elements of b$b$ that are not equal to −1$-1$ are distinct.

It is guaranteed that the sum of n$n$ over all test cases does not exceed 2⋅105$2\cdot {10}^5$.

Output

For each test case, output a single integer — the number of ways to fill up the permutation b$b$ so that it is possible to turn a$a$ into b$b$ using a strength of s$s$, modulo 998244353$998244353$.