2025年春招饿了么笔试马上开始，看看去年改编真题热热身！

1、有一个数组a，求这个数组不同的质数和不同的合数共有多少个。合数是指在大于1的整数中除了能被1和本身整除外，还能被其他数(0除外)整除的数。第一行输入一个整数n表示数组长度。1<=n<=2*10^5。第二行输入n个整数表示数组a。1<=ai<=2*10^5

输出一个整数。

输入

3

20 2 4 输出

3

------------------------------------------------------------------------------------------------------------

2、有一个长度为n的数组a,定义了一个函数f(L,R)=aL|aL+1|...|aR。|表示位运算中的按位或运算。现在有q次询问,每次询问都会给出一个区间[L,R]，以及一个正整数k，想知道在区间中是否存在一个右端点r(l<=r<=R)，使得f(L,r)=k?输入包含若干行。第一行两个正整数n,q([1,10^5]),分别表示数组a的长度和询问次数。第二行n个正整数ai([1,10^9]),表示数组a的每个元素。

接下来q行,每行三个正整数L,r,k(1<=L<=R<=n,1<=k<=3*10^9)输出包含q行,每行一个整数，如果存在符合条件的,请输出最小的一个,如果不存在输出一个-1。 输入

5 5

3 2 3 3 6

1 2 3

1 5 7

1 4 7

2 2 2

2 3 7

输出

1

5

-1

2

-1

说明：第一个询问,区间[1.2]中,选择r=1，区间[1,1]的f值为3，因此输出1。

--------------------------------------------------------------------------------------------------------- 3、一个无向图，删除若干条边,使得最终恰好有2个连通块。每次删除一条边后可以获得这条边边权的价值。能获得的最大价值是多少?第一行输入两个整数n, m,代表节点数量和边的数量。接下来的m行,每行输入三个正整数u,v, w，代表节点u和节点v有一条边权为w的边。如果该无向图初始的连通块的数量不小干3，则输出-1.否则输出—个整数,代表小红能获得的最大价值。

示例1

输入

3 3

1 2 4

2 3 3

1 3 2

输出

7

说明

删除前两条边即可。这样有两个连通块:节点1和节点3的连通块，节点2自己为个连通块。

示例2

输入

4 2

1 2 4

3 4 3

输出

0

说明

初始即为两个连通块,且无法删除任何边(如果删除就会变成3个连通块)。