/**
 * @param {number[]} A
 * @return {boolean}
 */
const canReorderDoubled = function(A) {
  const res = [];
  const both = [];
  const map = {};

  for (let i = 0; i < A.length; i++) {
    map[A[i]] = (map[A[i]] || 0) + 1;
  }

  for (let i = 0; i < A.length; i++) {
    const a = A[i];
    if (map[a] && map[a / 2] && map[a * 2]) {
      both.push(a);
    } else if (map[a] && map[a / 2]) {
      map[a / 2]--;
      map[a]--;

      res.push(a / 2, a);
    } else if (map[a] && map[a * 2]) {
      map[a * 2]--;
      map[a]--;

      res.push(a, a * 2);
    }
  }

  for (let i = 0; i < both.length; i++) {
    const a = both[i];
    if (map[a] && map[a / 2]) {
      map[a / 2]--;
      map[a]--;

      res.push(a / 2, a);
    } else if (map[a] && map[a * 2]) {
      map[a * 2]--;
      map[a]--;

      res.push(a, a * 2);
    }
  }

  return res.length === A.length;
};

/**
 * @param {number[]} A
 * @return {boolean}
 */
const canReorderDoubled = function(A) {
  const map = {};

  for (let i = 0; i < A.length; i++) {
    const val = Math.abs(A[i]);
    map[val] = (map[val] || 0) + 1;
  }

  for (const i in map) {
    const j = i * 2;

    if (i == '0') {
      if (map[i] % 2 !== 0) return false;

      map[i] = 0;
    } else if (map[i] && map[j]) {
      map[j] -= map[i];
      map[i] = 0;
    }
  }

  for (const i in map) if (map[i]) return false;

  return true;
};

Object instanceof Function // true
Function instanceof Object // true

// L instanceof R
function instance_of(L, R) {
 var O = R.prototype; // 取函数 R 的原型对象
 L = L.__proto__;     // 取对象 L 的原型
 while (true) {       // 遍历原型链
   if (L === null)
     return false; 
   if (O === L)       // 函数 R 的原型对象在对象 L 的原型链上
     return true; 
   L = L.__proto__; 
 } 
}

Function.__proto__ === Function.prototype

// lib/buffer.js

function allocate(size) {
  if (size <= 0) {
    return new FastBuffer();
  }
  if (size < (Buffer.poolSize >>> 1)) { // < 4k
    if (size > (poolSize - poolOffset)) // 大于剩余容量
      createPool();
    var b = new FastBuffer(allocPool, poolOffset, size);
    poolOffset += size;
    alignPool();
    return b;
  } else { // > 4k
    return createUnsafeBuffer(size);
  }
}

function fromString(string, encoding) {
  // ...
  if (length >= (Buffer.poolSize >>> 1)) // > 4k
    return binding.createFromString(string, encoding);

  if (length > (poolSize - poolOffset)) // 大于剩余容量
    createPool();
  var b = new FastBuffer(allocPool, poolOffset, length);
  const actual = b.write(string, encoding);
  if (actual !== length) { // byteLength() 可能会估计错误，尽管可能性很小
    b = new FastBuffer(allocPool, poolOffset, actual);
  }
  poolOffset += actual;
  alignPool();
  return b;
}

// lib/buffer.js

Buffer.poolSize = 8 * 1024;
var poolSize, poolOffset, allocPool;

function createUnsafeArrayBuffer(size) {
  // ...
  return new ArrayBuffer(size);
  // ...
}

function createPool() {
  poolSize = Buffer.poolSize; // 8k
  allocPool = createUnsafeArrayBuffer(poolSize);
  poolOffset = 0;
}
createPool();

function alignPool() {
  if (poolOffset & 0x7) { // 进行校准，只能为 8 的倍数
    poolOffset |= 0x7; // xxx111
    poolOffset++; // xx(x+1)000
  }
}

// lib/buffer.js

// safe
Buffer.from = function(value, encodingOrOffset, length) {
  if (typeof value === 'string')
    return fromString(value, encodingOrOffset); // safe

  if (isAnyArrayBuffer(value))
    return fromArrayBuffer(value, encodingOrOffset, length); // safe

  var b = fromObject(value); // safe
  // ...
};

function fromString(string, encoding) {
  // ...
  var b = new FastBuffer(allocPool, poolOffset, length);
  const actual = b.write(string, encoding);
  // ...
}

function fromArrayBuffer(obj, byteOffset, length) {
  // ...
  return new FastBuffer(obj, byteOffset, length);
}

function fromObject(obj) {
  if (isUint8Array(obj)) {
    const b = allocate(obj.length);
    // ...
    binding.copy(obj, b, 0, 0, obj.length);
  }

  if (obj != null) {
    // ...
      return fromArrayLike(obj);
    // ...
  }
}

function fromArrayLike(obj) {
  // ...
  const b = allocate(length);
  for (var i = 0; i < length; i++)
    b[i] = obj[i];
  return b;
}

