Codeforces Mahmoud the Thief(思维)-Toy模板网

这篇具有很好参考价值的文章主要介绍了Codeforces Mahmoud the Thief(思维)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

As Ayoub was going home from Mahmoud's house, he remembered that he forgot his hard disk, which contains the solutions to n problems from the JU Flash contest. The ith problem has size ai.

While panicking, he remembered that he installed a software that prevented the user from copying any files and only allowed the files to be cut from the hard disk in any order the user wants.

As a security measure, the software will stop the transfer if the number of remaining files is 1, or the absolute difference between the sizes of every pair of problems left on the hard disk is divisible by m.

Ayoub knows the permutation b, which represents the order of the problems Mahmoud will attempt to cut from the hard disk.

Since Ayoub is a bad programmer, he asks for your help to tell him how many problems Mahmoud will steal until the transfer stops.

Input

The first line contains two integer n and m (1≤n≤105) (1≤m≤109)

The second line contains integers a1,a2,...,an (1≤ai≤109)

The third line contains a permutation b , b1,b2,...,bn (1≤bi≤105)

Output

print exactly one integer −− the number of codes Mahmoud can steal

Examples

input

Copy

3 2
2 1 4
2 1 3

output

Copy

input

Copy

3 2
2 1 4
3 2 1

output

Copy

input

Copy

5 2
7 9 5 33 77
5 3 4 2 1

output

Copy

Note

In The first sample :

At first Mahmoud will try to cut the file with index 22, and he can do it since there exists two files, the absolute difference between their sizes is not divisible by m(for example file 22 and file 11 (a1−a2=1) and 11 is not divisible by 22).

After cutting The first file, the remaining files will be the files with indices 11 and 33, Mahmoud can't cut The next file, because the absolute difference between any pair is divisible by m.

So Mahmoud will steal only one file.

停止条件是数组中任意两个数的差值能被m除断，我们对原数组中每一个数取模m，发现只要余数相同，则必会满足上述条件，所以题目变为数组中所有数对m取模后，不同的余数是否只有一个。文章来源地址https://www.toymoban.com/news/detail-494152.html

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e+5;
int a[maxn];
int b[maxn];
int main()
{
	int n,m;
	cin>>n>>m;
	map<int,int> mp;
	int res=0;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		mp[a[i]%m]++;
		if(mp[a[i]%m]==1)
		res++;
	}
	for(int i=1;i<=n;i++)
	cin>>b[i];
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		if(res==1)
		break;
		mp[a[b[i]]%m]--;
		if(mp[a[b[i]]%m]==0)
		res--;
		cnt++;
	}
	cout<<cnt<<endl;
	return 0;
}

到了这里，关于Codeforces Mahmoud the Thief(思维)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！