C. Fishingprince Plays With Array--Codeforces Global Round 21

Problem - C - Codeforces

C. Fishingprince Plays With Array

time limit per test

2 seconds

memory limit per test

512 megabytes

input

standard input

output

standard output

Fishingprince is playing with an array [a1,a2,…,an][a1,a2,…,an]. He also has a magic number mm.

He can do the following two operations on it:

• Select 1≤i≤n1≤i≤n such that aiai is divisible by mm (that is, there exists an integer tt such that m⋅t=aim⋅t=ai). Replace aiai with mm copies of aimaim. The order of the other elements doesn't change. For example, when m=2m=2 and a=[2,3]a=[2,3] and i=1i=1, aa changes into [1,1,3][1,1,3].
• Select 1≤i≤n−m+11≤i≤n−m+1 such that ai=ai+1=⋯=ai+m−1ai=ai+1=⋯=ai+m−1. Replace these mm elements with a single m⋅aim⋅ai. The order of the other elements doesn't change. For example, when m=2m=2 and a=[3,2,2,3]a=[3,2,2,3] and i=2i=2, aa changes into [3,4,3][3,4,3].

Note that the array length might change during the process. The value of nn above is defined as the current length of the array (might differ from the nn in the input).

Fishingprince has another array [b1,b2,…,bk][b1,b2,…,bk]. Please determine if he can turn aa into bb using any number (possibly zero) of operations.

Input

Each test contains multiple test cases. The first line contains the number of test cases tt (1≤t≤1041≤t≤104). Description of the test cases follows.

The first line of each test case contains two integers nn and mm (1≤n≤5⋅1041≤n≤5⋅104, 2≤m≤1092≤m≤109).

The second line of each test case contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109).

The third line of each test case contains one integer kk (1≤k≤5⋅1041≤k≤5⋅104).

The fourth line of each test case contains kk integers b1,b2,…,bkb1,b2,…,bk (1≤bi≤1091≤bi≤109).

It is guaranteed that the sum of n+kn+k over all test cases does not exceed 2⋅1052⋅105.

Output

For each testcase, print Yes if it is possible to turn aa into bb, and No otherwise. You can print each letter in any case (upper or lower).

Example

input

Copy

5
5 2
1 2 2 4 2
4
1 4 4 2
6 2
1 2 2 8 2 2
2
1 16
8 3
3 3 3 3 3 3 3 3
4
6 6 6 6
8 3
3 9 6 3 12 12 36 12
16
9 3 2 2 2 3 4 12 4 12 4 12 4 12 4 4
8 3
3 9 6 3 12 12 36 12
7
12 2 4 3 4 12 56

output

Copy

Yes
Yes
No
Yes
No

Note

In the first test case of the sample, we can do the second operation with i=2i=2: [1,2,2,4,2]→[1,4,4,2][1,2,2,4,2]→[1,4,4,2].

In the second testcase of the sample, we can:

• do the second operation with i=2i=2: [1,2,2,8,2,2]→[1,4,8,2,2][1,2,2,8,2,2]→[1,4,8,2,2].
• do the second operation with i=4i=4: [1,4,8,2,2]→[1,4,8,4][1,4,8,2,2]→[1,4,8,4].
• do the first operation with i=3i=3: [1,4,8,4]→[1,4,4,4,4][1,4,8,4]→[1,4,4,4,4].
• do the second operation with i=2i=2: [1,4,4,4,4]→[1,8,4,4][1,4,4,4,4]→[1,8,4,4].
• do the second operation with i=3i=3: [1,8,4,4]→[1,8,8][1,8,4,4]→[1,8,8].
• do the second operation with i=2i=2: [1,8,8]→[1,16][1,8,8]→[1,16].
• ======================================================================
• 全都展开，注意展开很可能会爆掉，所以放进结构体进行判断，注意个数竟然会超int,开ll包过。

• 
  #include <iostream>
  
  typedef long long int ll;
  using namespace std;
  
  typedef struct
  {
     ll id,num;
  } xinxi;
  
  xinxi s[10000000],t[10000000];
  
  int main()
  {
  
      int tt;
  
      cin>>tt;
  
      while(tt--)
      {
          int n,m;
  
          scanf("%d%d",&n,&m);
  
          int len=0,len1=0;
  
  
  
          for(int i=1; i<=n; i++)
          {
              int x;
  
              scanf("%d",&x);
  
              if(x%m)
              {
                  if(s[len].id==x)
                  {
                      s[len].num++;
  
                  }
                  else
                  {
                      len++;
  
                      s[len].id=x;
  
                      s[len].num=1;
                  }
              }
              else
              {
  
                  ll cnt=1;
  
                  while(x%m==0)
                  {
                      cnt*=(m);
  
                      x/=m;
  
                  }
  
  
                  if(s[len].id==x)
                  {
                      s[len].num+=cnt;
  
                  }
                  else
                  {
                      len++;
  
                      s[len].id=x;
  
                      s[len].num=cnt;
                  }
  
  
              }
          }
  
          len1=len;
  
          len=0;
  
  
          scanf("%d",&n);
  
          int flag=0;
  
          for(int i=1; i<=n; i++)
          {
              int x;
  
              scanf("%d",&x);
  
              if(x%m)
              {
                  if(t[len].id==x)
                  {
                      t[len].num++;
  
                  }
                  else
                  {
                      len++;
  
                      t[len].id=x;
  
                      t[len].num=1;
                  }
              }
              else
              {
                  ll cnt=1;
  
                  while(x%m==0)
                  {
                      cnt*=(m);
  
                      x/=m;
  
                  }
  
  
                  if(t[len].id==x)
                  {
                      t[len].num+=cnt;
  
                  }
                  else
                  {
                      len++;
  
                      t[len].id=x;
  
                      t[len].num=cnt;
                  }
  
  
              }
          }
  
  
  
          if(len1!=len)
          {
              cout<<"No"<<endl;
          }
          else
          {
  
              flag=0;
  
              for(int i=0; i<=len; i++)
              {
                  if(t[i].id!=s[i].id||t[i].num!=s[i].num)
                  {
                      flag=1;
  
                      break;
  
                  }
              }
  
              if(flag)
              {
                  cout<<"No"<<endl;
              }
              else
              {
  
                  cout<<"YES"<<endl;
              }
          }
  
  
          for(int i=0;i<max(len1,len);i++)
          {
  
              s[i].id=0;
              s[i].num=0;
              t[i].id=0;
              t[i].num=0;
          }
  
      }
  
      return 0;
  }