// unsafe
Buffer.allocUnsafe = function(size) {
  return allocate(size);
};

// unsafe
Buffer.allocUnsafeSlow = function(size) {
  return createUnsafeBuffer(size);
};

function createUnsafeBuffer(size) {
  return new FastBuffer(createUnsafeArrayBuffer(size));
}

// safe
Buffer.alloc = function(size, fill, encoding) {
  assertSize(size);
  if (size > 0 && fill !== undefined) {
    // ...
    return createUnsafeBuffer(size).fill(fill, encoding); 
  }
  return new FastBuffer(size);
};

/**
 * @param {number[]} pushed
 * @param {number[]} popped
 * @return {boolean}
 */
let validateStackSequences = function(pushed, popped) {
  const arr = [];

  for (const i of pushed) {
    arr.push(i);

    while (
      arr.length > 0 &&
          arr[arr.length - 1] === popped[0]
    ) {
      arr.pop();
      popped.shift();
    }
  }

  return popped.length === 0;
};

const http = require('http')

http.createServer((req, res) => {
  res.end('Hello World\n')
}).listen(3000)

// lib/http.js

function createServer(requestListener) {
  return new Server(requestListener);
}

// lib/_http_server.js

function Server(requestListener) {
  if (!(this instanceof Server)) return new Server(requestListener);
  net.Server.call(this, { allowHalfOpen: true });

  if (requestListener) {
    this.on('request', requestListener);
  }

  this.on('connection', connectionListener);

  // ...
}

// lib/_http_server.js

function connectionListener(socket) {
  // ...

  // 从 parsers 中取一个 parser
  var parser = parsers.alloc();
  parser.reinitialize(HTTPParser.REQUEST);
  parser.socket = socket;
  socket.parser = parser;

  // ...

  state.onData = socketOnData.bind(undefined, this, socket, parser, state);

  // ...

  socket.on('data', state.onData);

  // ...
}

function socketOnData(server, socket, parser, state, d) {
  // ...
  var ret = parser.execute(d);
  // ...
}

// lib/internal/freelist.js

class FreeList {
  constructor(name, max, ctor) {
    this.name = name;
    this.ctor = ctor;
    this.max = max;
    this.list = [];
  }

  alloc() {
    return this.list.length ? this.list.pop() :
                              this.ctor.apply(this, arguments);
  }

  free(obj) {
    if (this.list.length < this.max) {
      this.list.push(obj);
      return true;
    }
    return false;
  }
}

module.exports = FreeList;

// lib/_http_common.js

const binding = process.binding('http_parser');
const HTTPParser = binding.HTTPParser;

// ...

var parsers = new FreeList('parsers', 1000, function() {
  var parser = new HTTPParser(HTTPParser.REQUEST);

  parser._headers = [];
  parser._url = '';
  parser._consumed = false;

  parser.socket = null;
  parser.incoming = null;
  parser.outgoing = null;

  parser[kOnHeaders] = parserOnHeaders;
  parser[kOnHeadersComplete] = parserOnHeadersComplete;
  parser[kOnBody] = parserOnBody;
  parser[kOnMessageComplete] = parserOnMessageComplete;
  parser[kOnExecute] = null;

  return parser;
});

function parserOnHeadersComplete(versionMajor, versionMinor, headers, method, url, statusCode, statusMessage, upgrade, shouldKeepAlive) {
  // ...
    
  if (!upgrade) {
    skipBody = parser.onIncoming(parser.incoming, shouldKeepAlive);
  }

  // ...
}

// lib/_http_server.js

function connectionListener(socket) {
  // ...
  parser.onIncoming = parserOnIncoming.bind(undefined, this, socket, state);
  // ...
}

// lib/_http_server.js

// 生成 response，并触发 request 事件
function parserOnIncoming(server, socket, state, req, keepAlive) {
  state.incoming.push(req);

  // ...

  var res = new ServerResponse(req);
  
  // ...

  if (socket._httpMessage) {
    state.outgoing.push(res);
  } else {
    res.assignSocket(socket);
  }

  // ...

  res.on('finish', resOnFinish.bind(undefined, req, res, socket, state, server));

  // ...

    server.emit('request', req, res);
  
  // ...
}

function resOnFinish(req, res, socket, state, server) {
  // ...

  state.incoming.shift();

  // ...

  res.detachSocket(socket);

  // ...
    var m = state.outgoing.shift();
    if (m) {
      m.assignSocket(socket);
    }
  }
}

const http = require('http')

http.createServer((req, res) => {
  res.end('Hello World\n')
}).listen(3000)

// lib/_http_outgoing.js

OutgoingMessage.prototype.end = function end(chunk, encoding, callback) {
  // ...
  if (chunk) {
    // ...
    write_(this, chunk, encoding, null, true);
  } else if (!this._header) {
    this._contentLength = 0;
    // 生成响应头
    this._implicitHeader();
  }

  // ...
  // 触发 finish 事件
  var finish = onFinish.bind(undefined, this);

  var ret;
  if (this._hasBody && this.chunkedEncoding) {
    // trailer 头相关
    ret = this._send('0\r\n' + this._trailer + '\r\n', 'latin1', finish);
  } else {
    // 保证一定会触发 finish 事件
    ret = this._send('', 'latin1', finish);
  }

  this.finished = true;

  // ...
};

