提示: 欢迎访问OurACM平台。
Problem 1981 Three kingdoms

Accept: 110    Submit: 643
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Romance of The Three Kingdoms is one of the great Chinese classics and is compiled into a semi-fictional literary masterpiece during the Ming Dynasty by Luo Guanzhong. The novel comprises around 70+% fact and 20+% fiction. Some issues such as Guan Yu's weapon weighing around 40+ kilograms, the capability of Lu Bu, Liu Bei's horses as well as the existence of the Valley of the Fallen Phoenix and some others are probably fictional.

That period in history can be said as the golden age of chivalry and although it happened more than 1700 years ago, characters such as Liu Bei, Guan Yu, Zhang Fei, Zhuge Liang and Cao Cao have become household names among Chinese. There are many movies and games' background based on the story.

Many wars occur between different armies. Bob is one of the Three Kingdoms fans. One light, he dreams he was Cao Cao. But it is not a sweet dream. A strong Army invades his country. The number of soldiers in the army is N (0<N≤10,000). Bob is so worried that he convenes all his M (0<M≤10,000) crossbowmen on the wall.

Each crossbowman has only one arrow. Bob orders them to shoot in the same direction V (vx, vy, vz). So many enemy soldiers are shot by arrows and die. Then he opens the gate to make a big fight with the left enemy soldiers. Finally he achieves victory. Bob wants to know the number of enemy soldiers who are shot by his crossbowmen. The arrow is so sharp that it can still fly in the same direction after shooting somebody. There may be more than one people in the same position. If many enemy soldiers stand in the same position, they may be shot at a time. If an enemy soldier and a crossbowman stand in the same position, the enemy soldier will also be shot.

Input

The first line of the input contains an integer T (T≤10), indicating the number of cases. Each case begins with a line containing two integers N and M (0<N, M≤10,000). Each of the following N lines contains three integers xi, yi and zi (|xi|, |yi|, |zi|≤100,000, 1≤i≤N), the coordinate of the i-th soldier is (xi, yi, zi). Each of the following M lines contains three integers xi, yi and zi (|xi|, |yi|, |zi|≤100,000, 1≤i≤M), the coordinate of the i-th crossbowman is (xi, yi, zi). The next line contains three integers vx, vy and vz (0<|vx|+|vy|+|vz|≤300,000), the direction in which all the crossbowmen shot their arrows.

Output

For each test case, print a line containing the test case number (beginning with 1) and the number of enemy soldiers who are shot by Bob’s crossbowmen.

Sample Input

2 1 1 1 1 1 0 0 0 1 1 1 2 1 2 1 1 4 2 2 0 0 0 2 1 1

Sample Output

Case 1: 1 Case 2: 2

Source

The 35th ACM/ICPC Asia Regional Fuzhou Site —— Online Contest

Submit  Back  Status  Discuss