static VECTOR2I pushoutForce( const SHAPE_CIRCLE& aA, const SEG& aB, int aClearance )
{
    VECTOR2I f( 0, 0 );

    const VECTOR2I c = aA.GetCenter();
    const VECTOR2I nearest = aB.NearestPoint( c );

    const int r = aA.GetRadius();

    int dist = ( nearest - c ).EuclideanNorm();
    int min_dist = aClearance + r;

    if( dist < min_dist )
    {
        for( int corr = 0; corr < 5; corr++ )
        {
            f = ( aA.GetCenter() - nearest ).Resize( min_dist - dist + corr );

            if( aB.Distance( c + f ) >= min_dist )
                break;
        }
    }

    return f;
}

void solve()
{
	int N, Q, cmd, p, q;
	ll val;
	scanf("%d %d",&N, &Q);
 
	SEG st = SEG(N);
 
	for(int i = 0; i < Q; i++)
	{
		scanf("%d",&cmd);
		if(cmd == 0)
		{
			scanf("%d %d %lld",&p, &q, &val);
			//cout << p << " " << q << val << endl;
			st.update(p-1,q-1,val);
		}
		else
		{
			scanf("%d %d",&p, &q);
			printf("%lld\n",st.query(p-1,q-1));
		}
	}
 
	return;
}

int SHAPE_LINE_CHAIN::Split( const VECTOR2I& aP )
{
    int ii = -1;
    int min_dist = 2;

    ii = Find( aP );

    if( ii >= 0 )
        return ii;

    for( int s = 0; s < SegmentCount(); s++ )
    {
        const SEG seg = CSegment( s );
        int dist = seg.Distance( aP );

        // make sure we are not producing a 'slightly concave' primitive. This might happen
        // if aP lies very close to one of already existing points.
        if( dist < min_dist && seg.A != aP && seg.B != aP )
        {
            min_dist = dist;
            ii = s;
        }
    }

    if( ii >= 0 )
    {
        m_points.insert( m_points.begin() + ii + 1, aP );

        return ii + 1;
    }

    return -1;
}

VECTOR2I GRID_HELPER::AlignToSegment ( const VECTOR2I& aPoint, const SEG& aSeg )
{
    OPT_VECTOR2I pts[6];

    const VECTOR2D gridOffset( GetOrigin() );
    const VECTOR2D gridSize( GetGrid() );

    VECTOR2I nearest( KiROUND( ( aPoint.x - gridOffset.x ) / gridSize.x ) * gridSize.x + gridOffset.x,
                      KiROUND( ( aPoint.y - gridOffset.y ) / gridSize.y ) * gridSize.y + gridOffset.y );

    pts[0] = aSeg.A;
    pts[1] = aSeg.B;
    pts[2] = aSeg.IntersectLines( SEG( nearest, nearest + VECTOR2I( 1, 0 ) ) );
    pts[3] = aSeg.IntersectLines( SEG( nearest, nearest + VECTOR2I( 0, 1 ) ) );

    int min_d = std::numeric_limits<int>::max();

    for( int i = 0; i < 4; i++ )
    {
        if( pts[i] && aSeg.Contains( *pts[i] ) )
        {
            int d = (*pts[i] - aPoint).EuclideanNorm();

            if( d < min_d )
            {
                min_d = d;
                nearest = *pts[i];
            }
        }
    }

    return nearest;
}

/**
 * Predicate to check expected distance between two segments
 * @param  aSegA the first #SEG
 * @param  aSegB the second #SEG
 * @param  aExp  expected distance
 * @return       does the distance calculated agree?
 */
bool SegDistanceCorrect( const SEG& aSegA, const SEG& aSegB, int aExp )
{
    const int AtoB = aSegA.Distance( aSegB );
    const int BtoA = aSegB.Distance( aSegA );

    bool ok = ( AtoB == aExp ) && ( BtoA == aExp );

    if( AtoB != BtoA )
    {
        std::stringstream ss;
        ss << "Segment distance is not the same in both directions: expected " << aExp << ", got "
           << AtoB << " & " << BtoA;
        BOOST_TEST_INFO( ss.str() );
    }
    else if( !ok )
    {
        std::stringstream ss;
        ss << "Distance incorrect: expected " << aExp << ", got " << AtoB;
        BOOST_TEST_INFO( ss.str() );
    }

    // Sanity check: the collision should be consistent with the distance
    ok = ok && SegCollideCorrect( aSegA, aSegB, 0, aExp == 0 );

    return ok;
}

