A. Zhinai's Hello XXXX

Just output Hello xxx.

B. Wisdom is buying melons

Link: https://ac.nowcoder.com/acm/contest/23478/B
Source: niuke.com

Title Description

A man came to buy melons.
"cronies,How much is this melon? "
"Two yuan a catty "
"What's up，The melon skin is made of gold,Or are melon particles made of gold? "

Zhinai comes to the fruit stall to buy melons. NN different watermelons are sold on the fruit stall. The weight of the second watermelon is wiwi. Zhinai can choose to buy a whole melon or split the melon to buy half a melon. The weight of half a melon is wi22wi.

In other words, zhinai has three different decisions for each watermelon:

1. Buy a whole watermelon weighing wiwi
2. Split the melon and buy half a watermelon weighing wi22wi
3. Do not purchase

In order to simplify the problem, we ensure that the weight of all melons is a positive even number.

Now zhinai wants to know that if he wants to buy the weight sum of watermelon is k = 1,2,3 Mk=1,2,3... M, how many schemes are there to buy watermelon? Because these numbers may be very large, please output the result after taking the remainder of 109 + 7109 + 7.

Enter Description:

Enter two integers in the first line N,M(0≤N≤103,1≤M≤103)N,M(0≤N≤103,1≤M≤103),Each represents the number of watermelons NN，And the maximum weight of the query is MM. 
if NN Not 00, next line NN Positive even number wi(2≤wi≤2×103)wi(2≤wi≤2×103)Represents the weight of each watermelon.

Output Description:

Output one line MM A number that represents the weight of the watermelon purchased and k=1,2,3...Mk=1,2,3...M How many plans are there to buy watermelon? Because these numbers may be very large, please output the number of plans to 109+7109+7 The result after taking the remainder.

Example 1

input

copy

3 6
8 2 4

output

copy

1 2 1 3 2 3

Compared with the naked backpack, dp [I, j] represents the number of schemes that use the first I watermelons to figure out the weight of j. It should be noted that the second dimension of dp array should be 2e3. Although m does not exceed 1e3, dp[i, w[i]] += 1 in the code; This sentence refers to WI, and wi may reach 2e3. See code for transfer equation:

#include <iostream>
#include <map>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <set>
#include <vector>
#define int long long
#define mod 1000000007
#define ll long long
#define pb push_back
#define pii pair<int,int>
using namespace std;
ll dp[1005][2005] = { 0 };
ll w[2005];
ll n, m;
signed main() {
	cin >> n >> m;
	for(ll i = 1; i <= n; i++) {
		cin >> w[i];
	}
	for(ll i = 1; i <= n; i++) {
		dp[i][w[i]] += 1;
		dp[i][w[i] / 2] += 1;
		for(int j = 1; j <= m; j++) {
			dp[i][j] = (dp[i - 1][j] + dp[i][j]) % mod;
			if(j - w[i] >= 0) dp[i][j] = (dp[i - 1][j - w[i]] + dp[i][j]) % mod;
			if(j - w[i] / 2 >= 0) dp[i][j] = (dp[i - 1][j - w[i] / 2] + dp[i][j]) % mod;
		}
	}
	for(int i = 1; i <= m; i++) {
		cout << dp[n][i] << " ";
	}
	return 0;
}

C. Another version

Link: https://ac.nowcoder.com/acm/contest/23478/C
Source: niuke.com

Title Description

This question is another version of the original version. In short, this question is the inversion of the input and output of the original version.

A man came to buy melons.
"cronies,How much is this melon? "
"Two yuan a catty "
"What's up，The melon skin is made of gold,Or are melon particles made of gold? "

Zhinai came to the fruit stall to buy melons. Several different watermelons were sold on the fruit stall. The weight of the second watermelon was wiwi. Zhinai can choose to buy a whole melon or split the melon to buy half a melon. The weight of half a melon is wi22wi.

In other words, zhinai has three different decisions for each watermelon:

1. Buy a whole watermelon weighing wiwi
2. Split the melon and buy half a watermelon weighing wi22wi
3. Do not purchase

In order to simplify the problem, we ensure that the weight of all melons is a positive even number.

Now zhinai knows that the weight sum of watermelon purchased is k = 1, 2 and 3 respectively Mk=1,2,3... M, the result after taking the remainder of 109 + 7109 + 7.