function write_(msg, chunk, encoding, callback, fromEnd) {
  // ...

  if (!msg._header) {
    msg._implicitHeader();
  }

  // ...

  var len, ret;
  if (msg.chunkedEncoding) { // 响应大文件时，分块传输
    if (typeof chunk === 'string')
      len = Buffer.byteLength(chunk, encoding);
    else
      len = chunk.length;

    msg._send(len.toString(16), 'latin1', null);
    msg._send(crlf_buf, null, null);
    msg._send(chunk, encoding, null);
    ret = msg._send(crlf_buf, null, callback);
  } else {
    ret = msg._send(chunk, encoding, callback);
  }

  // ...
}

// lib/_http_server.js

ServerResponse.prototype._implicitHeader = function _implicitHeader() {
  this.writeHead(this.statusCode);
};

ServerResponse.prototype.writeHead = writeHead;
function writeHead(statusCode, reason, obj) {
  // ...
  // 将 obj 和 this[outHeadersKey] 中的所有 header 放到 headers 中
  // ...

  var statusLine = 'HTTP/1.1 ' + statusCode + ' ' + this.statusMessage + CRLF;

  this._storeHeader(statusLine, headers);
}

// lib/_http_outgoing.js

OutgoingMessage.prototype._storeHeader = _storeHeader;
function _storeHeader(firstLine, headers) {
  // > GET /index.html HTTP/1.1\r\n
  // < HTTP/1.1 200 OK\r\n

  // ...
  // 校验 header 并生成 HTTP 报文头
  // ...

  this._header = state.header + CRLF;
  this._headerSent = false;

  // ...
}

// lib/_http_outgoing.js

OutgoingMessage.prototype._send = function _send(data, encoding, callback) {
  if (!this._headerSent) { // 将 headers 添加到 data 前面
    if (typeof data === 'string' &&
        (encoding === 'utf8' || encoding === 'latin1' || !encoding)) {
      data = this._header + data;
    } else {
      var header = this._header;
      if (this.output.length === 0) {
        this.output = [header];
        this.outputEncodings = ['latin1'];
        this.outputCallbacks = [null];
      } else {
        this.output.unshift(header);
        this.outputEncodings.unshift('latin1');
        this.outputCallbacks.unshift(null);
      }
      this.outputSize += header.length;
      this._onPendingData(header.length);
    }
    this._headerSent = true;
  }
  return this._writeRaw(data, encoding, callback);
};

OutgoingMessage.prototype._writeRaw = _writeRaw;
function _writeRaw(data, encoding, callback) {
  const conn = this.connection;

  // ...

  if (conn && conn._httpMessage === this && conn.writable && !conn.destroyed) {
    if (this.output.length) { // output 中有缓存，先写入缓存
      this._flushOutput(conn);
    } else if (!data.length) { // 没有则异步执行回调
      if (typeof callback === 'function') {
        nextTick(this.socket[async_id_symbol], callback);
      }
      return true;
    }
    // 直接写入 socket
    return conn.write(data, encoding, callback);
  }
  // 加入 output 缓存
  this.output.push(data);
  this.outputEncodings.push(encoding);
  this.outputCallbacks.push(callback);
  this.outputSize += data.length;
  this._onPendingData(data.length);
  return false;
}

/**
 * @param {number[][]} points
 * @param {number} K
 * @return {number[][]}
 */
var kClosest = function(points, K) {
    return points.map(([i, j]) => ([i, j, i * i + j * j]))
        .sort(function([i1, j1, n1], [i2, j2, n2]) {
            if (n1 > n2) return 1
            else if (n1 < n2) return -1
            else return 0
        })
        .slice(0, K)
        .map(([i, j]) => ([i, j]))
};

/**
 * @param {number[][]} points
 * @param {number} K
 * @return {number[][]}
 */
var kClosest = function(points, K) {
    return points.sort(
        ([i1, j1], [i2, j2]) => i1 * i1 + j1 * j1 - i2 * i2 - j2 * j2
    ).slice(0, K)
};

// lib/_stream_readable.js

function Writable(options) {
  // 只能在 Writable 或 Duplex 的上下文中执行
  if (!(realHasInstance.call(Writable, this)) &&
      !(this instanceof Stream.Duplex)) {
    return new Writable(options);
  }

  // Wrirable 的状态集
  this._writableState = new WritableState(options, this);

  // legacy
  this.writable = true;

  if (options) {
    if (typeof options.write === 'function')
      this._write = options.write;

    if (typeof options.writev === 'function')
      this._writev = options.writev;

    if (typeof options.destroy === 'function')
      this._destroy = options.destroy;

    if (typeof options.final === 'function')
      this._final = options.final;
  }

  Stream.call(this);
}