bool BOARD::TestAreaIntersection( ZONE_CONTAINER* area_ref, ZONE_CONTAINER* area_to_test )
{
    // see if areas are on same layer
    if( area_ref->GetLayer() != area_to_test->GetLayer() )
        return false;

    SHAPE_POLY_SET* poly1 = area_ref->Outline();
    SHAPE_POLY_SET* poly2 = area_to_test->Outline();

    // test bounding rects
    BOX2I b1 = poly1->BBox();
    BOX2I b2 = poly2->BBox();

    if( ! b1.Intersects( b2 ) )
        return false;

    // Now test for intersecting segments
    for( auto segIterator1 = poly1->IterateSegmentsWithHoles(); segIterator1; segIterator1++ )
    {
        // Build segment
        SEG firstSegment = *segIterator1;

        for( auto segIterator2 = poly2->IterateSegmentsWithHoles(); segIterator2; segIterator2++ )
        {
            // Build second segment
            SEG secondSegment = *segIterator2;

            // Check whether the two segments built collide
            if( firstSegment.Collide( secondSegment, 0 ) )
                return true;
        }
    }

    // If a contour is inside another contour, no segments intersects, but the zones
    // can be combined if a corner is inside an outline (only one corner is enough)
    for( auto iter = poly2->IterateWithHoles(); iter; iter++ )
    {
        if( poly1->Contains( *iter ) )
            return true;
    }

    for( auto iter = poly1->IterateWithHoles(); iter; iter++ )
    {
        if( poly2->Contains( *iter ) )
            return true;
    }

    return false;
}

bool SHAPE_ARC::Collide( const SEG& aSeg, int aClearance ) const
{
    int minDist = aClearance + m_width / 2;
    auto centerDist = aSeg.Distance( m_pc );
    auto p1 = GetP1();

    if( centerDist < minDist )
        return true;

    auto ab = (aSeg.B - aSeg.A );
    auto ac = ( m_pc - aSeg.A );

    auto lenAbSq = ab.SquaredEuclideanNorm();

    auto lambda = (double) ac.Dot( ab ) / (double) lenAbSq;


    if( lambda >= 0.0 && lambda <= 1.0 )
    {
        VECTOR2I p;

        p.x = (double) aSeg.A.x * lambda + (double) aSeg.B.x * (1.0 - lambda);
        p.y = (double) aSeg.A.y * lambda + (double) aSeg.B.y * (1.0 - lambda);

        auto p0pdist = ( m_p0 - p ).EuclideanNorm();

        if( p0pdist < minDist )
            return true;

        auto p1pdist = ( p1 - p ).EuclideanNorm();

        if( p1pdist < minDist )
            return true;
    }

    auto p0dist = aSeg.Distance( m_p0 );

    if( p0dist > minDist )
        return true;

    auto p1dist = aSeg.Distance( p1 );

    if( p1dist > minDist )
        return false;


    return true;
}

void EC_CONVERGING::Apply( EDIT_LINE& aHandle )
{
    // The dragged segment endpoints
    EDIT_POINT& origin = aHandle.GetOrigin();
    EDIT_POINT& end = aHandle.GetEnd();

    if( m_colinearConstraint )
    {
        m_colinearConstraint->Apply( origin );
        m_colinearConstraint->Apply( end );
    }

    // The dragged segment
    SEG dragged( origin.GetPosition(), origin.GetPosition() + m_draggedVector );

    // Do not allow points on the adjacent segments move freely
    m_originSideConstraint->Apply();
    m_endSideConstraint->Apply();

    EDIT_POINT& prevOrigin = *m_editPoints.Previous( origin, false );
    EDIT_POINT& nextEnd = *m_editPoints.Next( end, false );

    // Two segments adjacent to the dragged segment
    SEG originSide = SEG( origin.GetPosition(), prevOrigin.GetPosition() );
    SEG endSide = SEG( end.GetPosition(), nextEnd.GetPosition() );

    // First intersection point (dragged segment against origin side)
    if( OPT_VECTOR2I originIntersect = dragged.IntersectLines( originSide ) )
        origin.SetPosition( *originIntersect );

    // Second intersection point (dragged segment against end side)
    if( OPT_VECTOR2I endIntersect = dragged.IntersectLines( endSide ) )
        end.SetPosition( *endIntersect );

    // Check if adjacent segments intersect (did we dragged the line to the point that it may
    // create a selfintersecting polygon?)
    originSide = SEG( origin.GetPosition(), prevOrigin.GetPosition() );
    endSide = SEG( end.GetPosition(), nextEnd.GetPosition() );

    if( OPT_VECTOR2I originEndIntersect = endSide.Intersect( originSide ) )
    {
        origin.SetPosition( *originEndIntersect );
        end.SetPosition( *originEndIntersect );
    }
}