She wants to restore the weight of several different watermelons sold by the fruit stall. Please construct a fruit stall selling NN different watermelons. The weight of watermelons purchased meets zhinai's requirements. When there are many answers that meet the description of the question, you only need to input any one.

We guarantee that the input data has at least one legal solution of N ≤ 103N ≤ 103.

Enter Description:

Enter a positive integer in the first line M(1≤M≤103)M(1≤M≤103)，Indicates that zhinai knows the upper limit of the quality and of watermelon purchased.
Next line MM Integer, number ii An integer representing the weight of the watermelon purchased and ii The number of types of schemes to buy watermelon is 109+7109+7 The result after taking the remainder.

Output Description:

First, output an integer NN，The number of watermelons. Ask you to give NN Size range in[0,103][0,103]between
 Next line NN Positive even number wiwi，Represents the weight of each watermelon. Ask you to give wiwi Size range in[2,2×103][2,2×103]Between, and wiwi Is an even number.


The input data guarantees that there is at least one set of legal solutions within the output range.

Example 1

input

copy

6
1 2 1 3 2 3

output

copy

3
8 2 4

There is no idea during the game, dp we still need to practice more~~~

First of all, it is easy to know that the number of 2 is certain. If you don't think backwards, how do you get the number of schemes dp[i, j] in question B? Here's how to subtract it. The idea is to continuously put the weight used into the answer vector in the process of changing the number of dp schemes to 0. Traverse the dp array from front to back. If the value of a position is not 0, it means that the number of schemes corresponding to the remaining weight i can only be provided by i*2 watermelon / 2. At this point, put an i*2 into ans, and then update the following dp array part.

#include <iostream>
#include <map>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <set>
#include <vector>
#define mod 1000000007
#define int long long
#define pb push_back
#define pii pair<int,int>
using namespace std;
int m, dp[1005], w[1005];
int c[2005] = { 0 };
int cnt = 0;
signed main() {
	cin >> m;
	for(int i = 1; i <= m; i++) {
		cin >> dp[i];
	}
	vector<int> ans;
	dp[0] = 1;//Don't forget it
	for(int i = 1; i <= m; i++) {
		while(dp[i]) {
			ans.push_back(i * 2);
			for(int j = i; j <= m; j++) {//When i==j, dp[i] is processed, and the number of remaining schemes is provided by dp[i] i*2 melons. Therefore, dp[0] should be set to 1, that is, 1 should be reduced every time
				dp[j] = (dp[j] - dp[j - i] + mod) % mod;
				if(j - i * 2 >= 0) dp[j] = (dp[j] - dp[j - i * 2] + mod) % mod;
			}
		}
	}
	cout << ans.size() << endl;
	for(auto x : ans) {
		cout << x << " ";
	}
	return 0;
}

D. Zhinai's 01 string disrupts

Pure sign, just choose two 01 positions to exchange.

E. Zhinai's digital building blocks

Link: https://ac.nowcoder.com/acm/contest/23478/E
Source: niuke.com

Title Description

This question has a corresponding hard version. The difference between the two is only in the data range. Ensure that the test case set of easy version is a subset of hard version.

Zhinai sauce has NN blocks, each of which has its own color and number. The color range of NN blocks is from 11 to MM and the number range is from 00 to 99.
Now zhinai sauce arranges these blocks in a row from left to right, so that the blocks look like a large integer. Zhinai feels that the number is not large enough, so he decides to exchange some blocks to make the large integer as large as possible.

Specifically, intelligence can exchange adjacent and same color digital blocks infinitely at any time.
But even so, zhinai feels that this figure is not big enough.

So zhinai sauce took out her paint bucket. She decided to conduct KK operations. Each time, she selected two colors PP and QQ, and then dyed all the blocks with PP color into QQ.
Of course, zhinai sauce can also be adjusted by exchanging adjacent blocks of the same color after dyeing.

Now zhinai wants to know what is the largest positive integer she can get by exchange before and after KK dyeing operations. Of course, this large integer is allowed to contain leading zeros.
Because this large integer is very large, you are only required to output the result of taking the remainder of 109 + 7109 + 7.

Enter Description:

Enter three integers on the first line N,M,K(1≤N,M≤105,0≤K≤10)N,M,K(1≤N,M≤105,0≤K≤10)It indicates the number of building blocks, the type of initial color, and the number of times zhinai sauce is dyed.
Next, enter a length of NN String that consists only of the number 0−90−9 form.
Next line NN A positive integer coli(1≤coli≤M)coli(1≤coli≤M)Indicates the color of the building block.
next KK Line, enter two positive integers for each line P,Q(1≤P,Q≤M)P,Q(1≤P,Q≤M)Indicates that two colors are selected PP,QQ，Then set all colors to PP Color the building blocks QQ. 