function WritableState(options, stream) {
  options = options || {};

  // object 模式标识
  this.objectMode = !!options.objectMode;

  if (stream instanceof Stream.Duplex)
    this.objectMode = this.objectMode || !!options.writableObjectMode;

  var hwm = options.highWaterMark;
  var defaultHwm = this.objectMode ? 16 : 16 * 1024;
  this.highWaterMark = (hwm || hwm === 0) ? hwm : defaultHwm;

  // highWaterMark 高水位标识
  // 此时，write() 返回 false
  // 默认 16k
  this.highWaterMark = Math.floor(this.highWaterMark);

  this.finalCalled = false;
  // drain 事件标识
  this.needDrain = false;
  // 刚调用 end() 时的状态标识
  this.ending = false;
  // end() 调用完成后的状态标识
  this.ended = false;
  this.finished = false;
  this.destroyed = false;

  var noDecode = options.decodeStrings === false;
  // 数据写入前，是否应该将 string 解析为 buffer
  this.decodeStrings = !noDecode;
  this.defaultEncoding = options.defaultEncoding || 'utf8';

  // 缓存中的数据长度
  // 不是真正的 buffer 长度，而是正在等待写入的数据长度
  this.length = 0;
  // writing 标识
  this.writing = false;
  // cork 标识
  this.corked = 0;
  // 标识是否有异步回调
  this.sync = true;
  // 标识正在写入缓存中的内容
  this.bufferProcessing = false;
  // _write() 和 _writev() 函数的回调
  this.onwrite = onwrite.bind(undefined, stream);
  // 调用 write(chunk, cb) 时的回调函数
  this.writecb = null;
  // 需写入的单个 chunk 块长度
  this.writelen = 0;

  // Writable 的缓冲池实现也是一个链表，其每个节点的结构如下:
  // {
  //   chunk,
  //   encoding,
  //   isBuf,
  //   callback,
  //   next
  // }  

  // 缓冲池头节点
  this.bufferedRequest = null;
  // 缓冲池尾节点
  this.lastBufferedRequest = null;
  // 缓冲池的大小
  this.bufferedRequestCount = 0;

  // 还需要执行的 callback 数量，必须在 finish 事件发生之前降为 0
  this.pendingcb = 0;
  this.prefinished = false;
  this.errorEmitted = false;

  // cork 的回调函数，最多只能有两个函数对象
  var corkReq = { next: null, entry: null, finish: undefined };
  corkReq.finish = onCorkedFinish.bind(undefined, corkReq, this);
  this.corkedRequestsFree = corkReq;
}

{
  chunk,    // 数据块，可能是 object / string / buffer
  encoding, // 数据块编码
  isBuf,    // buffer 标识
  callback, // write(chunk, cb) 的回调函数
  next      // 下一个写入任务
}

// a duplex stream is just a stream that is both readable and writable.
// Since JS doesn't have multiple prototypal inheritance, this class
// prototypally inherits from Readable, and then parasitically from
// Writable.

// lib/_stream_writable.js

var realHasInstance;
if (typeof Symbol === 'function' && Symbol.hasInstance) {
  realHasInstance = Function.prototype[Symbol.hasInstance];
  Object.defineProperty(Writable, Symbol.hasInstance, {
    value: function(object) {
      if (realHasInstance.call(this, object))
        return true;

      return object && object._writableState instanceof WritableState;
    }
  });
} else {
  realHasInstance = function(object) {
    return object instanceof this;
  };
}

function Writable(options) {
  if (!(realHasInstance.call(Writable, this)) &&
      !(this instanceof Stream.Duplex)) {
    return new Writable(options);
  }
  // ...
}

// lib/_stream_duplex.js

util.inherits(Duplex, Readable);

var keys = Object.keys(Writable.prototype);
// 获取 Writable 的所有方法
for (var v = 0; v < keys.length; v++) {
  var method = keys[v];
  if (!Duplex.prototype[method])
    Duplex.prototype[method] = Writable.prototype[method];
}

function Duplex(options) {
  if (!(this instanceof Duplex))
    return new Duplex(options);

  Readable.call(this, options);
  Writable.call(this, options);
  // ...
}

// lib/_stream_writable.js

Writable.prototype.write = function(chunk, encoding, cb) {
  var state = this._writableState;
  var ret = false;
  // 判断是否是 buffer
  var isBuf = Stream._isUint8Array(chunk) && !state.objectMode;
  // ...
  if (state.ended)
    // Writable 结束后继续写入数据会报错
    // 触发 error 事件
    writeAfterEnd(this, cb);
  else if (isBuf || validChunk(this, state, chunk, cb)) { 
    // 对 chunk 进行校验
    // 不能为 null
    // undefined 和非字符串只在 objectMode 下接受
    state.pendingcb++;
    ret = writeOrBuffer(this, state, isBuf, chunk, encoding, cb);
  }

  return ret;
};

// lib/_stream_writable.js

