Game Developer Seunghee
Time limit1sMemory limit1024 MB
Perform M operations on sequence A, each adding Bi to all elements then deleting multiples of 7 unless that would empty the sequence, and report the final sequence modulo 1e9+7.
- Level
Hard8 of 10
- Topics
- Math, Number theory, Implementation, Simulation
- Solved
- No attempts yet
Problem
Seunghee recently became obsessed with the 369 game. While playing it, Seunghee was left stunned. Seunghee was proud of being so good at the 369 game. Once the 369 game grew stale, Seunghee developed the 71421 game, a variation of it. In the 369 game you clap for numbers containing 3, 6, or 9, but in the 71421 game you clap for multiples of 7. Seunghee decided to spread the 71421 game far and wide.
The 71421 game has recently become very popular among university students. Once the 71421 game grew stale as well, Seunghee developed a new game using sequences.
Seunghee's sequence game is a fun game you can enjoy alone. Before starting, you prepare a sequence A of length N and a sequence B of length M. Then you perform M operations on sequence A. The i-th operation (1 ≤ i ≤ M) adds Bi to every element of sequence A and then removes the elements that are multiples of 7. However, if performing the operation would remove every element of sequence A, that operation is not performed.
Given sequences A and B, write a program that computes the result of performing the M operations.
Input
The first line gives the length N of sequence A and the length M of sequence B.
The second line gives N integers A1, A2, ..., AN.
The third line gives M integers B1, B2, ..., BM.
All input is separated by spaces.
Output
On the first line, print the length K of sequence A after performing the M operations.
On the second line, print the K integers A1, A2, ..., AK separated by spaces. The answer can become very large, so print them modulo 109 + 7.
Constraints
- 1 ≤ N, M ≤ 100,000
- 1 ≤ Ai, Bi ≤ 1,000,000,000
Hint
The amount of input and output is large, so using fast input and output is recommended.