/**
 * @license
 * Copyright 2020 Google LLC. All Rights Reserved.
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 * =============================================================================
 */
import { backend_util, buffer, MaxPool3DGrad } from '@tensorflow/tfjs-core';
import { assertNotComplex } from '../cpu_util';
import { maxPool3dPositions } from '../utils/pool_utils';
export function maxPool3DGrad(args) {
    const { inputs, backend, attrs } = args;
    const { dy, input } = inputs;
    const { filterSize, strides, pad, dimRoundingMode } = attrs;
    assertNotComplex([dy, input], 'maxPool3DGrad');
    const convInfo = backend_util.computePool3DInfo(input.shape, filterSize, strides, 1 /* dilations */, pad, dimRoundingMode);
    const inputBuf = backend.bufferSync(input);
    const maxPosBuf = maxPool3dPositions(inputBuf, convInfo);
    const strideDepth = convInfo.strideDepth;
    const strideHeight = convInfo.strideHeight;
    const strideWidth = convInfo.strideWidth;
    const dilationDepth = convInfo.dilationDepth;
    const dilationHeight = convInfo.dilationHeight;
    const dilationWidth = convInfo.dilationWidth;
    const effectiveFilterDepth = convInfo.effectiveFilterDepth;
    const effectiveFilterHeight = convInfo.effectiveFilterHeight;
    const effectiveFilterWidth = convInfo.effectiveFilterWidth;
    const padFront = effectiveFilterDepth - 1 - convInfo.padInfo.front;
    const padLeft = effectiveFilterWidth - 1 - convInfo.padInfo.left;
    const padTop = effectiveFilterHeight - 1 - convInfo.padInfo.top;
    const dx = buffer(input.shape, 'float32');
    const dyBuf = backend.bufferSync(dy);
    for (let batch = 0; batch < convInfo.batchSize; ++batch) {
        for (let channel = 0; channel < convInfo.inChannels; ++channel) {
            for (let dxDepth = 0; dxDepth < convInfo.inDepth; ++dxDepth) {
                for (let dxRow = 0; dxRow < convInfo.inHeight; ++dxRow) {
                    for (let dxCol = 0; dxCol < convInfo.inWidth; ++dxCol) {
                        // Shader code begins
                        const dyDepthCorner = dxDepth - padFront;
                        const dyRowCorner = dxRow - padTop;
                        const dyColCorner = dxCol - padLeft;
                        let dotProd = 0;
                        for (let wDepth = 0; wDepth < effectiveFilterDepth; wDepth += dilationDepth) {
                            const dyDepth = (dyDepthCorner + wDepth) / strideDepth;
                            if (dyDepth < 0 || dyDepth >= convInfo.outDepth ||
                                Math.floor(dyDepth) !== dyDepth) {
                                continue;
                            }
                            for (let wRow = 0; wRow < effectiveFilterHeight; wRow += dilationHeight) {
                                const dyRow = (dyRowCorner + wRow) / strideHeight;
                                if (dyRow < 0 || dyRow >= convInfo.outHeight ||
                                    Math.floor(dyRow) !== dyRow) {
                                    continue;
                                }
                                for (let wCol = 0; wCol < effectiveFilterWidth; wCol += dilationWidth) {
                                    const dyCol = (dyColCorner + wCol) / strideWidth;
                                    if (dyCol < 0 || dyCol >= convInfo.outWidth ||
                                        Math.floor(dyCol) !== dyCol) {
                                        continue;
                                    }
                                    const maxPos = effectiveFilterDepth * effectiveFilterHeight *
                                        effectiveFilterWidth -
                                        1 -
                                        maxPosBuf.get(batch, dyDepth, dyRow, dyCol, channel);
                                    const curPos = wDepth * effectiveFilterHeight * effectiveFilterWidth +
                                        wRow * effectiveFilterWidth + wCol;
                                    const mask = maxPos === curPos ? 1 : 0;
                                    if (mask === 0) {
                                        continue;
                                    }
                                    const pixel = dyBuf.get(batch, dyDepth, dyRow, dyCol, channel);
                                    dotProd += pixel * mask;
                                }
                            }
                        }
                        dx.set(dotProd, batch, dxDepth, dxRow, dxCol, channel);
                    }
                }
            }
        }
    }
    return backend.makeTensorInfo(dx.shape, dx.dtype, dx.values);
}
export const maxPool3DGradConfig = {
    kernelName: MaxPool3DGrad,
    backendName: 'cpu',
    kernelFunc: maxPool3DGrad
};
//# sourceMappingURL=data:application/json;base64,eyJ2ZXJzaW9uIjozLCJmaWxlIjoiTWF4UG9vbDNER3JhZC5qcyIsInNvdXJjZVJvb3QiOiIiLCJzb3VyY2VzIjpbIi4uLy4uLy4uLy4uLy4uLy4uL3RmanMtYmFja2VuZC1jcHUvc3JjL2tlcm5lbHMvTWF4UG9vbDNER3JhZC50cyJdLCJuYW1lcyI6W10sIm1hcHBpbmdzIjoiQUFBQTs7Ozs7Ozs7Ozs7Ozs7O0dBZUc7QUFFSCxPQUFPLEVBQUMsWUFBWSxFQUFFLE1BQU0sRUFBNEIsYUFBYSxFQUE0RCxNQUFNLHVCQUF1QixDQUFDO0FBRy9KLE9BQU8sRUFBQyxnQkFBZ0IsRUFBQyxNQUFNLGFBQWEsQ0FBQztBQUM3QyxPQUFPLEVBQUMsa0JBQWtCLEVBQUMsTUFBTSxxQkFBcUIsQ0FBQztBQUV2RCxNQUFNLFVBQVUsYUFBYSxDQUFDLElBSTdCO0lBQ0MsTUFBTSxFQUFDLE1BQU0sRUFBRSxPQUFPLEVBQUUsS0FBSyxFQUFDLEdBQUcsSUFBSSxDQUFDO0lBQ3RDLE1BQU0sRUFBQyxFQUFFLEVBQUUsS0FBSyxFQUFDLEdBQUcsTUFBTSxDQUFDO0lBQzNCLE1BQU0sRUFBQyxVQUFVLEVBQUUsT0FBTyxFQUFFLEdBQUcsRUFBRSxlQUFlLEVBQUMsR0FBRyxLQUFLLENBQUM7SUFFMUQsZ0JBQWdCLENBQUMsQ0FBQyxFQUFFLEVBQUUsS0FBSyxDQUFDLEVBQUUsZUFBZSxDQUFDLENBQUM7SUFFL0MsTUFBTSxRQUFRLEdBQUcsWUFBWSxDQUFDLGlCQUFpQixDQUMzQyxLQUFLLENBQUMsS0FBaUQsRUFBRSxVQUFVLEVBQ25FLE9BQU8sRUFBRSxDQUFDLENBQUMsZUFBZSxFQUFFLEdBQUcsRUFBRSxlQUFlLENBQUMsQ0FBQztJQUV0RCxNQUFNLFFBQVEsR0FBRyxPQUFPLENBQUMsVUFBVSxDQUFDLEtBQUssQ0FBQyxDQUFDO0lBQzNDLE1BQU0sU0FBUyxHQUFHLGtCQUFrQixDQUFDLFFBQVEsRUFBRSxRQUFRLENBQUMsQ0FBQztJQUN6RCxNQUFNLFdBQVcsR0FBRyxRQUFRLENBQUMsV0FBVyxDQUFDO0lBQ3pDLE1BQU0sWUFBWSxHQUFHLFFBQVEsQ0FBQyxZQUFZLENBQUM7SUFDM0MsTUFBTSxXQUFXLEdBQUcsUUFBUSxDQUFDLFdBQVcsQ0FBQztJQUN6QyxNQUFNLGFBQWEsR0FBRyxRQUFRLENBQUMsYUFBYSxDQUFDO0lBQzdDLE1BQU0sY0FBYyxHQUFHLFFBQVEsQ0FBQyxjQUFjLENBQUM7SUFDL0MsTUFBTSxhQUFhLEdBQUcsUUFBUSxDQUFDLGFBQWEsQ0FBQztJQUM3QyxNQUFNLG9CQUFvQixHQUFHLFFBQVEsQ0FBQyxvQkFBb0IsQ0FBQztJQUMzRCxNQUFNLHFCQUFxQixHQUFHLFFBQVEsQ0FBQyxxQkFBcUIsQ0FBQztJQUM3RCxNQUFNLG9CQUFvQixHQUFHLFFBQVEsQ0FBQyxvQkFBb0IsQ0FBQztJQUMzRCxNQUFNLFFBQVEsR0FBRyxvQkFBb0IsR0FBRyxDQUFDLEdBQUcsUUFBUSxDQUFDLE9BQU8sQ0FBQyxLQUFLLENBQUM7SUFDbkUsTUFBTSxPQUFPLEdBQUcsb0JBQW9CLEdBQUcsQ0FBQyxHQUFHLFFBQVEsQ0FBQyxPQUFPLENBQUMsSUFBSSxDQUFDO0lBQ2pFLE1BQU0sTUFBTSxHQUFHLHFCQUFxQixHQUFHLENBQUMsR0FBRyxRQUFRLENBQUMsT0FBTyxDQUFDLEdBQUcsQ0FBQztJQUNoRSxNQUFNLEVBQUUsR0FBRyxNQUFNLENBQUMsS0FBSyxDQUFDLEtBQUssRUFBRSxTQUFTLENBQUMsQ0FBQztJQUUxQyxNQUFNLEtBQUssR0FBRyxPQUFPLENBQUMsVUFBVSxDQUFrQixFQUFFLENBQUMsQ0FBQztJQUV0RCxLQUFLLElBQUksS0FBSyxHQUFHLENBQUMsRUFBRSxLQUFLLEdBQUcsUUFBUSxDQUFDLFNBQVMsRUFBRSxFQUFFLEtBQUssRUFBRTtRQUN2RCxLQUFLLElBQUksT0FBTyxHQUFHLENBQUMsRUFBRSxPQUFPLEdBQUcsUUFBUSxDQUFDLFVBQVUsRUFBRSxFQUFFLE9BQU8sRUFBRTtZQUM5RCxLQUFLLElBQUksT0FBTyxHQUFHLENBQUMsRUFBRSxPQUFPLEdBQUcsUUFBUSxDQUFDLE9BQU8sRUFBRSxFQUFFLE9BQU8sRUFBRTtnQkFDM0QsS0FBSyxJQUFJLEtBQUssR0FBRyxDQUFDLEVBQUUsS0FBSyxHQUFHLFFBQVEsQ0FBQyxRQUFRLEVBQUUsRUFBRSxLQUFLLEVBQUU7b0JBQ3RELEtBQUssSUFBSSxLQUFLLEdBQUcsQ0FBQyxFQUFFLEtBQUssR0FBRyxRQUFRLENBQUMsT0FBTyxFQUFFLEVBQUUsS0FBSyxFQUFFO3dCQUNyRCxxQkFBcUI7d0JBQ3JCLE1BQU0sYUFBYSxHQUFHLE9BQU8sR0FBRyxRQUFRLENBQUM7d0JBQ3pDLE1BQU0sV0FBVyxHQUFHLEtBQUssR0FBRyxNQUFNLENBQUM7d0JBQ25DLE1BQU0sV0FBVyxHQUFHLEtBQUssR0FBRyxPQUFPLENBQUM7d0JBQ3BDLElBQUksT0FBTyxHQUFHLENBQUMsQ0FBQzt3QkFDaEIsS0FBSyxJQUFJLE1BQU0sR0FBRyxDQUFDLEVBQUUsTUFBTSxHQUFHLG9CQUFvQixFQUM3QyxNQUFNLElBQUksYUFBYSxFQUFFOzRCQUM1QixNQUFNLE9BQU8sR0FBRyxDQUFDLGFBQWEsR0FBRyxNQUFNLENBQUMsR0FBRyxXQUFXLENBQUM7NEJBQ3ZELElBQUksT0FBTyxHQUFHLENBQUMsSUFBSSxPQUFPLElBQUksUUFBUSxDQUFDLFFBQVE7Z0NBQzNDLElBQUksQ0FBQyxLQUFLLENBQUMsT0FBTyxDQUFDLEtBQUssT0FBTyxFQUFFO2dDQUNuQyxTQUFTOzZCQUNWOzRCQUNELEtBQUssSUFBSSxJQUFJLEdBQUcsQ0FBQyxFQUFFLElBQUksR0FBRyxxQkFBcUIsRUFDMUMsSUFBSSxJQUFJLGNBQWMsRUFBRTtnQ0FDM0IsTUFBTSxLQUFLLEdBQUcsQ0FBQyxXQUFXLEdBQUcsSUFBSSxDQUFDLEdBQUcsWUFBWSxDQUFDO2dDQUNsRCxJQUFJLEtBQUssR0FBRyxDQUFDLElBQUksS0FBSyxJQUFJLFFBQVEsQ0FBQyxTQUFTO29DQUN4QyxJQUFJLENBQUMsS0FBSyxDQUFDLEtBQUssQ0FBQyxLQUFLLEtBQUssRUFBRTtvQ0FDL0IsU0FBUztpQ0FDVjtnQ0FDRCxLQUFLLElBQUksSUFBSSxHQUFHLENBQUMsRUFBRSxJQUFJLEdBQUcsb0JBQW9CLEVBQ3pDLElBQUksSUFBSSxhQUFhLEVBQUU7b0NBQzFCLE1BQU0sS0FBSyxHQUFHLENBQUMsV0FBVyxHQUFHLElBQUksQ0FBQyxHQUFHLFdBQVcsQ0FBQztvQ0FDakQsSUFBSSxLQUFLLEdBQUcsQ0FBQyxJQUFJLEtBQUssSUFBSSxRQUFRLENBQUMsUUFBUTt3Q0FDdkMsSUFBSSxDQUFDLEtBQUssQ0FBQyxLQUFLLENBQUMsS0FBSyxLQUFLLEVBQUU7d0NBQy9CLFNBQVM7cUNBQ1Y7b0NBRUQsTUFBTSxNQUFNLEdBQUcsb0JBQW9CLEdBQUcscUJBQXFCO3dDQUNuRCxvQkFBb0I7d0NBQ3hCLENBQUM7d0NBQ0EsU0FBUyxDQUFDLEdBQUcsQ0FBQyxLQUFLLEVBQUUsT0FBTyxFQUFFLEtBQUssRUFBRSxLQUFLLEVBQUUsT0FBTyxDQUM1QyxDQUFDO29DQUNiLE1BQU0sTUFBTSxHQUNSLE1BQU0sR0FBRyxxQkFBcUIsR0FBRyxvQkFBb0I7d0NBQ3JELElBQUksR0FBRyxvQkFBb0IsR0FBRyxJQUFJLENBQUM7b0NBRXZDLE1BQU0sSUFBSSxHQUFHLE1BQU0sS0FBSyxNQUFNLENBQUMsQ0FBQyxDQUFDLENBQUMsQ0FBQyxDQUFDLENBQUMsQ0FBQyxDQUFDO29DQUN2QyxJQUFJLElBQUksS0FBSyxDQUFDLEVBQUU7d0NBQ2QsU0FBUztxQ0FDVjtvQ0FFRCxNQUFNLEtBQUssR0FDUCxLQUFLLENBQUMsR0FBRyxDQUFDLEtBQUssRUFBRSxPQUFPLEVBQUUsS0FBSyxFQUFFLEtBQUssRUFBRSxPQUFPLENBQUMsQ0FBQztvQ0FDckQsT0FBTyxJQUFJLEtBQUssR0FBRyxJQUFJLENBQUM7aUNBQ3pCOzZCQUNGO3lCQUNGO3dCQUNELEVBQUUsQ0FBQyxHQUFHLENBQUMsT0FBTyxFQUFFLEtBQUssRUFBRSxPQUFPLEVBQUUsS0FBSyxFQUFFLEtBQUssRUFBRSxPQUFPLENBQUMsQ0FBQztxQkFDeEQ7aUJBQ0Y7YUFDRjtTQUNGO0tBQ0Y7SUFFRCxPQUFPLE9BQU8sQ0FBQyxjQUFjLENBQUMsRUFBRSxDQUFDLEtBQUssRUFBRSxFQUFFLENBQUMsS0FBSyxFQUFFLEVBQUUsQ0FBQyxNQUFNLENBQUMsQ0FBQztBQUMvRCxDQUFDO0FBRUQsTUFBTSxDQUFDLE1BQU0sbUJBQW1CLEdBQWlCO0lBQy9DLFVBQVUsRUFBRSxhQUFhO0lBQ3pCLFdBQVcsRUFBRSxLQUFLO0lBQ2xCLFVBQVUsRUFBRSxhQUFzQztDQUNuRCxDQUFDIiwic291cmNlc0NvbnRlbnQiOlsiLyoqXG4gKiBAbGljZW5zZVxuICogQ29weXJpZ2h0IDIwMjAgR29vZ2xlIExMQy4gQWxsIFJpZ2h0cyBSZXNlcnZlZC5cbiAqIExpY2Vuc2VkIHVuZGVyIHRoZSBBcGFjaGUgTGljZW5zZSwgVmVyc2lvbiAyLjAgKHRoZSBcIkxpY2Vuc2VcIik7XG4gKiB5b3UgbWF5IG5vdCB1c2UgdGhpcyBmaWxlIGV4Y2VwdCBpbiBjb21wbGlhbmNlIHdpdGggdGhlIExpY2Vuc2UuXG4gKiBZb3UgbWF5IG9idGFpbiBhIGNvcHkgb2YgdGhlIExpY2Vuc2UgYXRcbiAqXG4gKiBodHRwOi8vd3d3LmFwYWNoZS5vcmcvbGljZW5zZXMvTElDRU5TRS0yLjBcbiAqXG4gKiBVbmxlc3MgcmVxdWlyZWQgYnkgYXBwbGljYWJsZSBsYXcgb3IgYWdyZWVkIHRvIGluIHdyaXRpbmcsIHNvZnR3YXJlXG4gKiBkaXN0cmlidXRlZCB1bmRlciB0aGUgTGljZW5zZSBpcyBkaXN0cmlidXRlZCBvbiBhbiBcIkFTIElTXCIgQkFTSVMsXG4gKiBXSVRIT1VUIFdBUlJBTlRJRVMgT1IgQ09ORElUSU9OUyBPRiBBTlkgS0lORCwgZWl0aGVyIGV4cHJlc3Mgb3IgaW1wbGllZC5cbiAqIFNlZSB0aGUgTGljZW5zZSBmb3IgdGhlIHNwZWNpZmljIGxhbmd1YWdlIGdvdmVybmluZyBwZXJtaXNzaW9ucyBhbmRcbiAqIGxpbWl0YXRpb25zIHVuZGVyIHRoZSBMaWNlbnNlLlxuICogPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT1cbiAqL1xuXG5pbXBvcnQge2JhY2tlbmRfdXRpbCwgYnVmZmVyLCBLZXJuZWxDb25maWcsIEtlcm5lbEZ1bmMsIE1heFBvb2wzREdyYWQsIE1heFBvb2wzREdyYWRBdHRycywgTWF4UG9vbDNER3JhZElucHV0cywgUmFuaywgVGVuc29ySW5mb30gZnJvbSAnQHRlbnNvcmZsb3cvdGZqcy1jb3JlJztcblxuaW1wb3J0IHtNYXRoQmFja2VuZENQVX0gZnJvbSAnLi4vYmFja2VuZF9jcHUnO1xuaW1wb3J0IHthc3NlcnROb3RDb21wbGV4fSBmcm9tICcuLi9jcHVfdXRpbCc7XG5pbXBvcnQge21heFBvb2wzZFBvc2l0aW9uc30gZnJvbSAnLi4vdXRpbHMvcG9vbF91dGlscyc7XG5cbmV4cG9ydCBmdW5jdGlvbiBtYXhQb29sM0RHcmFkKGFyZ3M6IHtcbiAgaW5wdXRzOiBNYXhQb29sM0RHcmFkSW5wdXRzLFxuICBiYWNrZW5kOiBNYXRoQmFja2VuZENQVSxcbiAgYXR0cnM6IE1heFBvb2wzREdyYWRBdHRyc1xufSk6IFRlbnNvckluZm8ge1xuICBjb25zdCB7aW5wdXRzLCBiYWNrZW5kLCBhdHRyc30gPSBhcmdzO1xuICBjb25zdCB7ZHksIGlucHV0fSA9IGlucHV0cztcbiAgY29uc3Qge2ZpbHRlclNpemUsIHN0cmlkZXMsIHBhZCwgZGltUm91bmRpbmdNb2RlfSA9IGF0dHJzO1xuXG4gIGFzc2VydE5vdENvbXBsZXgoW2R5LCBpbnB1dF0sICdtYXhQb29sM0RHcmFkJyk7XG5cbiAgY29uc3QgY29udkluZm8gPSBiYWNrZW5kX3V0aWwuY29tcHV0ZVBvb2wzREluZm8oXG4gICAgICBpbnB1dC5zaGFwZSBhcyBbbnVtYmVyLCBudW1iZXIsIG51bWJlciwgbnVtYmVyLCBudW1iZXJdLCBmaWx0ZXJTaXplLFxuICAgICAgc3RyaWRlcywgMSAvKiBkaWxhdGlvbnMgKi8sIHBhZCwgZGltUm91bmRpbmdNb2RlKTtcblxuICBjb25zdCBpbnB1dEJ1ZiA9IGJhY2tlbmQuYnVmZmVyU3luYyhpbnB1dCk7XG4gIGNvbnN0IG1heFBvc0J1ZiA9IG1heFBvb2wzZFBvc2l0aW9ucyhpbnB1dEJ1ZiwgY29udkluZm8pO1xuICBjb25zdCBzdHJpZGVEZXB0aCA9IGNvbnZJbmZvLnN0cmlkZURlcHRoO1xuICBjb25zdCBzdHJpZGVIZWlnaHQgPSBjb252SW5mby5zdHJpZGVIZWlnaHQ7XG4gIGNvbnN0IHN0cmlkZVdpZHRoID0gY29udkluZm8uc3RyaWRlV2lkdGg7XG4gIGNvbnN0IGRpbGF0aW9uRGVwdGggPSBjb252SW5mby5kaWxhdGlvbkRlcHRoO1xuICBjb25zdCBkaWxhdGlvbkhlaWdodCA9IGNvbnZJbmZvLmRpbGF0aW9uSGVpZ2h0O1xuICBjb25zdCBkaWxhdGlvbldpZHRoID0gY29udkluZm8uZGlsYXRpb25XaWR0aDtcbiAgY29uc3QgZWZmZWN0aXZlRmlsdGVyRGVwdGggPSBjb252SW5mby5lZmZlY3RpdmVGaWx0ZXJEZXB0aDtcbiAgY29uc3QgZWZmZWN0aXZlRmlsdGVySGVpZ2h0ID0gY29udkluZm8uZWZmZWN0aXZlRmlsdGVySGVpZ2h0O1xuICBjb25zdCBlZmZlY3RpdmVGaWx0ZXJXaWR0aCA9IGNvbnZJbmZvLmVmZmVjdGl2ZUZpbHRlcldpZHRoO1xuICBjb25zdCBwYWRGcm9udCA9IGVmZmVjdGl2ZUZpbHRlckRlcHRoIC0gMSAtIGNvbnZJbmZvLnBhZEluZm8uZnJvbnQ7XG4gIGNvbnN0IHBhZExlZnQgPSBlZmZlY3RpdmVGaWx0ZXJXaWR0aCAtIDEgLSBjb252SW5mby5wYWRJbmZvLmxlZnQ7XG4gIGNvbnN0IHBhZFRvcCA9IGVmZmVjdGl2ZUZpbHRlckhlaWdodCAtIDEgLSBjb252SW5mby5wYWRJbmZvLnRvcDtcbiAgY29uc3QgZHggPSBidWZmZXIoaW5wdXQuc2hhcGUsICdmbG9hdDMyJyk7XG5cbiAgY29uc3QgZHlCdWYgPSBiYWNrZW5kLmJ1ZmZlclN5bmM8UmFuaywgJ2Zsb2F0MzInPihkeSk7XG5cbiAgZm9yIChsZXQgYmF0Y2ggPSAwOyBiYXRjaCA8IGNvbnZJbmZvLmJhdGNoU2l6ZTsgKytiYXRjaCkge1xuICAgIGZvciAobGV0IGNoYW5uZWwgPSAwOyBjaGFubmVsIDwgY29udkluZm8uaW5DaGFubmVsczsgKytjaGFubmVsKSB7XG4gICAgICBmb3IgKGxldCBkeERlcHRoID0gMDsgZHhEZXB0aCA8IGNvbnZJbmZvLmluRGVwdGg7ICsrZHhEZXB0aCkge1xuICAgICAgICBmb3IgKGxldCBkeFJvdyA9IDA7IGR4Um93IDwgY29udkluZm8uaW5IZWlnaHQ7ICsrZHhSb3cpIHtcbiAgICAgICAgICBmb3IgKGxldCBkeENvbCA9IDA7IGR4Q29sIDwgY29udkluZm8uaW5XaWR0aDsgKytkeENvbCkge1xuICAgICAgICAgICAgLy8gU2hhZGVyIGNvZGUgYmVnaW5zXG4gICAgICAgICAgICBjb25zdCBkeURlcHRoQ29ybmVyID0gZHhEZXB0aCAtIHBhZEZyb250O1xuICAgICAgICAgICAgY29uc3QgZHlSb3dDb3JuZXIgPSBkeFJvdyAtIHBhZFRvcDtcbiAgICAgICAgICAgIGNvbnN0IGR5Q29sQ29ybmVyID0gZHhDb2wgLSBwYWRMZWZ0O1xuICAgICAgICAgICAgbGV0IGRvdFByb2QgPSAwO1xuICAgICAgICAgICAgZm9yIChsZXQgd0RlcHRoID0gMDsgd0RlcHRoIDwgZWZmZWN0aXZlRmlsdGVyRGVwdGg7XG4gICAgICAgICAgICAgICAgIHdEZXB0aCArPSBkaWxhdGlvbkRlcHRoKSB7XG4gICAgICAgICAgICAgIGNvbnN0IGR5RGVwdGggPSAoZHlEZXB0aENvcm5lciArIHdEZXB0aCkgLyBzdHJpZGVEZXB0aDtcbiAgICAgICAgICAgICAgaWYgKGR5RGVwdGggPCAwIHx8IGR5RGVwdGggPj0gY29udkluZm8ub3V0RGVwdGggfHxcbiAgICAgICAgICAgICAgICAgIE1hdGguZmxvb3IoZHlEZXB0aCkgIT09IGR5RGVwdGgpIHtcbiAgICAgICAgICAgICAgICBjb250aW51ZTtcbiAgICAgICAgICAgICAgfVxuICAgICAgICAgICAgICBmb3IgKGxldCB3Um93ID0gMDsgd1JvdyA8IGVmZmVjdGl2ZUZpbHRlckhlaWdodDtcbiAgICAgICAgICAgICAgICAgICB3Um93ICs9IGRpbGF0aW9uSGVpZ2h0KSB7XG4gICAgICAgICAgICAgICAgY29uc3QgZHlSb3cgPSAoZHlSb3dDb3JuZXIgKyB3Um93KSAvIHN0cmlkZUhlaWdodDtcbiAgICAgICAgICAgICAgICBpZiAoZHlSb3cgPCAwIHx8IGR5Um93ID49IGNvbnZJbmZvLm91dEhlaWdodCB8fFxuICAgICAgICAgICAgICAgICAgICBNYXRoLmZsb29yKGR5Um93KSAhPT0gZHlSb3cpIHtcbiAgICAgICAgICAgICAgICAgIGNvbnRpbnVlO1xuICAgICAgICAgICAgICAgIH1cbiAgICAgICAgICAgICAgICBmb3IgKGxldCB3Q29sID0gMDsgd0NvbCA8IGVmZmVjdGl2ZUZpbHRlcldpZHRoO1xuICAgICAgICAgICAgICAgICAgICAgd0NvbCArPSBkaWxhdGlvbldpZHRoKSB7XG4gICAgICAgICAgICAgICAgICBjb25zdCBkeUNvbCA9IChkeUNvbENvcm5lciArIHdDb2wpIC8gc3RyaWRlV2lkdGg7XG4gICAgICAgICAgICAgICAgICBpZiAoZHlDb2wgPCAwIHx8IGR5Q29sID49IGNvbnZJbmZvLm91dFdpZHRoIHx8XG4gICAgICAgICAgICAgICAgICAgICAgTWF0aC5mbG9vcihkeUNvbCkgIT09IGR5Q29sKSB7XG4gICAgICAgICAgICAgICAgICAgIGNvbnRpbnVlO1xuICAgICAgICAgICAgICAgICAgfVxuXG4gICAgICAgICAgICAgICAgICBjb25zdCBtYXhQb3MgPSBlZmZlY3RpdmVGaWx0ZXJEZXB0aCAqIGVmZmVjdGl2ZUZpbHRlckhlaWdodCAqXG4gICAgICAgICAgICAgICAgICAgICAgICAgIGVmZmVjdGl2ZUZpbHRlcldpZHRoIC1cbiAgICAgICAgICAgICAgICAgICAgICAxIC1cbiAgICAgICAgICAgICAgICAgICAgICAobWF4UG9zQnVmLmdldChiYXRjaCwgZHlEZXB0aCwgZHlSb3csIGR5Q29sLCBjaGFubmVsKSBhc1xuICAgICAgICAgICAgICAgICAgICAgICBudW1iZXIpO1xuICAgICAgICAgICAgICAgICAgY29uc3QgY3VyUG9zID1cbiAgICAgICAgICAgICAgICAgICAgICB3RGVwdGggKiBlZmZlY3RpdmVGaWx0ZXJIZWlnaHQgKiBlZmZlY3RpdmVGaWx0ZXJXaWR0aCArXG4gICAgICAgICAgICAgICAgICAgICAgd1JvdyAqIGVmZmVjdGl2ZUZpbHRlcldpZHRoICsgd0NvbDtcblxuICAgICAgICAgICAgICAgICAgY29uc3QgbWFzayA9IG1heFBvcyA9PT0gY3VyUG9zID8gMSA6IDA7XG4gICAgICAgICAgICAgICAgICBpZiAobWFzayA9PT0gMCkge1xuICAgICAgICAgICAgICAgICAgICBjb250aW51ZTtcbiAgICAgICAgICAgICAgICAgIH1cblxuICAgICAgICAgICAgICAgICAgY29uc3QgcGl4ZWwgPVxuICAgICAgICAgICAgICAgICAgICAgIGR5QnVmLmdldChiYXRjaCwgZHlEZXB0aCwgZHlSb3csIGR5Q29sLCBjaGFubmVsKTtcbiAgICAgICAgICAgICAgICAgIGRvdFByb2QgKz0gcGl4ZWwgKiBtYXNrO1xuICAgICAgICAgICAgICAgIH1cbiAgICAgICAgICAgICAgfVxuICAgICAgICAgICAgfVxuICAgICAgICAgICAgZHguc2V0KGRvdFByb2QsIGJhdGNoLCBkeERlcHRoLCBkeFJvdywgZHhDb2wsIGNoYW5uZWwpO1xuICAgICAgICAgIH1cbiAgICAgICAgfVxuICAgICAgfVxuICAgIH1cbiAgfVxuXG4gIHJldHVybiBiYWNrZW5kLm1ha2VUZW5zb3JJbmZvKGR4LnNoYXBlLCBkeC5kdHlwZSwgZHgudmFsdWVzKTtcbn1cblxuZXhwb3J0IGNvbnN0IG1heFBvb2wzREdyYWRDb25maWc6IEtlcm5lbENvbmZpZyA9IHtcbiAga2VybmVsTmFtZTogTWF4UG9vbDNER3JhZCxcbiAgYmFja2VuZE5hbWU6ICdjcHUnLFxuICBrZXJuZWxGdW5jOiBtYXhQb29sM0RHcmFkIGFzIHVua25vd24gYXMgS2VybmVsRnVuY1xufTtcbiJdfQ==