Output Description:

output K+1K+1 OK, that is, she does it KK The largest positive integer pair 109 can be obtained by exchange before and after each dyeing operation+7109+7 The result of the remainder.

Example 1

input

copy

10 2 0
9586547120
1 2 1 2 1 1 1 1 1 1

output

copy

586754147

Example 2

input

copy

10 2 1
9586547120
1 2 1 2 1 1 1 1 1 1
1 2

output

copy

586754147
876554147

Example 3

input

copy

5 5 4
12345
1 2 3 4 5
3 2
2 5
4 5
5 1

output

copy

12345
13245
13245
15432
54321

Note that the k range is very small, so each dyeing is directly processed by violence, then the interval of the same color is sorted by violence, and then the value of the string is calculated by violence traversal.

#include <iostream>
#include <map>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <set>
#include <vector>
#define mod 1000000007
#define ll long long
#define pb push_back
#define pii pair<int,int>
using namespace std;
int n, m, k;
char s[100005];
int c[100005];
bool cmp(char a, char b) {
	return a > b;
}
int main() {
	cin >> n >> m >> k;
	c[n + 1] = -1;
	scanf("%s", s + 1);
	
	for(int i = 1; i <= n; i++) {
		cin >> c[i];
	}
	int lst = 1;
	for(int i = 2; i <= n + 1; i++) {
		if(c[i] != c[i - 1]) {
			sort(s + lst, s + (i - 1) + 1, cmp);
			lst = i;
		}
	}
	ll ans = 0;
	for(int i = 1; i <= n; i++) {
		ans = (ans * 10) % mod;
		ans = (ans + s[i] - '0') % mod;
	}
	cout << ans << endl;
	for(int i = 1; i <= k; i++) {
		int p, q;
		cin >> p >> q;
		for(int j = 1; j <= n; j++) {
			if(c[j] == p) c[j] = q;
		}
		int lst = 1;
		for(int j = 2; j <= n + 1; j++) {
			if(c[j] != c[j - 1]) {
				sort(s + lst, s + (j - 1) + 1, cmp);
				lst = j;
			}
		}
		ans = 0;
		for(int i = 1; i <= n; i++) {
			ans = (ans * 10) % mod;
			ans = (ans + s[i] - '0') % mod;
		}
		cout << ans << endl;
	}
	return 0;
}

G. Zhinai's tree rotates

Link: https://ac.nowcoder.com/acm/contest/23478/G
Source: niuke.com

Title Description

This question has a corresponding hard version, * easy version has additional restrictions *, so as to ensure that the test case set of easy version is a subset of hard version.

Tree rotation is a subtree adjustment operation in a binary tree. Each rotation does not affect the result of the middle order traversal of the binary tree.

Tree rotation is usually used to adjust the local balance of the tree. Tree rotation includes two different ways: left rotation and right rotation. The two rotations are mirror images and operate against each other.

As shown in the figure, it is the schematic diagram of left rotation and right rotation of the tree. When AA node is located in the left subtree of BB node, right rotation with AA node as the rotation axis can be carried out. On the contrary, left rotation with BB node as the rotation axis can be carried out.

Specifically

Right rotation:

When the node AA is located on the left child of the node BB, the node AA can rotate right as the rotation axis. The rotation operation involves 44 nodes with structural changes.
We remember that the right child of AA node before rotation is ββ Node. The parent node of BB node is XX node (if BB node is the root node of the whole tree, there is no need to do operations related to XX node).
After rotation ββ The node changes from the right child of AA node to the left child of BB node, and one of the child nodes of XX node changes from BB node to AA node, and there is no other change in the order between them and XX node; In other words, if the original BB node is the right child of XX node, it will become AA node after rotation, and replace BB node to become the new right child of XX node. On the contrary, if BB node initially is the left child of XX node, AA node will replace BB node to become the new left child of XX node after rotation.