bool SHAPE_LINE_CHAIN::PointOnEdge( const VECTOR2I& aP ) const
{
    if( SegmentCount() < 1 )
        return m_points[0] == aP;

    for( int i = 1; i < SegmentCount(); i++ )
    {
        const SEG s = CSegment( i );

        if( s.A == aP || s.B == aP )
            return true;

        if( s.Distance( aP ) <= 1 )
            return true;
    }

    return false;
}

VECTOR2I PNS_LINE::snapToNeighbourSegments( const SHAPE_LINE_CHAIN& aPath, const VECTOR2I &aP,
                                            int aIndex, int aThreshold ) const
{
    VECTOR2I snap_p[2];
    DIRECTION_45 dragDir( aPath.CSegment( aIndex ) );
    int snap_d[2] = { -1, -1 };

    if( aThreshold == 0 )
        return aP;

    if( aIndex >= 2 )
    {
        SEG s = aPath.CSegment( aIndex - 2 );

        if( DIRECTION_45( s ) == dragDir )
            snap_d[0] = s.LineDistance( aP );

        snap_p[0] = s.A;
    }

    if( aIndex < aPath.SegmentCount() - 2 )
    {
        SEG s = aPath.CSegment( aIndex + 2 );

        if( DIRECTION_45( s ) == dragDir )
            snap_d[1] = s.LineDistance(aP);

        snap_p[1] = s.A;
    }

    VECTOR2I best = aP;
    int minDist = INT_MAX;

    for( int i = 0; i < 2; i++ )
    {
        if( snap_d[i] >= 0 && snap_d[i] < minDist && snap_d[i] <= aThreshold )
        {
            minDist = snap_d[i];
            best = snap_p[i];
        }
    }

    return best;
}

void fresh( SEG &T,SEG &L,SEG &R ) {
    int i,j,x,y;
    memset(T.V,0,sizeof T.V);
    for(j=0;j<3;j++)
        for(x=0;x<3;x++)if(g[j][x])
            for(i=0;i<3;i++)
                for(y=0;y<3;y++)
                    T.V[i][y]+=L.V[i][j]*R.V[x][y]%MOD;
    T.fresh();
}

int SHAPE_LINE_CHAIN::PathLength( const VECTOR2I& aP ) const
{
    int sum = 0;

    for( int i = 0; i < SegmentCount(); i++ )
    {
        const SEG seg = CSegment( i );
        int d = seg.Distance( aP );

        if( d <= 1 )
        {
            sum += ( aP - seg.A ).EuclideanNorm();
            return sum;
        }
        else
            sum += seg.Length();
    }

    return -1;
}

bool SHAPE_LINE_CHAIN::CheckClearance( const VECTOR2I& aP, const int aDist) const
{
    if( !PointCount() )
        return false;

    else if( PointCount() == 1 )
        return m_points[0] == aP;

    for( int i = 0; i < SegmentCount(); i++ )
    {
        const SEG s = CSegment( i );

        if( s.A == aP || s.B == aP )
            return true;

        if( s.Distance( aP ) <= aDist )
            return true;
    }

    return false;
}

static VECTOR2I pushoutForce( const SHAPE_CIRCLE& aA, const SEG& aB, int aClearance )
{
    VECTOR2I nearest = aB.NearestPoint( aA.GetCenter() );
    VECTOR2I f (0, 0);

    int dist = ( nearest - aA.GetCenter() ).EuclideanNorm();
    int min_dist = aClearance + aA.GetRadius();

    if( dist < min_dist )
        f = ( aA.GetCenter() - nearest ).Resize ( min_dist - dist + 10 );

    return f;
}

