All Tracks Data Structures Advanced Data Structures Trie (Keyword Tree) Problem

Sa Re Ga Ma

Prime Factorization, Tries


Once there was a series of blasts which took place around \(8\) years ago in BINverse. There was something very strange about that incident. The bombs went off following a musical progression. This incident destroyed half of BINverse and the person behind this incident was never caught. After a few hours of the incident, a video was released by the organisation The Eye of the Midnight Sun taking the responsibility. That's when the name Lord Musical Dosa was revealed. It is believed that Dosa was very much fond of music when the organisation found him. They saw a sense of madness, love and passion in him. 

Recently, BITverse Research Organisation (BRO) received an anonymous tip related to Lord Musical Dosa. Dosa has planted sequence-triggered bombs all across BITverse. After some investigation, \(2\) bombs were found. In the analysis report following inferences were made - 

  1. The sequence which will trigger a bomb will be a valid musical progression. The sequence will not be some random combination of musical notes.
  2. The bomb works on the principle of nuclear bombs. If the power of the musical progression  \(P\) is used to trigger the bomb then the bomb disintegrates into prime-factors of \(P\)reintegrates and blasts again.
  3. To disable a bomb, one needs to attack it with strength \(S\) such that the number of prime factors of \(S \ge P\) so that all bomb particles are destroyed.

According to the music theory, there are 12 notes in Chromatic Scale. \(\{a, a\#, b, c, c\#, d, d\#, e, f, f\#, g, g\#\}\) \(\)A progression is formed by using these notes in a particula order. All the progressions, \(N\), which currently exists are known along with their power \(P\)

Over time, all the bombs were located and SuperBhalu was contacted to disable all the bombs. When he arrived, he saw that the sequence visible on the bombs were not complete yet. They were prefix of the actual sequence. Now Bhalu is confused. He does not know with what strength he needs to attack.

You are the only coder in BITverse. Help SuperBhalu find the strength with which he needs to attack each bomb.


First-line contains \(N\) and \(T\), the number of progressions known and the number of bombs located.

Each of the next \(N\) lines contains \(P\), power of the progression, \(L\), length of the progression and \(L\) space-separated progression notes

Next \(T\) lines contain the length of the prefix on the bomb, \(l\), and \(l\) space-separated progression notes prefix.


For each bomb, print the strength(if two power \(P1 \) and \(P2 \) have same number of factors then strength \(S = max(P1, P2)\) with which SuperBhalu needs to attack.


\(1 \le N \le 10^6\)

\(1 \le T \le 5 * 10^5\)

\(2 \le P \le 5 * 10^6\)

Sum of \(L\) over \(N\) will not exceed \(5 * 10^6\)



4 2
8 4 b c f g#
24 4 b c d f#
16 4 b c d# e
45 3 a b g#
2 b c
1 a

Prefix b c is common for first 3 progression.

number of factors for 8 = 3 (2 * 2 * 2)

number of factors for 24 = 4 (2 * 2 * 2 * 3)

number of factors for 16 = 4 (2 * 2 * 2 * 2)

But 24 > 16

Time Limit: 3.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems


Initializing Code Editor...
View All Notifications