D. Virtuous Pope
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

"Take this, DIO! 20-meter radius Emerald Splash—!"

The Stardust Crusaders, after overcoming countless obstacles and repelling waves of enemies, finally arrived in Egypt for their ultimate confrontation with Dio. Facing Dio, their strategy involved Joseph Joestar and Kakyoin engaging in tactical retreats while fighting, while Kujo Jotaro and Polnareff pursued from the rear, forming a pincer attack. Amidst the chaos, Kakyoin devised a plan to uncover the abilities of Dio's Stand "The World", by setting traps across nearby structures.

As Dio pursued Kakyoin, he became ensnared in the barrier deployed by Kakyoin's Hierophant Green. The ensuing confrontation unleashed a concentrated barrage of Emerald Splash attacks...

Kakyoin has deployed a barrier of "Hierophant Green" within a cuboid region. For calculation purposes, we place the cuboid in a Cartesian coordinate system, with one vertex at the origin $$$(0,0,0)$$$ and the opposite vertex at $$$(a,b,c)$$$, where $$$a$$$, $$$b$$$, and $$$c$$$ represent the length, width, and height of the cuboid respectively. The barrier contains several tentacles, each defined as a line segment from $$$(x_1,y_1,z_1)$$$ to $$$(x_2,y_2,z_2)$$$, where both endpoints lie on the boundary of the cuboid.

Dio may appear at any position within the cuboid (including boundaries). According to the plan, Dio will execute a single attack by generating an infinitely large plane perpendicular to one of the coordinate axes ($$$x-$$$, $$$y-$$$, or $$$z-$$$ axis) and centered at his position. All tentacles intersecting Dio's attack range (i.e., there exists a point that lies on both the tentacle and Dio's attack plane) will be severed. Each severed tentacle will launch an Emerald Splash attack against Dio exactly once.

Kakyoin wants to determine: What is the maximum number of Emerald Splash attacks Dio could receive considering all possible positions he might occupy and all valid attack directions after the barrier is deployed?

Formalized statement: Given $$$n$$$ line segments in three-dimensional space with their endpoints restricted to a given cuboid, determine the maximum number of segments intersected by any plane that is perpendicular to one of the coordinate axes. A line segment is considered to intersect a plane if and only if there exists a point that lies on both the line segment and the plane.

Input

The first line contains four integers $$$n,a,b,c$$$ ($$$1 \leq n \leq 10^5,1 \leq a, b, c \leq 10^9$$$):

  • $$$n$$$: number of "Hierophant Green" 's tentacles;
  • $$$a$$$, $$$b$$$, $$$c$$$: dimensions of the cuboid (length, width, height).
The next $$$n$$$ lines each contain six integers $$$x_1,y_1,z_1,x_2,y_2,z_2$$$ ($$$0 \leq x_1, x_2 \leq a,0 \leq y_1, y_2 \leq b,0 \leq z_1, z_2 \leq c$$$), describing coordinates of the two endpoints $$$(x_1,y_1,z_1)$$$ and $$$(x_2,y_2,z_2)$$$ for each tentacle. All endpoints lie on the cuboid's surface.
Output

Output a single integer: the maximum number of Emerald Splash attacks Dio could receive.

Examples
Input
3 2 2 2
1 1 0 1 1 2
1 0 1 1 2 1
0 1 1 2 1 1
Output
3
Input
4 10 4 10
0 4 6 6 4 4
10 2 10 8 4 4
0 4 0 2 4 0
0 0 10 0 2 10
Output
3
Note

For Sample 1: When Dio's attack plane is set to $$$x=1$$$, he will receive 3 Emerald Splash attacks.

For Sample 2: When Dio's attack plane is $$$x=0$$$, he will receive 3 attacks.