Left rotation:
When the node BB is located in the right child of the node AA, the node BB can rotate left as the rotation axis. The rotation operation involves 44 nodes with structural changes.
We remember that the left child of BB node before rotation is ββ Node. The parent node of AA node is XX node (if AA node is the root node of the whole tree, there is no need to do operations related to XX node).
After rotation ββ The node changes from the left child of BB node to the right child of AA node, one of the child nodes of XX node changes from AA node to BB node, and there is no other change in the order between them and XX node; That is to say, if AA node is the right child of XX node, it will become BB node after rotation and replace AA node to become the new right child of XX node. On the contrary, if AA node initially is the left child of XX node, BB node will replace AA node to become the new left child of XX node after rotation.

Zhinai recently learned tree rotation. The essence of tree rotation is the change of the parent-child relationship between the rotation axis node and its parent node of a binary tree. From the visual effect, it seems that the whole tree has been "rotated".

In the actual operation process, if the rotation axis is specified, there is no difference between the so-called "left rotation" and "right rotation". When the rotation axis is determined, there will be only one rotation method, and the following rules shall be followed.

• The root node cannot be selected as an axis of rotation.
• When the rotation axis is the left child tree of its parent node, the rotation axis can only rotate right.
• When the rotation axis is the right subtree of its parent node, the rotation axis can only rotate left.

Now zhinai has a binary tree with the size of NN. Zhinai has made a rotation operation on it to disrupt it. She wants you to restore it through a series of tree rotation operations. It requires that you operate no more than N2 times.

Enter Description:

Enter a positive integer in the first line N(1≤N≤103)N(1≤N≤103)，Indicates the number of nodes in the binary tree, from 11 to NN grade.


next NN Line to enter what the binary tree looks like at the beginning.
Enter two nonnegative integers per line lch,rch(0≤lch,rch≤N)lch,rch(0≤lch,rch≤N)Represents the left and right subtrees of each node.
When lchlch When the value of is 00, it means that the node has no left subtree rchrch When the value of is 00, it means that the node has no right subtree.



next NN The row input binary tree is disrupted.
Enter two nonnegative integers per line lch,rch(0≤lch,rch≤N)lch,rch(0≤lch,rch≤N)Represents the left and right subtrees of each node.
When lchlch When the value of is 00, it means that the node has no left subtree rchrch When the value of is 00, it means that the node has no right subtree.


You are required to restore the disrupted binary tree through a series of rotation operations

Output Description:

First, output an integer KK，Indicates the number of times you restore the binary tree to rotate. You are required to give KK The scope of[0,N2][0,N2]，next KK Row to output the rotation axis of the rotation operation in turn.
Since the rotation axis can only rotate left or right, the referee program will judge whether it needs to rotate left or right.
Note: the root node in the rotation process cannot be used as the rotation axis. If you specify the root node in the rotation process as the rotation axis, the referee program will give it directly WA Results.


easy version Additional restrictions ensure that the binary tree can be restored by no more than one tree rotation, that is, it must exist K≤1K≤1 Solution.

Example 1

input

copy

5
2 3
0 0
4 5
0 0
0 0
2 4
0 0
1 5
0 0
0 0

output

copy

1
1

easy version is relatively simple, because it only rotates once at most, so it can only rotate two points where the parent-child relationship between the front and rear trees is exchanged.

#include <iostream>
#include <map>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <set>
#include <vector>
#define ll long long
#define pb push_back
#define pii pair<int,int>
using namespace std;
int n;
struct node {
	int ls, rs;
} n1[1005], n2[1005];
int fa1[1005], fa2[1005];
int main() {
	cin >> n;
	for(int i = 1; i <= n; i++) {
		int l, r;
		cin >> l >> r;
		n1[i].ls = l, n1[i].rs = r;
		fa1[l] = fa1[r] = i;
	}
	for(int i = 1; i <= n; i++) {
		int l, r;
		cin >> l >> r;
		n2[i].ls = l, n2[i].rs = r;
		fa2[l] = fa2[r] = i;
	}
	int p1 = 0, p2 = 0;
	for(int i = 1; i <= n; i++) {
		if(n1[i].ls != n2[i].ls || n1[i].rs != n2[i].rs) {
			if(!p1) p1 = i;
			else p2 = i;
		}
	}
	if(!p1 && !p2) {
		puts("0");
		return 0;
	}
	puts("1");
	int ans = 0;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			if(i != j && fa1[i] == j && fa2[j] == i) {
				ans = j;
				break;
			}
		}
	}
	cout << ans << endl;
	return 0;
}

1. Zhinai's password

Link: https://ac.nowcoder.com/acm/contest/23478/I
Source: niuke.com

Title Description

Zhinai went to register an account. He found that the password of the website must meet the following conditions