/**
 * Predicate to check expected collision between two segments
 * @param  aSegA the first #SEG
 * @param  aSegB      the second #SEG
 * @param  aClearance the collision clearance
 * @param  aExp  expected collision
 * @return       does the distance calculated agree?
 */
bool SegCollideCorrect( const SEG& aSegA, const SEG& aSegB, int aClearance, bool aExp )
{
    const bool AtoB = aSegA.Collide( aSegB, aClearance );
    const bool BtoA = aSegB.Collide( aSegA, aClearance );

    const bool ok = ( AtoB == aExp ) && ( BtoA == aExp );

    if( AtoB != BtoA )
    {
        std::stringstream ss;
        ss << "Segment collision is not the same in both directions: expected " << aExp << ", got "
           << AtoB << " & " << BtoA;
        BOOST_TEST_INFO( ss.str() );
    }
    else if( !ok )
    {
        std::stringstream ss;
        ss << "Collision incorrect: expected " << aExp << ", got " << AtoB;
        BOOST_TEST_INFO( ss.str() );
    }

    return ok;
}

/**
 * Predicate to check expected distance between a segment and a point
 * @param  aSegA the segment
 * @param  aVec  the vector (point)
 * @param  aExp  expected distance
 * @return       does the distance calculated agree?
 */
bool SegVecDistanceCorrect( const SEG& aSeg, const VECTOR2I& aVec, int aExp )
{
    const int dist = aSeg.Distance( aVec );

    bool ok = ( dist == aExp );

    if( !ok )
    {
        std::stringstream ss;
        ss << "Distance incorrect: expected " << aExp << ", got " << dist;
        BOOST_TEST_INFO( ss.str() );
    }

    return ok;
}

const VECTOR2I SHAPE_LINE_CHAIN::NearestPoint( const SEG& aSeg, int& dist ) const
{
    int nearest = 0;

    dist = INT_MAX;
    for( int i = 0; i < PointCount(); i++ )
    {
        int d = aSeg.LineDistance( CPoint( i ) );

        if( d < dist )
        {
            dist = d;
            nearest = i;
        }
    }

    return CPoint( nearest );
}