function writeOrBuffer(stream, state, isBuf, chunk, encoding, cb) {
  if (!isBuf) {
    // 非 buffer 的情况有: string 或 object
    // 为 object，代表是 objectMode，直接返回即可
    // 为 string，则需解码成 buffer
    var newChunk = decodeChunk(state, chunk, encoding);
    if (chunk !== newChunk) {
      isBuf = true;
      encoding = 'buffer';
      chunk = newChunk;
    }
  }
  var len = state.objectMode ? 1 : chunk.length;

  state.length += len;

  var ret = state.length < state.highWaterMark;
  if (!ret) state.needDrain = true;

  if (state.writing || state.corked) {
    // 正在写或处于 cork 状态
    // 将数据块添加到缓冲池链表为尾部
    var last = state.lastBufferedRequest;
    state.lastBufferedRequest = {
      chunk,
      encoding,
      isBuf,
      callback: cb,
      next: null
    };
    if (last) {
      last.next = state.lastBufferedRequest;
    } else {
      state.bufferedRequest = state.lastBufferedRequest;
    }
    state.bufferedRequestCount += 1;
  } else {
    // 写入数据
    doWrite(stream, state, false, len, chunk, encoding, cb);
  }

  return ret;
}

// lib/_stream_writable.js

function doWrite(stream, state, writev, len, chunk, encoding, cb) {
  state.writelen = len; // 写入的数据块长度
  state.writecb = cb; // 写入操作的回调函数
  state.writing = true;
  state.sync = true; // 同步状态标识
  if (writev) // 一次写入多个数据块
    stream._writev(chunk, state.onwrite);
  else // 一次写入单个数据块
    stream._write(chunk, encoding, state.onwrite);
  state.sync = false;
}

this.onwrite = onwrite.bind(undefined, stream);

// lib/_stream_writable.js

function onwrite(stream, er) {
  var state = stream._writableState;
  var sync = state.sync;
  var cb = state.writecb;

  // 更新 state
  onwriteStateUpdate(state);

  if (er) // 发生错误
    onwriteError(stream, state, sync, er, cb);
  else {
    var finished = needFinish(state);

    if (!finished &&
        !state.corked &&
        !state.bufferProcessing &&
        state.bufferedRequest) {
      // 清空缓冲池
      // 有 _writev() 函数时，执行 _writev() 一次写入多个数据块
      // 没有，则循环执行 _write() 写入单个数据块
      clearBuffer(stream, state);
    }

    if (sync) { // 代表写入操作是同步的，需要在 process.nextTick() 中执行 callback
      process.nextTick(afterWrite, stream, state, finished, cb);
    } else { // 代表写入操作是异步的，直接执行 callback 即可
      afterWrite(stream, state, finished, cb);
    }
  }
}

// lib/_stream_writable.js

function afterWrite(stream, state, finished, cb) {
  if (!finished)
    onwriteDrain(stream, state);
  state.pendingcb--;
  // 执行回调函数
  cb();
  // 检查是否应该结束 Writable
  finishMaybe(stream, state);
}

// lib/_stream_writable.js

Writable.prototype.cork = function() {
  var state = this._writableState;

  // 增加柱塞的次数
  state.corked++;
};

// lib/_stream_writable.js

Writable.prototype.uncork = function() {
  var state = this._writableState;

  if (state.corked) {
    // 减少柱塞的次数
    state.corked--;

    if (!state.writing &&
        !state.corked &&
        !state.finished &&
        !state.bufferProcessing &&
        state.bufferedRequest)
      // 清空缓冲池
      clearBuffer(this, state);
  }
};

// lib/_stream_writable.js

function clearBuffer(stream, state) {
  // 正在清空 buffer 的标识
  state.bufferProcessing = true;
  // 缓存的头节点
  var entry = state.bufferedRequest;

  if (stream._writev && entry && entry.next) {
    // _writev() 函数存在，且有一个以上数据块，就使用 _writev() 写入数据，效率更高
    var l = state.bufferedRequestCount;
    var buffer = new Array(l);
    var holder = state.corkedRequestsFree;
    holder.entry = entry;

    var count = 0;
    var allBuffers = true;
    // 取得所有数据块
    while (entry) {
      buffer[count] = entry;
      if (!entry.isBuf)
        allBuffers = false;
      entry = entry.next;
      count += 1;
    }
    buffer.allBuffers = allBuffers;

    // 写入数据
    doWrite(stream, state, true, state.length, buffer, '', holder.finish);

    state.pendingcb++;
    state.lastBufferedRequest = null;
    // 保证最多只有两个实例
    if (holder.next) { 
      state.corkedRequestsFree = holder.next;
      holder.next = null;
    } else {
      var corkReq = { next: null, entry: null, finish: undefined };
      corkReq.finish = onCorkedFinish.bind(undefined, corkReq, state);
      state.corkedRequestsFree = corkReq;
    }
  } else {
    // 一个个的写入
    while (entry) {
      var chunk = entry.chunk;
      var encoding = entry.encoding;
      var cb = entry.callback;
      var len = state.objectMode ? 1 : chunk.length;

      doWrite(stream, state, false, len, chunk, encoding, cb);
      entry = entry.next;
      // 如果写操作不是同步执行的，就意味着需要等待此次写入完成，再继续写入
      if (state.writing) {
        break;
      }
    }

    if (entry === null)
      state.lastBufferedRequest = null;
  }

  state.bufferedRequestCount = 0;
  // 修正缓存的头节点
  state.bufferedRequest = entry;
  state.bufferProcessing = false;
}