• A password is a string that contains only uppercase and lowercase English letters, numbers, and special symbols.
• The length of the password shall be no less than LL characters and no more than RR characters.
• The password should at least include three of the four types of characters: ① uppercase English letters, ② lowercase English letters, ③ numbers and ④ special symbols.

The so-called special characters refer to the visible characters of invisible characters such as non uppercase and lowercase letters, numbers and space carriage return, including but not limited to "~! @#$% ^ & * () +".

Now zhinai has a string SS with a length of NN. She wants to know how many substrings in the SS string are qualified passwords. Please help zhinai count the number of qualified passwords.

Substring refers to a continuous interval in a string. For example, "ABC" and "CDE" are all substrings of the string "abcde", while "ace" is not its substring.

Enter Description:

Enter three positive integers on the first line N,L,R(1≤N≤105,1≤L≤R≤N)N,L,R(1≤N≤105,1≤L≤R≤N)，express SS The length of the string and the length of the legal password should be LL reach RR Between characters.
On the next line, enter a length of NN String of SS，String includes only①Capital English letters②Lowercase English letters③Numbers④Special symbols are four types of characters.

Output Description:

Only one integer per line indicates how many substrings are a legal password.

Example 1

input

copy

10 6 8
asdfeg111*

output

copy

3

explain

"eg111*","feg111*","dfeg111*"

This question can be done with two pointers or two points. The wrong double pointer written for a long time during the competition can't be changed. There's no way but two points

Each possible right end point is traversed in dichotomy, and the dichotomy is the distance from the right end point of the actual interval to the left end point (because it is satisfied when the distance is small, it must be satisfied when the distance is large, and the solution satisfies monotonicity). Prefix and sum can be used to judge whether the interval is legal. For example, there are intervals 1 2 3 4 5 6, L = 3, R = 6. If [1 2 3 4] is legal, then [1 2 3 4 5] and [1 2 3 4 5 6] must be legal.

Note that the left endpoint will not exceed 1! Be sure to deal with it specially! The code is relatively abstract. Please refer to it briefly~

#include <iostream>
#include <map>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <set>
#include <vector>
#define int long long
#define ll long long
#define pb push_back
#define pii pair<int,int>
using namespace std;
int n, L, R;
char s[200005];
int sum[200005][4] = { 0 };
bool check(int mid, int i) {
	int a = sum[i][0] - sum[mid - 1][0];
	if(a) a = 1;
	int b = sum[i][1] - sum[mid - 1][1];
	if(b) b = 1;
	int c = sum[i][2] - sum[mid - 1][2];
	if(c) c = 1;
	int d = sum[i][3] - sum[mid - 1][3];
	if(d) d = 1;
	if(a + b + c + d >= 3) return 1;
	else return 0;
}
signed main() {
	cin >> n >> L >> R;
	scanf("%s", s + 1);
	int digit = 0, upper = 0, lower = 0, spe = 0;
	int lft = 1;
	int ans = 0;
	int cnt = 0;
	for(int i = 1; i <= n; i++) {
		for(int j = 0; j < 4; j++) {
			sum[i][j] = sum[i - 1][j];
		}
		if(s[i] >= '0' && s[i] <= '9') sum[i][0]++;
        else if(s[i] >= 'a' && s[i] <= 'z') sum[i][1]++;
        else if(s[i] >= 'A' && s[i] <= 'Z') sum[i][2]++;
        else sum[i][3]++;
        if(i < L) continue;
        int l = 0, r = min(R, i) - L, mid;
        while(l < r) {
        	mid = (l + r) >> 1;
        	if(check(i - (mid + L) + 1, i)) r = mid;
        	else l = mid + 1;
        }
        if(check(i - (l + L) + 1, i)) ans += (min(R, i) - (L + l) + 1);//
	}
	cout << ans;
	return 0;
}
// 10 3 5
// a1******1a

// 5 5 5
// a*111

50. Zhinai's database

Link: https://ac.nowcoder.com/acm/contest/23478/L
Source: niuke.com

Title Description

Zhinai is learning the query language SQL of database recently. SQL (Structured Query Language) is used to manage relational database management system (RDBMS). The scope of SQL includes data insertion, query, update and deletion, database schema creation and modification, and data access control.

Using SQL, you can operate the database table flexibly. There is a keyword such as "GROUP BY" in the query statement of the database.

The GROUP BY statement is used to group a result set according to one or more columns in combination with an aggregate function.

