8618: Three Body

"The fish who dried the sea went onto land before they did this. They move from one dark forest to another dark forest."

You are now in a $K$-dimensional universe, which could be seen as an n1×n2×...×nKn_1\times n_2 \times ... \times n_Kn1×n2×...×nK hyperrectangle. To be specific, let's divide the universe into n1×n2×...×nKn_1\times n_2 \times ... \times n_Kn1×n2×...×nK hypercubes sized $1\times 1\times ...\times 1$ to describe different regions. The position of each region can be denoted by a $K$-dimensional integer coordinate (a1,a2,...,aK)(a_1, a_2, ..., a_K)(a1,a2,...,aK) where 0≤ai<ni0 \le a_i < n_i0≤ai<ni. Each region owns a $\text{Dimensional Value}$ and the initial value is $K$. However, due to the space war and the abuse of dimensionality weapons, the $\text{Dimensional Values}$ of some regions in the universe has decayed to less than $K$.

Your spaceship is an m1×m2×...×mKm_1\times m_2 \times ... \times m_Km1×m2×...×mK hyperrectangle which can also be viewed as m1×m2×...×mKm_1\times m_2 \times ... \times m_Km1×m2×...×mK parts of hypercubes sized $1\times 1\times ...\times 1$. The position of each part can also be denoted by a $K$-dimensional integer coordinate (b1,b2,...,bK)(b_1, b_2, ..., b_K)(b1,b2,...,bK) where 0≤bi<mi0 \le b_i < m_i0≤bi<mi. Each part of your spaceship also owns a $\text{Dimensional Value}$ which is initially $K$. Thanks to advanced technology, some parts of your spaceship are reformed and their $\text{Dimensional Values}$ become less than $K$, which can make them enter the regions with lower $\text{Dimensional Values}$.

We define the spaceship to be in a valid position if the following conditions are met:

• Each part of the spaceship is located exactly in one region.
• Each part of the spaceship cannot have a $\text{Dimensional Value}$ strictly higher than the $\text{Dimensional Value}$ of the region.

Please calculate the number of different valid positions for your spaceship. Please note that you can't rotate the spaceship.

The first line contains an integer $K$ (2≤K≤52\le K\le 52≤K≤5).
The second line contains $K$ integers n1,n2,...,nKn_1,n_2,...,n_Kn1,n2,...,nK (1≤∏i=1Kni≤3×1051\le \prod_{i=1}^{K}n_i\le 3\times 10^51≤∏i=1Kni≤3×105), indicating the size of the universe.
The third line is an integer cuc_ucu (0≤cu≤∏i=1Kni0\le c_u\le \prod_{i=1}^{K}n_i0≤cu≤∏i=1Kni), indicating the number of regions whose $\text{Dimensional Value}$ has decayed.
Each of the following cuc_ucu lines contains K+1K+1K+1 integers a1,a2,...,aKa_1,a_2,...,a_Ka1,a2,...,aK and $d$ (0≤ai<ni0 \le a_i < n_i0≤ai<ni, $1\le d<K$), indicating that the $\text{Dimensional Value}$ of region (a1,a2,...,aK)(a_1,a_2,...,a_K)(a1,a2,...,aK) has decayed to $d$. It is guaranteed that the cuc_ucu regions are pairwise different.
The next line contains $K$ integers m1,m2,...,mKm_1,m_2,...,m_Km1,m2,...,mK (1≤mi<ni1 \le m_i <n_i1≤mi<ni), indicating the size of the spaceship.
The next line contains an integer csc_scs (0≤cs≤∏i=1Kmi0\le c_s\le \prod_{i=1}^{K}m_i0≤cs≤∏i=1Kmi), indicating the number of parts of the spaceship are reformed.
Each of the following csc_scs lines contains K+1K+1K+1 integers b1,b2,...,bKb_1,b_2,...,b_Kb1,b2,...,bK and $d$ (0≤bi<mi0 \le b_i < m_i0≤bi<mi, $1\le d<K$), indicating that the $\text{Dimensional Value}$ of part (b1,b2,...,bK)(b_1,b_2,...,b_K)(b1,b2,...,bK) becomes $d$. It is guaranteed that the csc_scs parts are pairwise different.

Output one integer indicating the number of different valid positions for your spaceship.

2
4 4
7
0 0 1
1 0 1
1 2 1
2 0 1
2 1 1
2 3 1
3 3 1
2 2
1
1 1 1

1