// lib/_stream_writable.js

function onCorkedFinish(corkReq, state, err) {
  var entry = corkReq.entry;
  corkReq.entry = null;
  // 依次执行回调函数
  while (entry) {
    var cb = entry.callback;
    state.pendingcb--;
    cb(err);
    entry = entry.next;
  }
  // 保证最多只有两个实例
  if (state.corkedRequestsFree) {
    state.corkedRequestsFree.next = corkReq;
  } else {
    state.corkedRequestsFree = corkReq;
  }
}

// lib/module.js

Module.prototype.require = function(path) {
  assert(path, 'missing path');
  assert(typeof path === 'string', 'path must be a string');
  return Module._load(path, this, /* isMain */ false);
};

// Check the cache for the requested file.
// 1. If a module already exists in the cache: return its exports object.
// 2. If the module is native: call `NativeModule.require()` with the
//    filename and return the result.
// 3. Otherwise, create a new module for the file and save it to the cache.
//    Then have it load  the file contents before returning its exports
//    object.
Module._load = function(request, parent, isMain) {
  if (parent) {
    debug('Module._load REQUEST %s parent: %s', request, parent.id);
  }

  var filename = Module._resolveFilename(request, parent, isMain);

  var cachedModule = Module._cache[filename];
  if (cachedModule) {
    return cachedModule.exports;
  }

  if (NativeModule.nonInternalExists(filename)) {
    debug('load native module %s', request);
    return NativeModule.require(filename);
  }

  var module = new Module(filename, parent);

  if (isMain) {
    process.mainModule = module;
    module.id = '.';
  }

  Module._cache[filename] = module;

  tryModuleLoad(module, filename);

  return module.exports;
};

// lib/module.js

Module._resolveFilename = function(request, parent, isMain) {
  if (NativeModule.nonInternalExists(request)) {
    return request;
  }

  // 可能存在要加载模块的目录
  var paths = Module._resolveLookupPaths(request, parent, true);

  // 具体的模块路径
  var filename = Module._findPath(request, paths, isMain);
  if (!filename) {
    var err = new Error(`Cannot find module '${request}'`);
    err.code = 'MODULE_NOT_FOUND';
    throw err;
  }
  return filename;
};

// lib/module.js

Module._resolveLookupPaths = function(request, parent, newReturn) {
  if (NativeModule.nonInternalExists(request)) {
    debug('looking for %j in []', request);
    return (newReturn ? null : [request, []]);
  }

  // 类似 require('xxx')
  if (request.length < 2 ||
      request.charCodeAt(0) !== 46 ||       // 非 . 开头
      (request.charCodeAt(1) !== 46         // 非 .. 开头
        && request.charCodeAt(1) !== 47)) { // 非 / 开头
    var paths = modulePaths;
    if (parent) {
      if (!parent.paths)
        paths = parent.paths = [];
      else
        paths = parent.paths.concat(paths);
    }

    // Maintain backwards compat with certain broken uses of require('.')
    // by putting the module's directory in front of the lookup paths.
    if (request === '.') {
      if (parent && parent.filename) {
        paths.unshift(path.dirname(parent.filename));
      } else {
        paths.unshift(path.resolve(request));
      }
    }

    debug('looking for %j in %j', request, paths);
    return (newReturn ? (paths.length > 0 ? paths : null) : [request, paths]);
  }

  // 执行 Module.runMain() 进入，此时 request 是绝对路径

  // with --eval, parent.id is not set and parent.filename is null
  if (!parent || !parent.id || !parent.filename) {
    // make require('./path/to/foo') work - normally the path is taken
    // from realpath(__filename) but with eval there is no filename
    var mainPaths = ['.'].concat(Module._nodeModulePaths('.'), modulePaths);

    debug('looking for %j in %j', request, mainPaths);
    return (newReturn ? mainPaths : [request, mainPaths]);
  }

  // ...

  var parentDir = [path.dirname(parent.filename)];
  debug('looking for %j in %j', id, parentDir);
  return (newReturn ? parentDir : [id, parentDir]);
};

// lib/module.js