For example, such a database Table table is stored in the database, and the query statement with the keyword "GROUP BY" is executed.

id name val 1 chino 1 2 chino
2 3 kokoa
3 SELECT COUNT(*) FROM Table GROUP BY name;

COUNT in SQL statement indicates how many pieces of data are in each group after aggregation.

After executing the above SQL query statement, the returned results are as follows

2 2 1 the 2 in the first line indicates grouping and aggregation according to the name field. A total of 2 groups can be divided.

The two integers in the second row represent how many pieces of data there are in each group.

Of course, the "GROUP BY" keyword can select multiple columns for grouping and aggregation. You only need to separate these fields with commas.

SELECT COUNT(*) FROM Table GROUP BY name,val; For example, the SQL query statement returns the following results after execution

3 1 now zhinai exports this database table to you. Please execute a SELECT COUNT(*) FROM Table GROUP BY; Please tell zhinai the result of the query.

To simplify the problem, we assume that the database table consists of NN records and MM fields, and the types of these fields are int.

Enter Description:

Enter two positive integers on the first line N,M(1≤N,M≤1000)N,M(1≤N,M≤1000)，Indicates that there are in the database table NN Records and MM Fields.


Enter on the next line MM String Si(1≤∣Si∣≤50)Si(1≤∣Si∣≤50)Represents the name of each field.


next NN Line, each line MM Column, enter a 2D table datai,j(0≤datai,j≤109)datai,j(0≤datai,j≤109)Represents the second row in the database table ii Record No jj The value of the first field.


Next, enter a string on each line SQL(1≤∣SQL∣≤5×104)SQL(1≤∣SQL∣≤5×104)，Represents a query statement. The format of the query statement is"SELECT    COUNT(∗)    FROM    Table    GROUP    BY    ...;""SELECTCOUNT(∗)FROMTableGROUPBY...;". 


among"...""..."Is the name of several fields, which is guaranteed to be entered before MM Some of the fields are different from each other, and the fields are separated by a comma.

Output Description:

The first line outputs an integer KK Represents the number of groups after aggregation.
Next line of output KK An integer representing the number of aggregated records in each group, separated by a space.


You can output the answers in the order you like, and the referee program will ignore the influence of the output order.

Example 1

input

copy

4 3
id name val
1 1 2
1 1 3
1 2 1
2 2 2
SELECT COUNT(*) FROM Table GROUP BY name,id;

output

copy

3
1 2 1

Simulation questions. The idea is to sort by these fields, and then the adjacent fields with the same value can be divided into a group.

#include <iostream>
#include <map>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <set>
#include <vector>
#define ll long long
#define pb push_back
#define pii pair<int,int>
using namespace std;
struct node {
	int data[1005];
} p[1005];
int rela[1005], cnt = 0;
bool cmp(node a, node b) {
	for(int i = 1; i <= cnt; i++) {
		if(a.data[rela[i]] == b.data[rela[i]]) continue;
		else return a.data[rela[i]] < b.data[rela[i]];
	}
	return a.data[rela[cnt]] < b.data[rela[cnt]];
}
int n, m;
string s[1005];
string sen;
map<string, int> mp;
int main() {
	cin >> n >> m;
	for(int i = 1; i <= m; i++) {
		cin >> s[i];
		mp[s[i]] = i;
	}
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			cin >> p[i].data[j];
		}
	}
	getchar();
	getline(cin, sen);
	int pos = sen.find("BY");
	pos += 3;
	int lst = pos;
	for(int i = pos; i < sen.size(); i++) {
		if(sen[i] == ',' || sen[i] == ';') {
			string tmp = sen.substr(lst, i - lst);
			lst = i + 1;
			cnt++;
			rela[cnt] = mp[tmp];
		}
	}
	sort(p + 1, p + n + 1, cmp);
	int num = 1;
	vector<int> ans;
	for(int i = 2; i <= n + 1; i++) {
		bool diff = 0;
		for(int j = 1; j <= cnt; j++) {
			if(p[i].data[rela[j]] != p[i - 1].data[rela[j]]) {
				diff = 1;
				break;
			}
		}
		if(diff) {
			ans.push_back(num);
			num = 1;
		} else {
			num++;
		}
	}
	cout << ans.size() << endl;
	for(int i = 0; i < ans.size() - 1; i++) {
		cout << ans[i] << " ";
	}
	cout << ans[ans.size() - 1];
	return 0;
}