Three Lines

Professor Pang has n rectangles. The i-th rectangle is given by its lower‐left corner \( (x_{i,1},y_{i,1}) \) and its upper‐right corner \( (x_{i,2},y_{i,2}) \). Note that the rectangles may overlap.

You are required to choose three distinct lines; each line is either vertical of the form \( x=a \) or horizontal of the form \( y=a \), where \( a \) is an integer satisfying \( 1\le a\le10^9 \). The chosen three lines (order does not matter) have to satisfy the condition that every rectangle is touched by at least one line. A line touches a rectangle if it intersects its boundary and/or its interior.

More formally, if you choose a set \( L \) of three lines (each either \( x=a \) or \( y=a \)), then for every rectangle \( i \) the following must hold: at least one of the vertical lines (if any) has its coordinate \( a \) satisfying \( x_{i,1}\le a\le x_{i,2} \) or at least one of the horizontal lines (if any) has its coordinate \( a \) satisfying \( y_{i,1}\le a\le y_{i,2} \).

Your task is to count the number of ways to choose three lines satisfying the above condition. Since the answer can be very large, output it modulo \( 998244353 \).

Note: Two ways are considered the same if they only differ in the order of the lines.

inputFormat

The first line contains a single integer \( n \) \( (1\le n\le 15) \) denoting the number of rectangles.

Each of the next \( n \) lines contains four integers \( x_{i,1}\), \( y_{i,1}\), \( x_{i,2}\), \( y_{i,2} \) \( (1\le x_{i,1}\le x_{i,2}\le10^9,\ 1\le y_{i,1}\le y_{i,2}\le10^9) \) describing a rectangle.

outputFormat

Output a single integer which is the number of ways to choose three lines so that every rectangle is touched by at least one of these lines, modulo \( 998244353 \).

sample

1
1 1 1 1

133464247