Module._findPath = function(request, paths, isMain) {
  if (path.isAbsolute(request)) {
    paths = [''];
  } else if (!paths || paths.length === 0) {
    return false;
  }

  // 计算 cacheKey
  // 对于同一模块，每个目录的 cacheKey 不同
  var cacheKey = request + '\x00' +
                (paths.length === 1 ? paths[0] : paths.join('\x00'));
  var entry = Module._pathCache[cacheKey];
  // 有缓存就走缓存
  if (entry)
    return entry;

  var exts;
  var trailingSlash = request.length > 0 &&
                      request.charCodeAt(request.length - 1) === 47; // /

  // For each path
  for (var i = 0; i < paths.length; i++) {
    const curPath = paths[i];
    // 不存在就跳过
    if (curPath && stat(curPath) < 1) continue;
    var basePath = path.resolve(curPath, request);
    var filename;

    var rc = stat(basePath);
    if (!trailingSlash) {
      if (rc === 0) {  // 文件
        if (preserveSymlinks && !isMain) {
          filename = path.resolve(basePath);
        } else {
          filename = toRealPath(basePath);
        }
      } else if (rc === 1) {  // 目录或 package
        if (exts === undefined)
          exts = Object.keys(Module._extensions);
        // 如果是目录，则 filename 为 false
        filename = tryPackage(basePath, exts, isMain);
      }

      // 对应是文件但未给出文件后缀的情况
      if (!filename) {
        // try it with each of the extensions
        if (exts === undefined)
          exts = Object.keys(Module._extensions);
        filename = tryExtensions(basePath, exts, isMain);
      }
    }

    if (!filename && rc === 1) {  // 目录或 package
      if (exts === undefined)
        exts = Object.keys(Module._extensions);
      // 如果是目录，则 filename 为 false
      filename = tryPackage(basePath, exts, isMain);
    }

    if (!filename && rc === 1) {  // 目录
      // try it with each of the extensions at "index"
      if (exts === undefined)
        exts = Object.keys(Module._extensions);
      filename = tryExtensions(path.resolve(basePath, 'index'), exts, isMain);
    }

    if (filename) {
      // Warn once if '.' resolved outside the module dir
      if (request === '.' && i > 0) {
        if (!warned) {
          warned = true;
          process.emitWarning(
            'warning: require(\'.\') resolved outside the package ' +
            'directory. This functionality is deprecated and will be removed ' +
            'soon.',
            'DeprecationWarning', 'DEP0019');
        }
      }

      Module._pathCache[cacheKey] = filename;
      return filename;
    }
  }
  return false;
};

  var exts = Object.keys(Module._extensions);
  var trailingSlash = request.length > 0 &&
                      request.charCodeAt(request.length - 1) === 47; // /

  for (var i = 0; i < paths.length; i++) {
    const curPath = paths[i];
    // 不存在就跳过
    if (curPath && stat(curPath) < 1) continue;
    var basePath = path.resolve(curPath, request);
    var filename;

    var rc = stat(basePath);
    if (!trailingSlash && rc !== 1) {  // 文件或啥也没有
      if (rc === 0) {  // 文件
        if (preserveSymlinks && !isMain) {
          filename = path.resolve(basePath);
        } else {
          filename = toRealPath(basePath);
        }
      } else {  // 对应是文件但未给出文件后缀的情况
        filename = tryExtensions(basePath, exts, isMain);
      }
    }

    if(!filename && rc === 1){  // 目录或 package
      filename = tryPackage(basePath, exts, isMain);

      // 如果是目录，则 filename 为 false
      if (!filename) {
        // try it with each of the extensions at "index"
        filename = tryExtensions(path.resolve(basePath, 'index'), exts, isMain);
      }
    }

    if (filename) {
      // Warn once if '.' resolved outside the module dir
      if (request === '.' && i > 0) {
        if (!warned) {
          warned = true;
          process.emitWarning(
            'warning: require(\'.\') resolved outside the package ' +
            'directory. This functionality is deprecated and will be removed ' +
            'soon.',
            'DeprecationWarning', 'DEP0019');
        }
      }

      Module._pathCache[cacheKey] = filename;
      return filename;
    }
  }

// lib/module.js

function tryPackage(requestPath, exts, isMain) {
  // 读取目录下的 package.json 并返回 package.main，没有则返回 false
  var pkg = readPackage(requestPath);

  if (!pkg) return false;

  var filename = path.resolve(requestPath, pkg);
  return tryFile(filename, isMain) || // package.main 有后缀
         tryExtensions(filename, exts, isMain) || // package.main 没有后缀
         tryExtensions(path.resolve(filename, 'index'), exts, isMain); // package.main 不存在则默认加载 index.js / index.json / index.node
}

function readPackage(requestPath) {
  const entry = packageMainCache[requestPath];
  if (entry)
    return entry;

  const jsonPath = path.resolve(requestPath, 'package.json');
  const json = internalModuleReadFile(path._makeLong(jsonPath));

  // 没有 package.json，说明不是一个包
  if (json === undefined) {
    return false;
  }

  try {
    var pkg = packageMainCache[requestPath] = JSON.parse(json).main;
  } catch (e) {
    e.path = jsonPath;
    e.message = 'Error parsing ' + jsonPath + ': ' + e.message;
    throw e;
  }
  return pkg;
}

