Problem Statement

A train has n compartments numbered from 1 to n. Each compartment requires a set of items, where item numbers range from 1 to m. A vendor named Alice is assigned to any continuous sequence of compartments to sell goods. For any such sequence, she must prepare all items required by those compartments and create a unique chant for them. The task is to calculate how many different chants Alice needs to prepare for all possible continuous compartment sequences.

Input Format

The first line contains two integers n (1 ≤ n ≤ 2×10^5) and m (1 ≤ m ≤ 100), representing the number of compartments and maximum item number.

Following n lines, each line describes a compartment. The i-th line starts with an integer k_i (1 ≤ k_i ≤ m), indicating the number of items needed in compartment i-1. Then k_i integers follow, representing the required item numbers. All item numbers are within [1, m] and distinct within the same compartment. The sum of all k_i does not exceed 10^6.

Output Format

Output a single integer representing the number of different chants required.

Example

Input:

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

Output:

8

Explanation:

The 8 unique item sets for all continuous compartment sequences are:

{1}, {1,2}, {1,2,4,5}, {1,2,3,4,5}, {4,5}, {1,4,5}, {1,2,3}, {2,3}

Naive Approach and Its Limitations

A straightforward solution would generate all possible continuous compartment sequences (O(n^2) combinations), merge their item sets, and count unique combinations using a hash table. However, this approach fails with large n (up to 2×10^5) due to O(n^2) time complexity.

Optimized Solution

The optimized solution leverages preprocessing and bit manipulation to achieve better performance:

1. Preprocessing: For each item, track its last occurrence position. For each compartment, determine the next occurrence of each item.
2. Bit Representation: Use 128-bit integers (__int128_t) to efficiently represent item sets as bitmasks.
3. Deduplication: Sort items by their next occurrence and use a set to store unique bitmasks.

C++ Implementation

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

int n, m;
bool hasItem[200005][105];
int lastPos[105];
pii nextPos[200005][105];
set<__int128_t> uniqueMasks;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> m;
    
    // Read compartment requirements
    for (int i = 1; i <= n; i++) {
        int k;
        cin >> k;
        while (k--) {
            int item;
            cin >> item;
            hasItem[i][item] = true;
        }
    }
    
    // Initialize last positions
    for (int i = 1; i <= m; i++) {
        lastPos[i] = 300000;
    }
    
    // Preprocess next occurrence positions
    for (int i = n; i >= 1; i--) {
        for (int j = 1; j <= m; j++) {
            if (hasItem[i][j]) lastPos[j] = i;
            nextPos[i][j] = {lastPos[j], j};
        }
    }
    
    // Generate unique bitmasks
    for (int i = 1; i <= n; i++) {
        sort(nextPos[i]+1, nextPos[i]+1+m);
        __int128_t currentMask = 0;
        
        for (int j = 1; j <= m; j++) {
            if (nextPos[i][j].first == 300000) break;
            
            int pos = nextPos[i][j].first;
            while (nextPos[i][j].first == pos && j <= m) {
                currentMask |= ((__int128_t)1 << nextPos[i][j].second);
                j++;
            }
            j--;
            uniqueMasks.insert(currentMask);
        }
    }
    
    cout << uniqueMasks.size() << endl;
    return 0;
}

Key Optimization Techniques

1. Preprocessing: By preprocessing next occurrence positions, we avoid repeated calculations during sequence generation.
2. Bit Manipulation: Using __int128_t allows efficient representation of item sets as bitmasks, reducing memory usage and improving comparison speed.
3. Early Termination: Sorting items by next occurrence enables early termination when items won't appear in current or future sequences.

Complexity Analysis

• Time Complexity: O(n × m log m) due to sorting operations for each compartment.
• Space Complexity: O(n × m) for storing preprocessing data and unique masks.