PNS_WALKAROUND::WalkaroundStatus PNS_WALKAROUND::Route( const PNS_LINE& aInitialPath,
        PNS_LINE& aWalkPath,
        bool aOptimize )
{
    PNS_LINE path_cw( aInitialPath ), path_ccw( aInitialPath );
    WalkaroundStatus s_cw = IN_PROGRESS, s_ccw = IN_PROGRESS;
    SHAPE_LINE_CHAIN best_path;

    start( aInitialPath );

    m_currentObstacle[0] = m_currentObstacle[1] = nearestObstacle( aInitialPath );
    m_recursiveBlockageCount = 0;

    aWalkPath = aInitialPath;

    while( m_iteration < m_iteration_limit )
    {
        if( s_cw != STUCK )
            s_cw = singleStep( path_cw, true );

        if( s_ccw != STUCK )
            s_ccw = singleStep( path_ccw, false );

        if( ( s_cw == DONE && s_ccw == DONE ) || ( s_cw == STUCK && s_ccw == STUCK ) )
        {
            int len_cw  = path_cw.GetCLine().Length();
            int len_ccw = path_ccw.GetCLine().Length();

            if( m_forceLongerPath )
                aWalkPath = (len_cw > len_ccw ? path_cw : path_ccw);
            else
                aWalkPath = (len_cw < len_ccw ? path_cw : path_ccw);

            break;
        }
        else if( s_cw == DONE && !m_forceLongerPath )
        {
            aWalkPath = path_cw;
            break;
        }
        else if( s_ccw == DONE && !m_forceLongerPath )
        {
            aWalkPath = path_ccw;
            break;
        }

        m_iteration++;
    }

    if( m_iteration == m_iteration_limit )
    {
        int len_cw  = path_cw.GetCLine().Length();
        int len_ccw = path_ccw.GetCLine().Length();


        if( m_forceLongerPath )
            aWalkPath = (len_cw > len_ccw ? path_cw : path_ccw);
        else
            aWalkPath = (len_cw < len_ccw ? path_cw : path_ccw);
    }

    if( m_cursorApproachMode )
    {
        // int len_cw = path_cw.GetCLine().Length();
        // int len_ccw = path_ccw.GetCLine().Length();
        bool found = false;

        SHAPE_LINE_CHAIN l = aWalkPath.GetCLine();

        for( int i = 0; i < l.SegmentCount(); i++ )
        {
            const SEG s = l.Segment( i );

            VECTOR2I nearest = s.NearestPoint( m_cursorPos );
            VECTOR2I::extended_type dist_a = ( s.A - m_cursorPos ).SquaredEuclideanNorm();
            VECTOR2I::extended_type dist_b = ( s.B - m_cursorPos ).SquaredEuclideanNorm();
            VECTOR2I::extended_type dist_n = ( nearest - m_cursorPos ).SquaredEuclideanNorm();

            if( dist_n <= dist_a && dist_n < dist_b )
            {
                // PNSDisplayDebugLine( l, 3 );
                l.Remove( i + 1, -1 );
                l.Append( nearest );
                l.Simplify();
                found = true;
                break;
            }
        }

        if( found )
        {
            aWalkPath = aInitialPath;
            aWalkPath.SetShape( l );
        }
    }

    aWalkPath.SetWorld( m_world );
    aWalkPath.GetLine().Simplify();

    WalkaroundStatus st = s_ccw == DONE || s_cw == DONE ? DONE : STUCK;
//.........这里部分代码省略.........

const PNS_DIFF_PAIR PNS_DP_GATEWAY::Entry() const
{
    return PNS_DIFF_PAIR( m_entryP, m_entryN, 0 );
}


void PNS_DP_GATEWAYS::BuildOrthoProjections( PNS_DP_GATEWAYS& aEntries,
        const VECTOR2I& aCursorPos, int aOrthoScore )
{
    BOOST_FOREACH( PNS_DP_GATEWAY g, aEntries.Gateways() )
    {
        VECTOR2I dir = ( g.AnchorP() - g.AnchorN() ).Perpendicular();
        VECTOR2I midpoint( ( g.AnchorP() + g.AnchorN() ) / 2 );
        SEG guide( midpoint, midpoint + dir );
        VECTOR2I proj = guide.LineProject( aCursorPos );

        PNS_DP_GATEWAYS targets( m_gap );

        targets.m_viaGap = m_viaGap;
        targets.m_viaDiameter = m_viaDiameter;
        targets.m_fitVias = m_fitVias;

        targets.BuildForCursor( proj );

        BOOST_FOREACH( PNS_DP_GATEWAY t, targets.Gateways() )
        {
            t.SetPriority( aOrthoScore );
            m_gateways.push_back( t );
        }

OPT_BOX2I PNS_LINE::ChangedArea( const PNS_LINE* aOther ) const
{
    BOX2I area;
    bool areaDefined = false;

    int i_start = -1;
    int i_end_self = -1, i_end_other = -1;

    SHAPE_LINE_CHAIN self( m_line );
    self.Simplify();
    SHAPE_LINE_CHAIN other( aOther->m_line );
    other.Simplify();

    int np_self = self.PointCount();
    int np_other = other.PointCount();

    int n = std::min( np_self, np_other );

    for( int i = 0; i < n; i++ )
    {
        const VECTOR2I p1 = self.CPoint( i );
        const VECTOR2I p2 = other.CPoint( i );

        if( p1 != p2 )
        {
            if( i != n - 1 )
            {
                SEG s = self.CSegment( i );

                if( !s.Contains( p2 ) )
                {
                    i_start = i;
                    break;
                }
            } else {
                i_start = i;
                break;
            }
        }
    }

    for( int i = 0; i < n; i++ )
    {
        const VECTOR2I p1 = self.CPoint( np_self - 1 - i );
        const VECTOR2I p2 = other.CPoint( np_other - 1 - i );

        if( p1 != p2 )
        {
            i_end_self = np_self - 1 - i;
            i_end_other = np_other - 1 - i;
            break;
        }
    }

    if( i_start < 0 )
        i_start = n;

    if( i_end_self < 0 )
        i_end_self = np_self - 1;

    if( i_end_other < 0 )
        i_end_other = np_other - 1;

    for( int i = i_start; i <= i_end_self; i++ )
        extendBox( area, areaDefined, self.CPoint( i ) );

    for( int i = i_start; i <= i_end_other; i++ )
        extendBox( area, areaDefined, other.CPoint( i ) );

    if( areaDefined )
    {
        area.Inflate( std::max( Width(), aOther->Width() ) );
        return area;
    }

    return OPT_BOX2I();
}