// given a path check a the file exists with any of the set extensions
function tryExtensions(p, exts, isMain) {
  for (var i = 0; i < exts.length; i++) {
    const filename = tryFile(p + exts[i], isMain);

    if (filename) {
      return filename;
    }
  }
  return false;
}

// check if the file exists and is not a directory
// if using --preserve-symlinks and isMain is false,
// keep symlinks intact, otherwise resolve to the
// absolute realpath.
function tryFile(requestPath, isMain) {
  const rc = stat(requestPath);
  if (preserveSymlinks && !isMain) {
    return rc === 0 && path.resolve(requestPath);
  }
  return rc === 0 && toRealPath(requestPath);
}

function toRealPath(requestPath) {
  return fs.realpathSync(requestPath, {
    [internalFS.realpathCacheKey]: realpathCache
  });
}

// lib/module.js

function tryModuleLoad(module, filename) {
  var threw = true;
  try {
    module.load(filename);
    threw = false;
  } finally {
    if (threw) {
      delete Module._cache[filename];
    }
  }
}

// lib/module.js

// Given a file name, pass it to the proper extension handler.
Module.prototype.load = function(filename) {
  debug('load %j for module %j', filename, this.id);

  assert(!this.loaded);
  this.filename = filename;
  // 全局 node_modules 和文件路径上所有的 node_modules
  this.paths = Module._nodeModulePaths(path.dirname(filename));

  // 通过文件扩展名确定加载方式，默认采用 .js 的方式加载
  var extension = path.extname(filename) || '.js';
  if (!Module._extensions[extension]) extension = '.js';
  Module._extensions[extension](this, filename);
  this.loaded = true;
};

// Native extension for .js
Module._extensions['.js'] = function(module, filename) {
  var content = fs.readFileSync(filename, 'utf8');
  module._compile(internalModule.stripBOM(content), filename);
};

// Native extension for .json
Module._extensions['.json'] = function(module, filename) {
  var content = fs.readFileSync(filename, 'utf8');
  try {
    module.exports = JSON.parse(internalModule.stripBOM(content));
  } catch (err) {
    err.message = filename + ': ' + err.message;
    throw err;
  }
};

//Native extension for .node
Module._extensions['.node'] = function(module, filename) {
  return process.dlopen(module, path._makeLong(filename));
};

// Run the file contents in the correct scope or sandbox. Expose
// the correct helper variables (require, module, exports) to
// the file.
// Returns exception, if any.
Module.prototype._compile = function(content, filename) {

  content = internalModule.stripShebang(content);

  // 使用下面这个结构包裹
  // (function (exports, require, module, __filename, __dirname) {
  //   ...
  // });
  var wrapper = Module.wrap(content);

  // 在沙箱内生成函数对象
  var compiledWrapper = vm.runInThisContext(wrapper, {
    filename: filename,
    lineOffset: 0,
    displayErrors: true
  });

  // ...

  var dirname = path.dirname(filename);
  var require = internalModule.makeRequireFunction(this);
  var depth = internalModule.requireDepth;
  if (depth === 0) stat.cache = new Map();
  var result;
  if (inspectorWrapper) {
    result = inspectorWrapper(compiledWrapper, this.exports, this.exports,
                              require, this, filename, dirname);
  } else {
    result = compiledWrapper.call(this.exports, this.exports, require, this,
                                  filename, dirname);
  }
  if (depth === 0) stat.cache = null;
  return result;
};

// lib/internal/module.js

// Invoke with makeRequireFunction(module) where |module| is the Module object
// to use as the context for the require() function.
function makeRequireFunction(mod) {
  const Module = mod.constructor;

  function require(path) {
    try {
      exports.requireDepth += 1;
      return mod.require(path);
    } finally {
      exports.requireDepth -= 1;
    }
  }

  function resolve(request) {
    return Module._resolveFilename(request, mod);
  }

  require.resolve = resolve;

  require.main = process.mainModule;

  // Enable support to add extra extension types.
  require.extensions = Module._extensions;

  require.cache = Module._cache;

  return require;
}

/**
 * Definition for an interval.
 * function Interval(start, end) {
 *     this.start = start;
 *     this.end = end;
 * }
 */
/**
 * @param {Interval[]} A
 * @param {Interval[]} B
 * @return {Interval[]}
 */
var intervalIntersection = function(A, B) {
    let res = []

    let i = 0
    let j = 0
    while (i < A.length && j < B.length) {
        let x = A[i].start
        let y = A[i].end
        let x1 = B[j].start
        let y1 = B[j].end

        if (y >= x1 && x <= y1) {
            res.push({ start: Math.max(x, x1), end: Math.min(y, y1) })
        }

        y < y1 ? i++ : j++
    }
    
    return res
};

/**
 * @param {string} S
 * @return {boolean}
 */
var isValid = function(S) {
  if (S.length === 0) return true

  for (let i = 0; i < S.length; i++) {
    if (S.substring(i, i + 3) === 'abc') return isValid(S.slice(0, i) + S.slice(i + 3))
  }
  
  return false
};